Search

Plug-and-Play priors recently emerged as a powerful technique for solving inverse problems by plugging a denoiser into a classical optimization algorithm. The denoiser accounts for the regularization and therefore implicitly determines the prior knowledge on the data, hence replacing typical handcrafted priors. In this paper, we extend the concept of Plug-and-Play priors to use denoisers that can be parameterized for nonconstant noise variance. In that aim, we introduce a preconditioning of the ADMM algorithm, which mathematically justifies the use of such an adjustable denoiser. We additionally propose a procedure for training a convolutional neural network for high quality nonblind image denoising that also allows for pixelwise control of the noise standard deviation. We show that our pixelwise adjustable denoiser, along with a suitable preconditioning strategy, can further improve the Plug-and-Play ADMM approach for several applications, including image completion, interpolation, demosaicing, and Poisson denoising. [ABSTRACT FROM AUTHOR]

Tensor robust principal component analysis (TRPCA) is an important method to handle highdimensional data and has been widely used in many areas. In this paper, we mainly focus on the TRPCA problem based on tensor fibered rank for sparse noise removal, which aims to recover the low-fibered-rank tensor from grossly corrupted observations. Usually, the l1-norm is used as a convex approximation of tensor rank, but it is essentially biased and fails to achieve the best estimation performance. Therefore, we first propose a novel nonconvex model named TRPCAp, in which the lp norm (0 < p <1) is adopted to approximate tensor fibered rank and measure sparsity. Then, an error bound of the estimator of TRPCAp is established and this error bound can be better than those of similar models based on Tucker rank or tubal rank. Further, we use the alternating direction method of multipliers to solve TRPCAp and provide convergence guarantee. Finally, extensive experiments on color images, videos, and hyperspectral images demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper we provide a generalization of the Douglas--Rachford splitting (DRS) and the primal-dual algorithm [L. Condat, J. Optim. Theory Appl., 158 (2013), pp. 460-479; B. C. V\~u, Adv. Comput. Math., 38 (2013), pp. 667-681] for solving monotone inclusions in a real Hilbert space involving a general linear operator. The proposed method allows for primal and dual nonstandard metrics and activates the linear operator separately from the monotone operators appearing in the inclusion. In the simplest case when the linear operator has full range, it reduces to classical DRS. Moreover, the weak convergence of primal-dual sequences to a Kuhn--Tucker point is guaranteed, generalizing the main result in [B. F. Svaiter, SIAM J. Control Optim., 49 (2011), pp. 280-287]. Inspired by [D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, M. Fortin and R. Glowinski, eds., Stud. Math. Appl. 15, North-Holland, Amsterdam, 1983, pp. 299-331], we also derive a new split alternating direction method of multipliers (SADMM) by applying our method to the dual of a convex optimization problem involving a linear operator which can be expressed as the composition of two linear operators. The proposed SADMM activates one linear operator implicitly and the other one explicitly, and we recover ADMM when the latter is set as the identity. Connections and comparisons of our theoretical results with respect to the literature are provided for the main algorithm and SADMM. The flexibility and efficiency of both methods is illustrated via numerical simulations in total variation image restoration and a sparse minimization problem. [ABSTRACT FROM AUTHOR]

Although originally designed and analyzed for convex problems, the alternating direction method of multipliers (ADMM) and its close relatives, Douglas–Rachford splitting (DRS) and Peaceman–Rachford splitting (PRS), have been observed to perform remarkably well when applied to certain classes of structured nonconvex optimization problems. However, partial global convergence results in the nonconvex setting have only recently emerged. In this paper we show how the Douglas–Rachford envelope, introduced in 2014, can be employed to unify and considerably simplify the theory for devising global convergence guarantees for ADMM, DRS, and PRS applied to nonconvex problems under less restrictive conditions, larger prox-stepsizes, and overrelaxation parameters than previously known. In fact, our bounds are tight whenever the overrelaxation parameter ranges in (0, 2]. The analysis of ADMM uses a universal primal equivalence with DRS that generalizes the known duality of the algorithms. [ABSTRACT FROM AUTHOR]

