PaperlayerView exact revision on arXiv

Source-linked AI summary

Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing

Junfeng Yang, Yin Zhang

arXiv:0912.1185v1math.OC

TL;DR

Sparse recovery in compressive sensing requires efficient methods for ℓ1-minimization problems, while standard approaches can be inefficient for dense sensing matrices. The paper reformulates primal and dual ℓ1 models and applies exact or inexact alternating direction methods, obtaining primal-dual algorithms. The proposed methods are reported as efficient, stable, and accurate relative to appropriate tolerances, with ℓ1 fidelity emphasized when measurements may contain errors.

  • Problem

    Sparse-signal recovery involves ℓ1-minimization problems whose dense sensing matrices make standard optimization methods inefficient.

  • Method

    The paper reformulates several primal or dual ℓ1 problems and applies exact or inexact alternating direction methods that update primal and dual variables.

  • Results

    The proposed ADM algorithms are generally efficient and stable, achieving lower relative errors within fewer or comparable iterations under appropriate noisy-data stopping tolerances.

  • Takeaways & Limitations

    Algorithm speed should be judged at appropriate solution accuracy, and ℓ1-norm fidelity is emphasized when measurements may contain erroneous values.

  • Takeaways & Limitations

    The convergence analysis cited for the inexact ADM does not cover the case where its x-subproblem is solved approximately.

Abstract

from arXiv · show

In this paper, we propose and study the use of alternating direction algorithms for several $\ell_1$-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis-pursuit denoising problems of both unconstrained and constrained forms, as well as others. We present and investigate two classes of algorithms derived from either the primal or the dual forms of the $\ell_1$-problems. The construction of the algorithms consists of two main steps: (1) to reformulate an $\ell_1$-problem into one having partially separable objective functions by adding new variables and constraints; and (2) to apply an exact or inexact alternating direction method to the resulting problem. The derived alternating direction algorithms can be regarded as first-order primal-dual algorithms because both primal and dual variables are updated at each and every iteration. Convergence properties of these algorithms are established or restated when they already exist. Extensive numerical results in comparison with several state-of-the-art algorithms are given to demonstrate that the proposed algorithms are efficient, stable and robust. Moreover, we present numerical results to emphasize two practically important but perhaps overlooked points. One point is that algorithm speed should always be evaluated relative to appropriate solution accuracy; another is that whenever erroneous measurements possibly exist, the $\ell_1$-norm fidelity should be the fidelity of choice in compressive sensing.

1. Introduction.

The paper develops alternating direction methods for ℓ1-minimization problems in compressive sensing, targeting efficient sparse-signal recovery with dense sensing matrices. It also evaluates model choice and algorithm speed under practically relevant noise and accuracy conditions.

  • 1. Introduction.: Compressive sensing reconstructs sparse or nearly sparse signals from fewer linear measurements by solving an underdetermined system.Recovery depends on signal sparsity and suitable properties of the encoding matrix.
  • 1. Introduction.: The ℓ0 decoder can recover sparse signals from limited random measurements but is combinatorial and generally computationally intractable.Basis pursuit replaces this difficult formulation with ℓ1-norm minimization under favorable conditions.
  • 1. Introduction.: Standard interior-point methods are inefficient for these problems because sensing matrices are dense while solutions are sparse.First-order methods that exploit fast matrix-vector multiplications are therefore desirable.
  • 1. Introduction.: The paper introduces alternating direction methods and derives first-order primal-dual algorithms for several ℓ1 models.The approach also yields a MATLAB package, YALL1, supporting eight ℓ1-minimization models, including nonnegative counterparts and local ℓ1 weights.
  • 1. Introduction.: The study compares the proposed algorithms with state-of-the-art methods and examines appropriate speed evaluation and optimization-model choices.These practical issues are addressed through extensive computational results under varied situations.

2. ADM-based first-order primal-dual algorithms.

