An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems

By Manya V. Afonso, José M. Bioucas-Dias, Mário A. T. Figueiredo. 2009

1,118 citations recorded by the source corpus.

We propose a new fast algorithm for solving one of the standard approaches to ill-posed linear inverse problems (IPLIP), where a (possibly nonsmooth) regularizer is minimized under the constraint that the solution explains the observations sufficiently well. Although the regularizer and constraint are usually convex, several particular features of these problems (huge dimensionality, nonsmoothness) preclude the use of off-the-shelf optimization tools and have stimulated a considerable amount of research. In this paper, we propose a new efficient algorithm to handle one class of constrained problems (often known as basis pursuit denoising) tailored to image recovery applications. The proposed algorithm, which belongs to the family of augmented Lagrangian methods, can be used to deal with a variety of imaging IPLIP, including deconvolution and reconstruction from compressive observations (such as MRI), using either total-variation or wavelet-based (or, more generally, frame-based) regularization. The proposed algorithm is an instance of the so-called alternating direction method of multipliers, for which convergence sufficient conditions are known; we show that these conditions are satisfied by the proposed algorithm. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is a strong contender for the state-of-the-art.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

In Optimization & Training

Citations in the corpus

Semantic Image Inpainting with Deep Generative Models (2016, methodology): “We compare our method with TV inpainting [1] and LR inpainting [24, 12] on images with small random holes.”
ISTA-Net: Interpretable Optimization-Inspired Deep Network for Image Compressive Sensing (2017, background): “It is worthwhile to note that ADMM-Net cannot be trivially extended to other CS domains, since it imposes a specific structure to the sampling matrix Φ. Utilizing the same training and 2https://github.com/yangyan92/Deep-ADMM-Net testing brain medical images as ADMM-Net, the CS-MRI results of ISTA-Ne”
The Little Engine That Could: Regularization by Denoising (RED) (2016, positive): “Aiming to solve the problem posed in (6), the ADMM technique [57, 58, 59] suggests handling this by variable splitting, leading to the equivalent problem The constraint is turned into a penalty term, relying on the augmented Lagrangian method (in its scaled dual form [57]), leading to where u…”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, methodology): “For example, here we use the state-of-the-art ADMM algorithm SALSA (Afonso et al. 2011) implemented with g 1 ( θ ) = (cid:107) y − H θ 22 / 2 σ 2 , g 2 ( u ) = α Raguet et al. 2013)).”
Multi-Wiener SURE-LET Deconvolution (2013, positive): “2) Transform-domain sparsity constraints [12]–[16]: Here, the coefficients of a frame-based representation of the original image are estimated under a sparsity-inducing regularizer such as the 1 -norm [17].”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “For example, here we use the state-of-the-art ADMM algorithm SALSA (Afonso et al. 2011) implemented with g1(θ) = ‖y − Hθ‖(2)2/2σ 2, g2(u) = α e f f ‖∇du‖1−2, and the constraint θ = u (though we could have also used other modern algorithms Pesquet and Pustelnik 2012; Combettes and Pesquet 2012; Rague”
Hyperspectral and Multispectral Image Fusion Based on a Sparse Representation (2014, methodology): “Conducting the fusion in a subspace of dimensionm̃λ instead of working with the initial space of dimension mλ greatly decreases the complexity of both SALSA and sparse coding steps.”
Collaborative Sparse Regression for Hyperspectral Unmixing (2014, methodology): “The ADMM algorithm for the formulation (5) is shown in Algorithm 1, where (see [27], [42] is the augmented Lagrangian for problem (5), μ > 0 is a positive constant, and D/μ denotes the Lagrange multipliers associated to the constraint GU + BV = 0.”
Semantic Image Inpainting with Perceptual and Contextual Losses (2016, methodology): “We compare our method with local methods using Total Variation (TV) regularization [2] and low rank minimization [11, 16].”
Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011, neutral): “For a discussion of similar algorithms for related problems in image processing, see [2].”
High-quality hyperspectral reconstruction using a spectral prior (2017, methodology): “We summarize here the key aspects of this solution, and refer the interested reader to other recent works for a more detailed explanation of this technique (e.g., [Afonso et al. 2011]).”
Hyperspectral Pansharpening: A Review (2015, methodology): “These difficulties were tackled by solving the problem via the split augmented lagrangian shrinkage algorithm (SALSA) [69], an instance of ADMM.”
A Convex Formulation for Hyperspectral Image Superresolution via Subspace-Based Regularization (2014, methodology): “With L s = 10 , which is a typical value, only 5% of the number of original variables need to be inferred.”
Total Variation Spatial Regularization for Sparse Hyperspectral Unmixing (2012, methodology): “To solve the problem in (8), we have modified the SUnSAL algorithm [45] following closely the methodology introduced in [62].”
Templates for convex cone problems with applications to sparse signal recovery (2010, methodology): “The second is that there are no existing efficient first-order algorithms to solve the analysis problem, with the exception of the recent NESTA [5] and C-SALSA [1] algorithms, which both work on the LASSO version, and only when AA∗ = I .”
BM3D Frames and Variational Image Deblurring (2011, methodology): “In this paper similar to [12] we confine ourself to the Augmented Langrangian (AL) technique, using it as a simple and efficient tool for an explicit derivation of the reconstruction algorithms.”