The well-known interior point method for semidefinite progams can only be used to tackle problems of relatively small scales. First-order methods such as the the alternating direction method of multipliers (ADMM) have much lower computational cost per iteration. However, their convergence can be slow, especially for obtaining highly accurate approximations. In this paper, we present a practical and efficient second-order semismooth Newton type method based on solving a fixed-point mapping derived from an equivalent form of the ADMM. We discuss a number of techniques that can be used to improve the computational efficiency of the method and achieve global convergence. Then we further consider the application in electronic structure calculations. The ground state energy of a many-electron system can be approximated by an variational approach in which the total energy of the system is minimized with respect to one- and two-body reduced density matrices instead of many-electron wavefunctions. This problem can be formulated as a semidefinite programming problem. Extensive numerical experiments show that our approach is competitive to the state-of-the-art methods in terms of both accuracy and speed. [ABSTRACT FROM AUTHOR]

Regularized inversion methods for image reconstruction are used widely due to their tractability and their ability to combine complex physical sensor models with useful regularity criteria. Such methods motivated the recently developed Plug-and-Play prior method, which provides a framework to use advanced denoising algorithms as regularizers in inversion. However, the need to formulate regularized inversion as the solution to an optimization problem limits the expressiveness of possible regularity conditions and physical sensor models. In this paper, we introduce the idea of consensus equilibrium (CE), which generalizes regularized inversion to include a much wider variety of both forward (or data fidelity) components and prior (or regularity) components without the need for either to be expressed using a cost function. CE is based on the solution of a set of equilibrium equations that balance data fit and regularity. In this framework, the problem of MAP estimation in regularized inversion is replaced by the problem of solving these equilibrium equations, which can be approached in multiple ways. The key contribution of CE is to provide a novel framework for fusing multiple heterogeneous models of physical sensors or models learned from data. We describe the derivation of the CE equations and prove that the solution of the CE equations generalizes the standard MAP estimate under appropriate circumstances. We also discuss algorithms for solving the CE equations, including a version of the Douglas--Rachford/alternating direction method of multipliers algorithm with a novel form of preconditioning and Newton's method, both standard form and a Jacobian-free form using Krylov subspaces. We give several examples to illustrate the idea of CE and the convergence properties of these algorithms and demonstrate this method on some toy problems and on a denoising example in which we use an array of convolutional neural network denoisers, none of which is tuned to match the noise level in a noisy image but which in consensus can achieve a better result than any of them individually. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems. We show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules. [ABSTRACT FROM AUTHOR]

This paper is concerned with deblurring and spectral analysis of ground-based astronomical images of space objects. A numerical approach is provided for deblurring and sparse unmixing of ground-based hyperspectral images (HSIs) of objects taken through atmospheric turbulence. Hyperspectral imaging systems capture a three-dimensional (3D) datacube (tensor) containing two-dimensional (2D) spatial information and one-dimensional (1D) spectral information at each spatial location. Pixel intensities vary with wavelength bands, providing a spectral trace of intensity values and generating a spatial map of spectral variation (spectral signatures of materials). The deblurring and spectral unmixing problem is quite challenging since the point spread function (PSF) depends on the imaging system as well as the seeing conditions and is wavelength varying. We show how to efficiently construct an optimal Kronecker product-based preconditioner, and provide numerical methods for estimating the multiple PSFs using spectral data from an isolated (guide) star for joint deblurring and sparse unmixing of HSI datasets in order to spectrally analyze the image objects. The methods are illustrated with numerical experiments on a commonly used test example, a simulated HSI of the Hubble Space Telescope satellite. [ABSTRACT FROM AUTHOR]