The paper reformulates ℓ1 problems into separable constrained forms and applies exact or inexact alternating minimization, producing first-order primal-dual algorithms based on primal and dual formulations. It establishes convergence under stated conditions and extends the approach to non-orthonormal matrices with a steepest-descent step.

  • General ADM framework: ADM separates the objective by alternating minimization over two variables, then updates the Lagrange multiplier after one sweep.The framework targets problems whose variables are separate in the objective but coupled by a linear constraint.
  • Primal-based algorithms: The proposed PADMs reformulate primal ℓ1 problems with auxiliary variables and update primal and dual variables at every iteration.They cover basis pursuit and unconstrained and constrained basis-pursuit denoising formulations.
  • Primal-based algorithms: The primal ADM for (1.5) is inexact because its x-subproblem is approximated, while convergence is established when τλmax + γ < 2.For fixed β > 0, the generated sequence converges from any starting point to a solution of the problem.
  • Primal-based algorithms: The same alternating-minimization construction yields a constrained denoising algorithm whose iterates converge under τλmax + γ < 2.The residual update uses projection onto the Euclidean ball Bδ.
  • Dual-based algorithms: Dual-based ADMs, or DADMs, are also first-order primal-dual algorithms because they update primal and dual variables at every iteration.The dual problems are obtained by introducing an auxiliary variable and applying the ADM idea to the resulting formulation.
  • Dual-based algorithms: When AA∗ ≠ I, the exact solution of a dual subproblem is costly, so the paper uses a steepest-descent step; convergence remains an open issue.The resulting algorithm is reported to converge well for random non-orthonormal matrices, although the supplied passage leaves the qualification incomplete.

3. Choice of denoising models.

Experiments compare ℓ1- and ℓ2-based denoising models under impulsive, mixed, and white-noise contamination. The ℓ1/ℓ1 model is preferred when erroneous measurements may occur, while ℓ2 fidelity is preferable under large white noise, where recovery remains low quality.

  • Impulsive noise: The ℓ1/ℓ1 model (1.6) recovers the exact signal to high accuracy across a range of ν values under impulsive noise, although that range shrinks as corruption increases.Models (1.4) and (1.5) yield substantially worse recovered-signal quality in these experiments.
  • Impulsive and mixed noise: Model (1.6) should be preferred over ℓ2-fidelity models whenever measurements may contain erroneous observations or impulsive noise, even with white noise present.The experiments compare impulsive-noise levels of 1%, 5%, and 10%, including white-noise SNRs of 40dB and 20dB.
  • White noise only: Under poor data, model (1.4) performs better than model (1.6), but both produce poor solutions across the tested ν range.At ν = 1, model (1.4) has about 38% relative error versus 42% at ν = 0.05, while model (1.6) reaches about 40%.
  • White noise only: Without impulsive noise, ℓ1 fidelity does no harm when white noise is not large and ν remains reasonably small.On good data, model (1.4) degrades after ν > 0.25, whereas model (1.6) essentially does no harm until ν > 0.7; on fair data, both degrade after ν > 0.7.
  • Practical guidelines: When data contain a large amount of white noise, ℓ2 fidelity should be preferred, although high-quality recovery should not be expected.The authors frame these guidelines as applying at least to random problems of the tested type.

4. Numerical results.

