Source-linked AI summary
Fast Image Recovery Using Variable Splitting and Constrained Optimization
Manya V. Afonso, José M. Bioucas-Dias, Mário A. T. Figueiredo
TL;DR
The paper addresses unconstrained regularized image reconstruction and restoration, including wavelet- and total-variation-based formulations. It introduces SALSA through variable splitting and ADMM, and reports faster performance than competing methods across standard image-recovery problems.
Problem
The paper addresses unconstrained image reconstruction and restoration problems whose objectives combine data fidelity with regularization.
Method
SALSA splits the variable into an equivalent constrained formulation and applies an augmented Lagrangian method, specifically ADMM, using a regularized data-fidelity Hessian for efficient computation.
Results
Experiments on deconvolution, MRI reconstruction, and inpainting show that SALSA is faster than previous state-of-the-art methods.
Takeaways & Limitations
SALSA provides a fast approach applicable to wavelet-based and total-variation regularization across standard image-recovery tasks.
Abstract
from arXiv · showhide
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 $\ell_2$ data-fidelity term and a non-smooth 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.
I. INTRODUCTION
Image restoration estimates an unknown image from noisy indirect observations using regularization because the inverse problem is ill-posed. The paper considers wavelet-based synthesis and direct image-domain regularization formulations, including total variation.
- Problem formulation: Image restoration models a noisy observation y as the output of a linear operator applied to an unknown image x, plus noise.The operator can represent convolution, tomographic projections, partial Fourier observations, or missing pixels.
- Problem formulation: Regularization is needed because estimating x from y is ill-posed.Regularization incorporates prior information to make the inverse problem solvable satisfactorily.
- Wavelet-based formulation: Wavelet-based synthesis represents x as Wβ and estimates coefficients β with a nonsmooth or possibly nonconvex regularizer.The final image estimate is reconstructed as Wβ̂.
- Analysis formulation: An alternative analysis formulation applies the regularizer directly to the unknown image x.Total variation is identified as a prominent regularizer in this class of approaches.
- Constrained formulations: The unconstrained criteria can be viewed as Lagrangians of associated constrained optimization problems, with corresponding relationships between their solutions.For feasible constrained problems, non-null solutions of one formulation correspond to minimizers of the unconstrained formulation for some τ > 0.
B. Previous Algorithms
Earlier methods primarily solve the regularized objective through iterative shrinkage or its accelerated variants. Their speed can be limited by ill-conditioning and small regularization parameters, motivating faster alternatives and continuation strategies.
- IST: IST applies a gradient step on the data-fidelity term followed by the regularizer’s shrinkage or thresholding function.The step size is 1/γ, and the gradient is A^H(Ax_k − y).
- IST limitations: For convex φ, IST converges, but it may be slow when τ is very small or A is highly ill-conditioned.These limitations motivated several faster variants.
- Accelerated variants: TwIST uses two previous iterates and can achieve speed gains of up to two orders of magnitude over IST on typical benchmark problems.It was evaluated on wavelet-based and TV-based image restoration problems.
- Accelerated variants: FISTA is a nonsmooth variant of Nesterov’s optimal gradient-based method and was shown to outperform IST in speed.SpaRSA instead varies γ across iterations and was experimentally reported to outperform standard IST.
- Continuation: Continuation schemes exploit IST warm-starting by using solutions at one regularization parameter to initialize nearby problems.This strategy is especially relevant when slowness is caused by a small regularization parameter.
C. Proposed Approach
The proposed SALSA algorithm splits the variable of the regularized objective, solves the equivalent constrained problem with augmented-Lagrangian and ADMM techniques, and exploits problem structure for efficient computation. Experiments report consistent speed advantages over prior methods.
- Variable splitting: Variable splitting introduces separate variables for the two objective terms and constrains them to be equal, preserving equivalence with the original problem.The split is chosen so each variable serves as the argument of one function.
- Augmented-Lagrangian solution: The constrained problem is addressed with an augmented-Lagrangian scheme using alternating direction method of multipliers.The paper presents this as the algorithmic route from splitting to SALSA.
- Efficient implementation: ADMM requires a linear solve whose size matches the image or its representation, but convolution, partial Fourier, and related structures permit fast solutions.For several problems, the cost is O(n) or O(n log n); tight Parseval frames also enable efficient solves.
- Experiments: Across benchmark deconvolution, missing-pixel recovery, and partial-Fourier reconstruction experiments, SALSA was consistently and considerably faster than FISTA, TwIST, and SpaRSA.The experiments used both frame-based and TV-based regularization.
- Efficient implementation: SALSA’s speed comes from using a regularized Hessian A^H A of the data-fidelity term rather than essentially only gradient information.This distinguishes its computational mechanism from the cited IST variants.
B. Augmented Lagrangian
The augmented Lagrangian method alternates constrained-objective minimization with multiplier updates. Unlike quadratic penalty methods, it does not require the penalty parameter to approach infinity for convergence guarantees.
- ALM formulation: The augmented Lagrangian introduces a penalty parameter μ and a multiplier vector λ for the linear equality constraints.The formulation applies to p constraints represented by A z = b.
- ALM procedure: ALM minimizes the augmented Lagrangian over the primal variable with multipliers fixed, updates the multipliers, and repeats.The multiplier update uses the constraint residual b − Az_k+1.
- Convergence: Unlike quadratic penalty methods, ALM does not require μ to tend to infinity to guarantee convergence to the constrained solution.The value of μ may also be updated between iterations.
- Equivalent form: ALM can be written using a quadratic term centered at an auxiliary vector d_k, followed by a residual-based update of d_k.This alternative form makes its equivalence with Bregman iterative methods clear.
- Convergence: With adequate initializations, ALM/MM generates a proximal-point sequence for the dual problem, whose iterates converge to a dual solution while primal cluster points solve the constrained problem.This provides the stated convergence characterization for the ALM/MM procedure.
C. ALM/MM for Variable Splitting
The paper applies ALM/MM to a constrained variable-splitting problem, yielding ADMM updates with convergence guarantees under stated convexity, rank, and error conditions.
- Problem (13) is rewritten in the form (11) by introducing f1, f2, and a linear constraint involving G.
- ADMM alternates minimization over u and v, then updates the scaled multiplier d using the constraint residual.
- The joint ALM/MM minimization can be difficult because it contains non-separable quadratic and possibly nonsmooth terms.
- If the constrained problem has a solution, the ADMM sequence converges to a solution under the theorem’s convexity and full-column-rank assumptions.
- Exact subproblem minimization is unnecessary when the optimization errors form an absolutely summable sequence.
- ADMM is connected to Douglas–Rachford splitting applied to the dual problem, while the theorem also covers divergence when no solution exists.
III. PROPOSED METHOD
The proposed formulation replaces the unconstrained recovery problem with an equivalent constraint x = v and distinguishes this splitting from split-Bregman’s treatment of non-separable regularizers.
- The unconstrained regularized image-recovery problem is reformulated as a constrained optimization problem with x = v.
- Split-Bregman methods instead split a regularizer represented as φ(x) = ϕ(D x) by imposing D x = v.
- The proposed splitting assumes that the Moreau proximal mapping of φ can be computed efficiently.
- Its purpose is to exploit second-order Hessian information from f1 rather than resolve non-separability and non-quadratic regularization.
B. Algorithm and Its Convergence
SALSA is obtained by specializing ADMM to the split image-recovery problem, with x- and v-updates followed by a dual update. Its convergence depends on exact or suitably controlled proximal computations.
- Substituting the split formulation into ADMM yields SALSA, the split augmented Lagrangian shrinkage algorithm.
- Each iteration updates x by minimizing the quadratic data-fidelity subproblem, updates v through the regularizer proximal problem, and then applies the stopping criterion.
- SALSA is an ADMM instance with G = I, satisfying the theorem’s full-column-rank condition.
- The x-update minimizes a strictly convex quadratic and therefore reduces to a linear system.
- The linear system uses a regularized Hessian, so SALSA incorporates second-order information from the data-fidelity function.
- Closed-form proximal evaluations guarantee convergence, while iterative evaluations require a summable error sequence; warm starts and decreasing thresholds can achieve this approximately.
C. Computing xk+1
For convolutional operators, SALSA computes the x-update efficiently in the Fourier domain by diagonalizing the system with the discrete Fourier transform.
- Although explicitly forming A is infeasible in the target problems, the required inverse can be computed efficiently in important cases.
- For convolution, A = B, and under periodic boundary conditions B is block-circulant with circulant blocks.
- The Fourier factorization uses a unitary DFT matrix U and a diagonal matrix D containing the convolution operator’s DFT coefficients.
- The diagonal inversion costs O(n), while multiplication by U and U^H costs O(n log n) using FFT; the resulting expression is a frequency-domain Wiener filter.
2) Deconvolution with Frame-Based Synthesis Prior:
The section derives fast linear-system updates for synthesis-prior and related image-reconstruction cases by exploiting matrix structure, Fourier transforms, and fast frame transforms. These simplifications make each SALSA iteration O(n log n) for a broad class of frames and observation models.
- Deconvolution: For periodic convolution with a Parseval frame, the update uses diagonal frequency-domain matrices and FFT products, yielding O(n log n) cost.The resulting operation is a Wiener filter in the frequency domain.
- Overall Complexity: For many tight frames, fast implementations of W and W^H make each SALSA iteration O(n log n).The section cites undecimated wavelets and curvelets as O(n log n) examples, and complex wavelets as an O(n) example.
- Missing Pixels: Image Inpainting: For synthesis priors with missing pixels, the update matrix is diagonal because B^T B is a binary mask, reducing the operation to O(n).Its diagonal entries are 1/(μ+1) or 1/μ, depending on whether a pixel is observed.
- Missing Pixels: Image Inpainting: For synthesis priors under missing-pixel observations, the update applies synthesis, masking, and representation transforms, with cost typically O(n log n).This follows from fast products by W and W^H.
- Partial Fourier Observations: MRI Reconstruction: For partial Fourier observations, synthesis-prior updates combine FFTs with fast frame transforms and retain O(n log n) cost.The observation operator has the form A = BUW.
IV. EXPERIMENTS
The experiments compare SALSA with TwIST, SpaRSA, and FISTA on benchmark deconvolution, inpainting, and partial-Fourier reconstruction problems. For image deconvolution with wavelet or TV regularization, SALSA is reported as clearly faster than the competing methods.
- Experimental Design: The benchmark suite covers deconvolution with wavelet and TV regularization, missing-pixel recovery, and partial-Fourier image reconstruction.The comparisons use standard imaging inverse problems and freely available competing implementations.
- Image Deblurring with Wavelets: Five benchmark deblurring problems use the Cameraman image, FFT-based blur application, and hand-tuned ℓ1 regularization for best SNR improvement.Because restored images and SNR improvements were similar to prior results, the study reports computation times.
- Image Deblurring with Wavelets: The wavelet experiments compare a four-level redundant Haar frame with an orthogonal Haar wavelet basis using CPU times and objective-function plots.Figures 1 and 2 show objective evolution for experiments 1A, 2B, and 3A.
- Image Deblurring with Total Variation: The TV experiments use isotropic discrete total variation, with the Moreau proximal mapping computed by five iterations of Chambolle’s algorithm.CPU times are listed for SALSA, TwIST, SpaRSA, and FISTA, with objective evolutions plotted for selected experiments.
- Results: SALSA is always clearly faster than the fastest competing algorithm in image deconvolution with both wavelet-based and TV-based regularization.This conclusion is drawn from Tables II, III, and IV.
C. MRI Image Reconstruction
MRI reconstruction recovers a 128 × 128 Shepp-Logan phantom from 22 noisy radial Fourier lines using TV regularization. SALSA produces a visually comparable reconstruction while running considerably faster than the other algorithms.
- MRI setup: The MRI experiment uses TV regularization, with its Moreau proximal mapping implemented by 40 iterations of Chambolle’s algorithm.
- Results: The MRI reconstruction obtained with SALSA has a comparable mean squared error to the other algorithms.The other reconstructions are described as visually indistinguishable from SALSA’s estimate.
- Algorithm: SALSA uses variable splitting and an augmented Lagrangian method, specifically ADMM, to solve the regularized image-reconstruction formulation.
- Results: SALSA is considerably faster than TwIST, SpaRSA, and FISTA across the benchmark image-recovery experiments.The experiments include deconvolution, MRI reconstruction, and inpainting, using wavelet-based and TV-based regularization.