Alternating direction methods are a common tool for general mathematical programming and optimization. These methods have become particularly important in the field of variational image processing, which frequently requires the minimization of nondifferentiable objectives. This paper considers accelerated (i.e., fast) variants of two common alternating direction methods: the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). The proposed acceleration is of the form first proposed by Nesterov for gradient descent methods. In the case that the objective function is strongly convex, global convergence bounds are provided for both classical and accelerated variants of the methods. Numerical examples are presented to demonstrate the superior performance of the fast methods for a wide variety of problems. [ABSTRACT FROM AUTHOR]

Over the last 30 years a plethora of variational regularization models for image reconstruction have been proposed and thoroughly inspected by the applied mathematics community. Among them, the pioneering prototype often taught and learned in basic courses in mathematical image processing is the celebrated Rudin--Osher--Fatemi (ROF) model [L. I. Rudin, S. Osher, and E. Fatemi, Phys. D, 60 (1992), pp. 259--268], which relies on the minimization of the edge-preserving total variation (TV) seminorm as a regularization term. Despite its (often limiting) simplicity, this model is still very much employed in many applications and used as a benchmark for assessing the performance of modern learning-based image reconstruction approaches, thanks to its thorough analytical and numerical understanding. Among the many extensions to TV proposed over the years, a large class is based on the concept of space variance. Space-variant models can indeed overcome the intrinsic inability of TV to describe local features (strength, sharpness, directionality) by means of an adaptive mathematical modeling which accommodates local regularization weighting, variable smoothness, and anisotropy. Those ideas can further be cast in the flexible Bayesian framework of generalized Gaussian distributions and combined with maximum likelihood and hierarchical optimization approaches for efficient hyperparameter estimation. In this work, we review and connect the major contributions in the field of space-variant TVtype image reconstruction models, focusing, in particular, on their Bayesian interpretation which paves the way to new exciting and unexplored research directions. [ABSTRACT FROM AUTHOR]

We propose an inverted approach to the Sparse Principal Component Analysis (SPCA) problem. Most previous research efforts focused on solving the problem of maximizing the variance subject to sparsity constraints or penalizing lack of sparsity. We focus on the problem of minimizing the number of nonzero elements of the loadings subject to a variance constraint. We derive a tractable approach for this problem using Semidefinite Programming (SDP). Our method minimizes a non-convex penalty function mimicking a cardinality penalty function more closely than the convex ℓ 1 norm which has been studied before. We develop a novel iterative weighted ℓ 1 norm minimization algorithm referred to as PCA Sparsified. We develop two algorithms to solve the weighted ℓ 1 norm minimization problem which have different efficiency estimates and computational complexity. Convergence properties of PCA Sparsified are studied. Connections to previously proposed methods are discussed. We introduce a preprocessing method to shrink the problem size which can also be used in previously proposed approaches. Numerical results based on careful implementation show the efficacy and potential of the proposed approach. [ABSTRACT FROM AUTHOR]

In this paper we propose an efficient method for a convex optimization problem which involves a large nonsymmetric and non-Toeplitz matrix. The proposed method is an instantiation of the alternating direction method of multipliers applied in Krylov subspace. Our method offers significant advantages in computational speed for the convex optimization problems involved with general matrices of large size. We apply the proposed method to the restoration of spatially variant blur. The matrix representing spatially variant blur is not block circulant with circulant blocks (BCCB). Efficient implementation based on diagonalization of BCCB matrices by the discrete Fourier transform is not applicable for spatially variant blur. Since the proposed method can efficiently work with general matrices, the restoration of spatially variant blur is a good application of our method. Experimental results for total variation restoration of spatially variant blur show that the proposed method provides meaningful solutions in a short time. [ABSTRACT FROM AUTHOR]