The experiments compare PADM and DADM with several state-of-the-art algorithms and emphasize evaluating speed at accuracy appropriate to the noise level. Across tested noisy cases, the proposed methods generally achieve lower relative errors with fewer or comparable iterations, while their advantage can diminish for highly accurate noiseless solutions.

  • 4.1. Relative error versus optimality.: Algorithm speed should be evaluated relative to the solution accuracy warranted by the data, especially when observations are noisy.For noisy data, further reduction of optimality residue may not improve relative error.
  • 4.1. Relative error versus optimality.: In noiseless data, reducing residue and relative error together improves solution quality, whereas noisy problems reach their best relative error at lower accuracy.For one noisy case, relative error stopped decreasing after residue reached about 10^-2 in about 40 iterations.
  • 4.3. Comparison with FPC-BB, SpaRSA, FISTA and CGD.: PADM and DADM usually decreased relative errors and function values faster than FPC-BB and SpaRSA on the tested noisy problem.Their curves fell below those of FPC-BB and SpaRSA through almost the entire iteration process, although later relative-error increases were attributed to model (1.5).
  • 4.3. Comparison with FPC-BB, SpaRSA, FISTA and CGD.: DADM converged faster than IST and FISTA in function value, and its convergence was unaffected when µ decreased from 10^-3 to 10^-4.At µ = 10^-3, FISTA reached a nearly optimal function value within 200 iterations, while IST required more than 1000.
  • 4.3. Comparison with FPC-BB, SpaRSA, FISTA and CGD.: DADM decreased both function value and relative error faster than CGD and FPC-BB in the reported comparison.CGD decreased function value faster than FPC-BB but did not necessarily decrease relative error faster.
  • 4.3. Comparison with FPC-BB, SpaRSA, FISTA and CGD.: PADM and DADM obtained smaller relative errors in comparable iteration counts to FPC-BB and SpaRSA, especially on more difficult problems.Similar behavior was observed for partial DCT matrices and sparse signals with different dynamic ranges.
  • 4.4. Comparison with SPGL1 and NESTA.: Against SPGL1 and NESTA, PADM and DADM generally achieved smaller relative errors with fewer or comparable matrix-vector multiplications.NESTA reduced fidelity residue fastest but relative error slowest; DADM could be slower than SPGL1 when noiseless data demanded high accuracy.
  • 4.6. Summary.: The authors conclude that the proposed ADM algorithms are efficient and stable under noisy conditions with appropriate stopping tolerances.They generally achieved lower relative errors within fewer or comparable iterations, and dual-based ADMs were generally more efficient than primal-based ADMs.

5. Concluding remarks.

The paper develops primal-dual alternating direction algorithms for ℓ1-problems and finds them competitive, robust, and particularly effective for noisy measurements. It also highlights broader applicability to ℓ1-like regularized problems and open convergence questions for some inexact schemes.

  • Algorithms: The proposed algorithms reformulate ℓ1-problems and apply alternating direction methods, yielding primal-dual iterations for numerous compressive-sensing models.Their per-iteration cost is dominated by two matrix-vector multiplications.
  • Numerical results: Experiments show the ADM algorithms, especially dual-based variants, perform competitively with several state-of-the-art methods on noisy test problems.
  • Numerical results: The algorithms converge relatively fast without continuation or line search, are relatively insensitive to parameters, and quickly reduce relative error to true solutions.
  • Numerical results: They are not necessarily fastest at extremely high accuracy on noiseless data but are arguably most effective at the best achievable accuracy with nontrivial noise.The latter setting is identified as most relevant to practical applications.
  • Broader applicability: The ADM framework also extends naturally to nuclear-norm and total-variation regularized problems through analogous formulations and splitting variables.The discussion connects these extensions to matrix completion, image reconstruction, and related optimization problems.
  • Open issues: New applications raise further research issues, including convergence of certain inexact ADM schemes.

Appendix A. Proof of Theorem 2.1.

The appendix proves convergence of the alternating-direction iteration by establishing residual decay, boundedness, and convergence of the relevant energy measure. Limit-point analysis then shows that the iterates converge to a solution of the optimization problem.

  • Optimality conditions: The proof begins from optimality conditions involving primal feasibility, dual subgradients, and the auxiliary residual variable.
  • Iteration reformulation: The iteration is rewritten using auxiliary variables so the dual update becomes a relaxed step toward an intermediate dual iterate.
  • Descent argument: Under τλmax + γ < 2, a positive descent parameter is obtained for the convergence argument.
  • Convergence properties: The proof establishes vanishing successive differences, bounded iterates, and convergence of the associated G-metric energy.
  • Limit-point analysis: Limit-point arguments combined with the shrinkage relation show that every limit point satisfies the optimization problem’s solution conditions.The resulting primal, residual, and dual variables solve the stated problem.
Loading 0912.1185v1…