Fast Image Recovery Using Variable Splitting and Constrained Optimization
IEEE Transactions on Image ProcessingPublished 9 April 2010Open access
Manya Afonso, José M. Bioucas‐Dias, Mário A. T. Figueiredo
Citations1,226
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new fast algorithm is proposed for solving one of the standard formulations of image restoration and reconstruction which consists of an unconstrained optimization problem where the objective includes an l2 data-fidelity term and a nonsmooth regularizer.
Abstract
We propose a new fast algorithm for solving one of the standard formulations of image restoration and reconstruction which consists of an unconstrained optimization problem where the objective includes an l2 data-fidelity term and a nonsmooth regularizer. This formulation allows both wavelet-based (with orthogonal or frame-based representations) regularization or total-variation regularization. Our approach is based on a variable splitting to obtain an equivalent constrained optimization formulation, which is then addressed with an augmented Lagrangian method. The proposed algorithm is an instance of the so-called alternating direction method of multipliers, for which convergence has been proved. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is faster than the current state of the art methods.
Keywords
Computer ScienceEngineering
IEEE Transactions on Information TheoryCompressed sensing
23,147 Citations2006David L. Donoho
It is shown that "most" subspaces in Ropfm are near-optimal, and that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces.
Compressed sensing
17,129 Citations2004David L. Donoho
Elsevier eBooksA Wavelet Tour of Signal Processing
16,401 Citations1999Stéphane Mallat
An introduction to a Transient World and an Approximation Tour of Wavelet Packet and Local Cosine Bases.
IEEE Transactions on Information TheoryRobust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
15,775 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown how one can reconstruct a piecewise constant object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.
Physica D Nonlinear PhenomenaNonlinear total variation based noise removal algorithms
15,672 Citations1992L. Rudin, Stanley Osher +1 more
A constrained optimization type of numerical algorithm for removing noise from images is presented, which appears to be state-of-the-art for very noisy images and yielding sharp edges in the image.
Cambridge University Press eBooksNumerical optimization
14,107 Citations2021W. John Braun, Duncan J. Murdoch
SIAM Journal on Imaging SciencesA Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
12,045 Citations2009Amir Beck, Marc Teboulle
A new fast iterative shrinkage-thresholding algorithm (FISTA) which preserves the computational simplicity of ISTA but with a global rate of convergence which is proven to be significantly better, both theoretically and practically.
Numerical Optimization
8,678 Citations2006Jorge Nocedal, Stephen J. Wright
Communications on Pure and Applied MathematicsStable signal recovery from incomplete and inaccurate measurements
7,170 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown that it is possible to recover x0 accurately based on the data y from incomplete and contaminated observations.
Magnetic Resonance in MedicineSparse MRI: The application of compressed sensing for rapid MR imaging
6,980 Citations2007Michael Lustig, David L. Donoho +1 more
Practical incoherent undersampling schemes are developed and analyzed by means of their aliasing interference and demonstrate improved spatial resolution and accelerated acquisition for multislice fast spin‐echo brain imaging and 3D contrast enhanced angiography.
Computers & Operations ResearchNonlinear programming: theory and algorithms
5,829 Citations1993
The book is a solid reference for professionals as well as a useful text for students in the fields of operations research, management science, industrial engineering, applied mathematics, and also in engineering disciplines that deal with analytical optimization techniques.
Communications on Pure and Applied MathematicsAn iterative thresholding algorithm for linear inverse problems with a sparsity constraint
4,957 Citations2004Ingrid Daubechies, Michel Defrise +1 more
It is proved that replacing the usual quadratic regularizing penalties by weighted 𝓁p‐penalized penalties on the coefficients of such expansions, with 1 ≤ p ≤ 2, still regularizes the problem.
SIAM Journal on Imaging SciencesThe Split Bregman Method for L1-Regularized Problems
4,324 Citations2009Tom Goldstein, Stanley Osher
This paper proposes a “split Bregman” method, which can solve a very broad class of L1-regularized problems, and applies this technique to the Rudin-Osher-Fatemi functional for image denoising and to a compressed sensing problem that arises in magnetic resonance imaging.
IEEE Journal of Selected Topics in Signal ProcessingGradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems
3,542 Citations2007Mário A. T. Figueiredo, Robert D. Nowak +1 more
This paper proposes gradient projection algorithms for the bound-constrained quadratic programming (BCQP) formulation of these problems and test variants of this approach that select the line search parameters in different ways, including techniques based on the Barzilai-Borwein method.
Journal of Mathematical Imaging and VisionAffine Invariant Flows in the Beltrami Framework
3,289 Citations2004Mila Nikolova
The geometric Beltrami framework is shown to incorporate and explain some of the known invariant flows e.g. the equi-affine invariant flow for hypersurfaces, and it is demonstrated that the new concepts put forward enable us to suggest new invariants namely the case where the codimension is greater than one.
Mathematical ProgrammingOn the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators
2,877 Citations1992Jonathan Eckstein, Dimitri P. Bertsekas
This paper shows, by means of an operator called asplitting operator, that the Douglas—Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm, which allows the unification and generalization of a variety of convex programming algorithms.
Multiscale Modeling and SimulationSignal Recovery by Proximal Forward-Backward Splitting
2,599 Citations2005Patrick L. Combettes, Valérie R. Wajs
It is shown that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties, which makes it possible to derive existence, uniqueness, characterization, and stability results in a unified and standardized fashion for a large class of apparently disparate problems.
Multiscale Modeling and SimulationFast Discrete Curvelet Transforms
2,524 Citations2006Emmanuel J. Candès, Laurent Demanet +2 more
This paper describes two digital implementations of a new mathematical transform, namely, the second generation curvelet transform in two and three dimensions, based on unequally spaced fast Fourier transforms, while the second is based on the wrapping of specially selected Fourier samples.
Journal of Optimization Theory and ApplicationsMultiplier and gradient methods
2,410 Citations1969Magnus R. Hestenes
The main purpose of this paper is to suggest a method for finding the minimum of a functionf(x) subject to the constraintg(x)=0, which consists of replacingf byF=f+λg+1/2cg2, and computing the appropriate value of the Lagrange multiplier.
Cambridge University Press eBooksIterative Solution Methods
2,104 Citations1994Owe Axelsson
This paper presents a meta-analyses of matrix eigenvalues and condition numbers for preconditional matrices using the framework of the Perron-Frobenius theory for nonnegative matrices and some simple iterative methods.
IEEE Transactions on Image ProcessingA New TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithms for Image Restoration
2,065 Citations2007José M. Bioucas‐Dias, Mário A. T. Figueiredo
This paper introduces two-step 1ST (TwIST) algorithms, exhibiting much faster convergence rate than 1ST for ill-conditioned problems, and introduces a monotonic version of TwIST (MTwIST); although the convergence proof does not apply, the effectiveness of the new methods are experimentally confirmed on problems of image deconvolution and of restoration with missing samples.
SIAM Journal on Imaging SciencesA New Alternating Minimization Algorithm for Total Variation Image Reconstruction
1,951 Citations2008Yilun Wang, Junfeng Yang +2 more
An alternating minimization algorithm for recovering images from blurry and noisy observations with total variation (TV) regularization from a new half-quadratic model applicable to not only the anisotropic but also the isotropic forms of TV discretizations is proposed.
IEEE Transactions on Signal ProcessingSparse Reconstruction by Separable Approximation
1,880 Citations2009Stephen J. Wright, Robert D. Nowak +1 more
The American StatisticianA Tutorial on MM Algorithms
1,799 Citations2004David R. Hunter, Kenneth Lange
The principle behind MM algorithms is explained, some methods for constructing them are suggested, and some of their attractive features are discussed.
IEEE Signal Processing MagazineDigital image restoration
1,669 Citations1997M.R. Banham, Aggelos K. Katsaggelos
The article introduces digital image restoration to the reader who is just beginning in this field, and provides a review and analysis for the readers who may already be well-versed in image restoration.
Applied and Computational Harmonic AnalysisComplex Wavelets for Shift Invariant Analysis and Filtering of Signals
1,667 Citations2001Nick Kingsbury
This paper describes a form of discrete wavelet transform, which generates complex coefficients by using a dual tree of wavelet filters to obtain their real and imaginary parts and describes how the dual tree may be extended for images and other multi-dimensional signals.
Bulletin of the American Mathematical SocietyVariational methods for the solution of problems of equilibrium and vibrations
1,652 Citations1943Richard Courant
SIAM Journal on Imaging SciencesBregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
1,417 Citations2008Wotao Yin, Stanley Osher +2 more
IEEE Transactions on Image ProcessingAn EM algorithm for wavelet-based image restoration
1,204 Citations2003Mário A. T. Figueiredo, R.D. Nowak
An expectation-maximization (EM) algorithm for image restoration (deconvolution) based on a penalized likelihood formulated in the wavelet domain is introduced, and it is shown that under mild conditions the algorithm converges to a globally optimal restoration.
Inverse ProblemsAnalysis versus synthesis in signal priors
692 Citations2007Michael Elad, Peyman Milanfar +1 more
This paper describes two prior classes, analysis-based and synthesis-based, and shows that although when reducing to the complete and under-complete formulations the two become equivalent, in their more interesting overcomplete formulation the two types depart.
Journal of Mathematical Imaging and VisionAn Algorithm for Total Variation Minimization and Applications
681 Citations2004Antonin Chambolle
An algorithm for minimizing the total variation of an image, and a proof of convergence is provided, which shows applications to image denoising, zooming, and the computation of the mean curvature motion of interfaces.
Handbook of Mathematical Models in Computer Vision
574 Citations2005Nikos Paragios, Olivier Faugeras +1 more
This comprehensive volume provides a detailed discourse on the mathematical models used in computational vision from leading educators and active research experts in this field and serves as a complete reference work for professionals.
IEEE Transactions on Image ProcessingMajorization–Minimization Algorithms for Wavelet-Based Image Restoration
553 Citations2007Mário A. T. Figueiredo, José M. Bioucas‐Dias +1 more
Several new results are proved which strongly support the claim that the SI does not compromise the usefulness of this class of algorithms, and introduce a new algorithm, resulting from using bounds for nonconvex regularizers, which confirms the superior performance of this method, when compared to the one based on quadratic majorization.
IEEE Journal of Selected Topics in Signal ProcessingA Douglas–Rachford Splitting Approach to Nonsmooth Convex Variational Signal Recovery
494 Citations2007Patrick L. Combettes, Jean‐Christophe Pesquet
A decomposition method based on the Douglas-Rachford algorithm for monotone operator-splitting for signal recovery problems and applications to non-Gaussian image denoising in a tight frame are demonstrated.
IEEE Signal Processing LettersNoise reduction using an undecimated discrete wavelet transform
479 Citations1996Markus Lang, Guo Hong-xia +3 more
A new nonlinear noise reduction method is presented that uses the discrete wavelet transform instead of the usual orthogonal one, resulting in a significantly improved noise reduction compared to the original wavelet based approach.
IEEE Signal Processing LettersHilbert transform pairs of wavelet bases
342 Citations2001Ivan Selesnick
This paper gives an alternative derivation and explanation for the result by Kingsbury (1999), that the dual-tree DWT is (nearly) shift-invariant when the scaling filters satisfy the same offset.
Recent Developments in Total Variation Image Restoration
302 Citations2004Tony F. Chan, Selim Esedoḡlu +2 more
There has been a resurgence of interest and exciting new developments in total variation minimizing models, some extending the applicabilities to inpainting, blind deconvolution and vector-valued images, while others offer improvements in better preservation of contrast, geometry and textures.
Proceedings of the ... IEEE International Conference on Acoustics, Speech, and Signal ProcessingSparse reconstruction by separable approximation
194 Citations2008Stephen J. Wright, Robert D. Nowak +1 more
This work proposes iterative methods in which each step is obtained by solving an optimization subproblem involving a quadratic term with diagonal Hessian plus the original sparsity-inducing regularizer, and proves convergence of the proposed iterative algorithm to a minimum of the objective function.
Lecture notes in computer scienceSplit Bregman Algorithm, Douglas-Rachford Splitting and Frame Shrinkage
193 Citations2009Simon Setzer
It is shown that for a special setting based on Parseval frames the gradient descent reprojection and the alternating Split Bregman algorithm are equivalent and turn out to be a frame shrinkage method.
A bound optimization approach to wavelet-based image deconvolution
189 Citations2005Mário A. T. Figueiredo, Rob Nowak
An algorithm based on the bound optimization approach is proposed; this approach allows deriving EM-type algorithms without using the concept of missing/hidden data and has provable monotonicity both with orthogonal or redundant wavelet transforms.
Image Denoising with Shrinkage and Redundant Representations
89 Citations2006Michael Elad, Boaz Matalon +1 more
It is shown that simple shrinkage could be interpreted as the first iteration of an algorithm that solves the basis pursuit denoising (BPDN) problem, which leads to a novel iterative shrinkage algorithm that can be considered as an effective pursuit method.
An iterative algorithm for linear inverse problems with compound regularizers
53 Citations2008José M. Bioucas‐Dias, Mário A. T. Figueiredo
This paper introduces an iterative algorithm to solve the optimization problem resulting from image (or signal) inverse problems with two (or more) regularizers and shows the effectiveness of the proposed algorithm in solving the corresponding optimization problem.
2009 IEEE/SP 15th Workshop on Statistical Signal ProcessingFast frame-based image deconvolution using variable splitting and constrained optimization
29 Citations2009Mario A. T. Figueiredo, Jose M. Bioucas-Dias +1 more
A new fast algorithm for solving one of the standard formulations of frame-based image deconvolution: an unconstrained optimization problem, involving an ℓ2 data-fidelity term and a non-smooth regularizer, based on using variable splitting to obtain an equivalent constrained optimization formulation.