We introduce a robust optimization method for flip-free distortion energies used, for example, in parametrization, deformation, and volume correspondence. This method can minimize a variety of distortion energies, such as the symmetric Dirichlet energy and our new symmetric gradient energy. We identify and exploit the special structure of distortion energies to employ an operator splitting technique, leading us to propose a novel alternating direction method of multipliers (ADMM) algorithm to deal with the nonconvex, nonsmooth nature of distortion energies. The scheme results in an efficient method where the global step involves a single matrix multiplication and the local steps are closed-form per-triangle/per-tetrahedron expressions that are highly parallelizable. The resulting general-purpose optimization algorithm exhibits robustness to flipped triangles and tetrahedra in initial data as well as during the optimization. We establish the convergence of our proposed algorithm under certain conditions and demonstrate applications to parametrization, deformation, and volume correspondence. [ABSTRACT FROM AUTHOR]

We present a first-order quadratic cone programming algorithm that can scale to very large problem sizes and produce modest accuracy solutions quickly. Our algorithm returns primal-dual optimal solutions when available or certificates of infeasibility otherwise. It is derived by applying Douglas--Rachford splitting to a homogeneous embedding of the linear complementarity problem, which is a general set membership problem that includes quadratic cone programs (QCPs) as a special case. Each iteration of our procedure requires pro jecting onto a convex cone and solving a linear system with a fixed coefficient matrix. If a sequence of related problems are solved, then the procedure can easily be warm-started and make use of factorization caching of the linear system. We demonstrate on a range of public and synthetic datasets that for feasible problems our approach tends to be somewhat faster than applying operator splitting directly to the QCP, and in cases of infeasibility our approach can be significantly faster than alternative approaches based on diverging iterates. The algorithm we describe has been implemented in C and is available open-source in the solver SCS v3.0. [ABSTRACT FROM AUTHOR]

Nowadays the Potts model works as the key mo del in a broad spectrum of applications in image processing and computer vision, which can be mathematically formulated in the form of min-cuts and, meanwhile, solved in terms of flow maximizing under the perspective of primal and dual. It is of great interest in developing efficient methods with better algorithmic structures and proved convergence, which is, however, still lost and open for the classical augmented Lagrangian method (ALM)-based approaches. In this work, we propose two novel preconditioned and overrelaxed alternating direction methods of multipliers (ADMMs) with guaranteed convergence, which are based on the classical Eckstein--Bertsekas and Fortin--Glowinski splitting techniques. Particularly, the two new algorithms are essentially accelerated with the proposed preconditioners and overrelaxation schemes. We explore the proposed preconditioned overrelaxed ADMM methods for image segmentation; experiment results demonstrate the proposed methods significantly outperform the classical ALM-based algorithms in terms of superior numerical efficiency along with proved convergence. [ABSTRACT FROM AUTHOR]

We propose a new method for computing dynamic mode decomposition evolution matrices, which we use to analyze dynamical systems. Unlike the majority of existing methods, our approach is based on a variational formulation consisting of data alignment penalty terms and constitutive orthogonality constraints. Our method does not make any assumptions on the structure of the data or their size, and thus it is applicable to a wide range of problems including nonlinear scenarios or extremely small observation sets. In addition, our technique is robust to noise that is independent of the dynamics and it does not require input data to be sequential. Our key idea is to introduce a regularization term for the forward and backward dynamics. The obtained minimization problem is solved efficiently using the alternating method of multipliers (ADMM) which requires two Sylvester equation solves per iteration. Our numerical scheme converges empirically and is similar to a provably convergent ADMM scheme. We compare our approach to various state-of-the-art methods on several benchmark dynamical systems. [ABSTRACT FROM AUTHOR]

We propose a new space-variant anisotropic regularization term for variational image restoration, based on the statistical assumption that the gradients of the target image distribute locally according to a bivariate generalized Gaussian distribution. The highly flexible variational structure of the corresponding regularizer encodes several free parameters which hold the potential for faithfully modeling the local geometry in the image and describing local orientation preferences. For an automatic estimation of such parameters, we design a robust maximum likelihood approach and report results on its reliability on synthetic data and natural images. For the numerical solution of the corresponding image restoration model, we use an iterative algorithm based on the alternating direction method of multipliers. A suitable preliminary variable splitting together with a novel result in multivariate nonconvex proximal calculus yield a very efficient minimization algorithm. Several numerical results showing significant quality improvement of the proposed model with respect to some related state-of-the-art competitors are reported, in particular, in terms of texture and detail preservation. [ABSTRACT FROM AUTHOR]

We consider the sequence acceleration problem for the alternating direction method of multipliers (ADMM) applied to a class of equality-constrained problems with strongly convex quadratic objectives, which frequently arise as the Newton subproblem of interior-point methods. Within this context, the ADMM update equations are linear, the iterates are confined within a Krylov subspace, and the general minimum residual (GMRES) algorithm is optimal in its ability to accelerate convergence. The basic ADMM method solves a κ-conditioned problem in O(√ κ) iterations. We give theoretical justification and numerical evidence that the GMRES-accelerated variant consistently solves the same problem in O(κ1/4) iterations for an order-of-magnitude reduction in iterations, despite a worst-case bound of O(√ κ) iterations. The method is shown to be competitive against standard preconditioned Krylov subspace methods for saddle-point problems. The method is embedded within SeDuMi, a popular open-source solver for conic optimization written in MATLAB, and used to solve many large-scale semidefinite programs with error that decreases like O(1/k²), instead of O(1/k), where k is the iteration index. [ABSTRACT FROM AUTHOR]

We discuss the application of the augmented Lagrangian method to the convex optimization problem of instationary variational mean field games with diffusion. The problem is first discretized with space-time tensor product piecewise polynomial bases. This leads to a sequence of linear problems posed on the space-time cylinder that are second order in the temporal variable and fourth order in the spatial variable. To solve these large linear problems with the preconditioned conjugate gradients method, we propose a preconditioner that is based on a temporal transformation coupled with a spatial multigrid. This preconditioner is thus based on standard components and is particularly suitable for parallel computation. It is conditionally parameter-robust in the sense that the condition number of the preconditioned system is low for sufficiently fine temporal discretizations. Numerical examples illustrate the method. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the sum of a convex function and a convex function composed with an injective linear mapping. For such problems, subject to a coercivity condition at fixed points of the corresponding Picard iteration, iterates of the alternating directions method of multipliers converge locally linearly to points from which the solution to the original problem can be computed. Our proof strategy uses duality and strong metric subregularity of the Douglas-Rachford fixed point mapping. Our analysis does not require strong convexity and yields error bounds to the set of model solutions. We show in particular that convex piecewise linear-quadratic functions naturally satisfy the requirements of the theory, guaranteeing eventual linear convergence of both the Douglas-Rachford algorithm and the alternating directions method of multipliers for this class of objectives under mild assumptions on the set of fixed points. We demonstrate this result on quantitative image deconvolution and denoising with multiresolution statistical constraints. [ABSTRACT FROM AUTHOR]

Finding a fixed point to a nonexpansive operator, i.e., x* = Tx*, abstracts many problems in numerical linear algebra, optimization, and other areas of data science. To solve fixed- point problems, we propose ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update x in an asynchronous parallel fashion. Asynchrony is crucial to parallel computing since it reduces synchronization wait, relaxes communication bottleneck, and thus speeds up computing significantly. At each step of ARock, an agent updates a randomly selected coordinate xi based on possibly out-of-date information on x. The agents share x through either global memory or communication. If writing xi is atomic, the agents can read and write x without memory locks. We prove that if the nonexpansive operator T has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed point of T. Our conditions on T and step sizes are weaker than those in comparable work. Linear convergence is obtained under suitable assumptions. We propose special cases of ARock for linear systems, convex optimization, and machine learning, as well as distributed and decentralized consensus problems. Numerical experiments solving sparse logistic regression problems are presented. [ABSTRACT FROM AUTHOR]