PaperlayerView exact revision on arXiv

Source-linked AI summary

NESTA: A Fast and Accurate First-order Method for Sparse Recovery

Stephen Becker, Jerome Bobin, Emmanuel Candes

arXiv:0904.3367v1math.OC

TL;DR

Large-scale recovery from indirect or undersampled measurements requires algorithms that are both computationally efficient and sufficiently accurate for high-dynamic-range signals. The paper develops NESTA by extending Nesterov’s smoothing and accelerated first-order ideas to sparse-recovery problems. NESTA is reported to be accurate, competitive, and adaptable across ℓ1, total-variation, and broader transform-based formulations.

  • Problem

    Large-scale recovery is challenging because second-order methods are computationally costly, whereas many first-order methods do not provide sufficient accuracy for high-dynamic-range or approximately sparse signals.

  • Method

    NESTA extends Nesterov’s smoothing and accelerated-gradient framework, using continuation and inexpensive matrix-vector operations for constrained sparse-recovery problems.

  • Results

    NESTA is reported to be accurate and competitive with state-of-the-art alternatives, outperforming most compared methods on approximately sparse signals while remaining comparable to the best.

  • Takeaways & Limitations

    NESTA’s minor adaptations support a range of signal and image processing problems, including total-variation and nonstandard ℓ1 minimization.

  • Takeaways & Limitations

    The paper focuses on cases where A∗A is a projector and identifies extension to nonprojector, nondiagonal settings as important future work.

Abstract

from arXiv · show

Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel first-order methods in convex optimization, most notably Nesterov's smoothing technique, this paper introduces a fast and accurate algorithm for solving common recovery problems in signal processing. In the spirit of Nesterov's work, one of the key ideas of this algorithm is a subtle averaging of sequences of iterates, which has been shown to improve the convergence properties of standard gradient-descent algorithms. This paper demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as 1) it is computationally efficient, 2) it is accurate and returns solutions with several correct digits, 3) it is flexible and amenable to many kinds of reconstruction problems, and 4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization, and convex programs seeking to minimize the l1 norm of Wx under constraints, in which W is not diagonal.

1. Introduction.

Large-scale sparse recovery requires methods that combine computational efficiency with high accuracy, especially for realistic signals spanning a large dynamic range. The paper introduces NESTA, a Nesterov-based first-order algorithm designed to provide accurate, flexible recovery across several formulations.

  • Compressed sensing exploits sparsity or compressibility to recover signals from relatively small amounts of sampled data.
  • Large-scale recovery is difficult because second-order methods require expensive linear solves, while many first-order methods sacrifice accuracy.
  • At least five digits of precision may be necessary to detect components around 100 dB below unit-scale signal components.
  • NESTA extends Nesterov’s smoothing and accelerated-gradient framework to recovery problems from incomplete measurements.
  • NESTA uses inexpensive matrix-vector operations per iteration and a principal smoothing parameter, with continuation available to accelerate convergence.
  • Experiments report that NESTA obtains the first 4 or 5 significant digits of optimal ℓ1- or total-variation solutions in a few hundred iterations.
  • The algorithm adapts beyond ℓ1 minimization to total variation and constrained minimization of ∥Wx∥ℓ1 for broad transform or dictionary choices.
  • The paper evaluates NESTA through broad comparisons on very large, high-dynamic-range problems and discusses constrained and Lagrangian sparse-recovery formulations.

2. Nesterov’s method.

Nesterov’s method accelerates convex optimization by combining smoothing, weighted iterate sequences, and prox-functions. Applied to nonsmooth recovery objectives, it achieves faster accuracy-dependent convergence and motivates NESTA for constrained ℓ1 recovery.

  • The framework assumes a differentiable objective with a Lipschitz gradient on the primal feasible set before smoothing is used for nonsmooth objectives.
  • Nesterov’s framework minimizes smooth convex functions over a feasible set using three iteratively estimated sequences and scalar weight sequences.
  • The weighted sequence z_k incorporates earlier gradients through a prox-function, while x_k averages z_k and y_k before gradient evaluation.
  • The accelerated decay scales as L/k^2 rather than L/k for standard gradient-based optimization.
  • For nonsmooth convex objectives represented through a dual feasible set, smoothing produces a differentiable approximation with a Lipschitz gradient.
  • With fixed smoothing, the method converges in O(1/k^2) iterations, while reaching ε accuracy yields O(1/ε), improving on the subgradient rate O(1/ε^2).
  • NESTA applies this smoothed Nesterov framework to quadratically constrained ℓ1 minimization in compressed sensing.

3. Extension to Compressed Sensing.

NESTA solves constrained ℓ1 recovery from undersampled measurements by smoothing the objective and applying accelerated first-order updates. Orthogonal-projector measurement structure enables cheap iterations, while continuation improves convergence for high-dynamic-range signals.

  • NESTA minimizes ∥x∥_ℓ1 subject to ∥b−Ax∥_ℓ2 ≤ ϵ for singular undersampled measurement matrices.
  • When A∗A is an orthogonal projector, NESTA updates auxiliary iterates yk and zk using only a few matrix-vector products.This structure commonly arises with subsampled Fourier, cosine, Hadamard, and related unitary transforms.
  • NESTA smooths the objective through a dual prox-function, yielding the Huber function with gradient Lipschitz constant 1/µ.The smoothing parameter µ trades approximation accuracy against convergence speed.
  • A Euclidean primal prox-function is computationally efficient for the quadratic feasible set, and choosing x0 near the solution can reduce the error bound.The paper suggests x0 = A∗b when no prior solution estimate is available.
  • Each NESTA iteration costs 6 CA + O(n), while a unitary-domain change of variables reduces the cost to 2 CU + O(n).For a subsampled DFT, this is essentially the cost of two FFTs.

4. Accurate Optimization.

This section evaluates NESTA’s accuracy against optimal or reference solutions, including across signals with a large dynamic range and varying smoothing parameters. The experiments show accurate recovery and a direct trade-off between the smoothing parameter and precision.

  • Analytic accuracy tests: The exact solution is analytically available when the sparse signal is sufficiently sparse and its nonzero entries are sufficiently large.The solution has the same support and sign as the unknown signal under these conditions.
  • Analytic accuracy tests: NESTA achieves four-digit objective accuracy and an ℓ∞ error of 0.08 on a signal whose nonzero entries span 1 to 10^5.The experiment uses n = 262,144, m = n/8, s = m/100, and approximately 100 dB of dynamic range.
  • Reference accuracy: FISTA reaches an ℓ∞ error of 0.31 and accurate objective values after 20,000 iterations on the same problem.The paper therefore uses high-iteration FISTA as its reference method in subsequent comparisons.
  • Parameter sensitivity: Decreasing NESTA’s µ by a factor of 10 yields about one additional digit of accuracy on the optimal value in the higher-sparsity experiment.The comparison uses µ ∈ {0.2, 0.02, 0.002} with corresponding tolerances δ = 10^-6, 10^-7, and 10^-8.
  • Parameter sensitivity: The paper selects µ = 0.02 and δ = 10^-7 as defaults because they provide four to five accurate digits and an ℓ∞ error below 1 in the reported experiment.The chosen µ also separates nonzero entries from the noise floor when σ = 0.01.

5. Numerical comparisons.

The comparison section targets difficult, realistic ℓ1 reconstruction problems and examines computed solutions against optimal solutions on entries with magnitude above 1. The stated focus is recovering lower-magnitude entries accurately.

  • Comparison focus: Figure 4.2 compares computed solutions with the optimal solution using absolute values of entries whose optimal magnitude exceeds 1.The figure isolates entries above a specified magnitude threshold.
  • Comparison focus: The experiments are designed around hard but realistic ℓ1 reconstruction problems rather than only relatively easy academic problems.The section describes these as extensive comparisons of optimization methods.
  • Comparison focus: Recovering low-magnitude signal entries accurately is more challenging than finding the most significant entries.This motivates examining solution accuracy beyond the largest coefficients.

1. High dynamic range.

Realistic signals are seldom exactly sparse and may contain many low-level coefficients. Accurate recovery of these coefficients is therefore important in signal and image processing.

  • High dynamic range: Realistic signals are seldom exactly sparse.The section emphasizes approximate rather than exact sparsity as the practical setting.
  • High dynamic range: Approximately sparse signals contain many low-level entries that may still be worth retrieving.The passage frames these entries as relevant rather than negligible.
  • High dynamic range: Wavelet coefficients of natural images are given as an example containing many low-level entries.This example connects approximate sparsity to image-processing data.

2. Approximate sparsity.

Large-scale recovery remains difficult because accurate second-order methods require costly linear-system solves, while some software does not exploit fast applications of A. The paper therefore focuses on problems with more than a quarter million unknowns.

  • Approximate sparsity: Interior-point methods can provide accurate solutions but are not applicable to large-scale problems because solving linear systems is costly.Their Newton steps require large linear systems.
  • Approximate sparsity: Many existing software packages fail to exploit fast algorithms for applying A.This limits efficiency in the large-scale setting described by the paper.
  • Approximate sparsity: The experiments focus on problems with n = 262,144 unknowns, exceeding a quarter of a million.This defines the scale targeted in the section.

3. Large scale.

The section characterizes the compared algorithms as state-of-the-art methods for sparse reconstruction. It emphasizes their competitiveness within this class of methods.

  • The methods discussed are considered state-of-the-art sparse reconstruction algorithms.
  • They are described as among the most competitive sparse reconstruction methods.
  • The passage notes that many of these methods have undergone subsequent improvement or were recently introduced.

5.1. State-of-the-art methods.

This section reviews competing sparse-reconstruction algorithms and their implementations, emphasizing rapid methods compatible with fast applications of A. It also describes stopping and continuation choices used in the comparisons.

  • Comparison scope: The comparison focuses on rapid algorithms that can exploit fast application of A to a vector.
  • NESTA parameters: NESTA uses at most 10,000 iterations, equivalent to 20,000 calls to A or A∗, as the common DNC threshold.
  • Compared methods: GPSR, SpaRSA, l1 ls, FPC, FPC-AS, Bregman, and FISTA represent alternative first-order, interior-point, or iterative reconstruction approaches.
  • Compared methods: Continuation and step-size strategies vary across methods, including Barzilai-Borwein heuristics, shrinkage, active sets, and conjugate-gradient preconditioning.
  • FISTA: FISTA has a theoretical convergence rate of O(1/k^2) and is run once for a high-accuracy reference solution.

5.2. Constrained versus unconstrained minimization.

The section contrasts constrained and unconstrained formulations and argues that NESTA and SPGL1 offer broader practical flexibility. With continuation, both are reported as robust for arbitrary signals.

  • NESTA and SPGL1 solve more general formulations than the other compared algorithms.
  • NESTA handles a wide variety of constrained problems, extending its generality beyond SPGL1.
  • Estimating an appropriate ϵ may be easier in practice than estimating an appropriate λ.
  • NESTA with continuation and SPGL1 with continuation are reported as the most robust methods for arbitrary signals.
  • Comparisons are difficult because NESTA solves BPϵ while other algorithms solve QPλ, and equivalence between ϵ and λ is difficult to compute accurately.

5.3. Experimental protocol.

The experimental protocol constructs nearly equivalent constrained and unconstrained reference problems, then compares methods using accuracy-based stopping criteria. Both criteria are tested to reduce formulation-related bias.

  • Problem matching: The protocol estimates λ from an SPGL1 solution and computes a highly accurate corresponding ϵ using FISTA with δ = 10^-14.
  • Problem matching: The constrained problem BPϵ minimizes the ℓ1 norm over a feasible set defined by ∥Ax − b∥ℓ2 ≤ ϵ.
  • Stopping criteria: Other algorithms are asked to reach solutions at least as accurate as NESTA’s continuation-based solution.
  • Stopping criteria: Criterion 1 requires no larger ℓ1 norm and at most 1.05 times NESTA’s residual norm.
  • Stopping criteria: Both stopping criteria are used because different algorithms naturally solve QPλ or BPϵ, and their practical results are not significantly different.

5.4. Numerical results.

Across exactly and approximately sparse recovery tests, NESTA with continuation remained competitive as signal difficulty increased, while several alternatives degraded sharply. It also performed well on realistic approximately sparse signals and supported broader regularization functions.

  • Exactly sparse signals: As dynamic range increased, SPGL1, FISTA, FPC, and GPSR degraded faster than NESTA with continuation.SPGL1 required about 9× more calls and FISTA about 200× more iterations at 100 dB than at 20 dB; GPSR did not converge at 80 and 100 dB.
  • Exactly sparse signals: Continuation reduced NESTA's function calls by up to about 20× on high-dynamic-range exactly sparse signals.The largest reported reduction occurred for the 100 dB case.
  • Exactly sparse signals: NESTA with continuation was comparable to state-of-the-art algorithms for exactly sparse signals with significant dynamic range.The experiments used dynamic ranges from 20 to 100 dB, with results averaged over 10 trials.
  • Approximately sparse signals: When noise decreased from σ = 1 to σ = 0.1, NESTA with continuation required 5% more iterations, compared with 90% for SPGL1 and 20% for Bregman.This experiment characterized NESTA's lower sensitivity to dynamic range and noise level.
  • Approximately sparse signals: NESTA with continuation, SPGL1, and Bregman were the only methods reported to handle approximately sparse signals effectively.These methods converged in about 2,000 function calls, whereas many others exceeded 10,000 calls or failed within 20,000.
  • Broader applications: NESTA was presented as flexible across regularizers, including nonstandard ℓ1 minimization and total-variation minimization.The paper introduced these as examples beyond its main sparse-recovery experiments.

6. An all-purpose algorithm.

NESTA extends Nesterov’s framework to analysis and synthesis recovery, including total variation and dictionary-based ℓ1 problems. Experiments show useful trade-offs between analysis and synthesis and effective recovery under large dynamic ranges.

  • ℓ1 analysis and synthesis: NESTA solves both analysis and synthesis recovery problems by adapting its first step, while retaining the remaining steps unchanged.Applying W and W∗ adds a low-cost term when fast transforms are available.
  • Radar experiment: The radar test includes a signal of interest more than 60 dB below a dominant sinusoid, creating a challenging large-dynamic-range recovery problem.The frequency-hopping pulse has maximum amplitude 1, versus 1000 for the sinusoid and 10 for the Doppler pulse.
  • Extensions: NESTA’s analysis formulation can also handle reweighted ℓ1 problems without code changes.This follows from its ability to solve analysis problems efficiently.
  • ℓ1 analysis and synthesis: Analysis can better identify weak frequency components, whereas synthesis can better recreate strong pulses and pure tones.The two reconstructions used different µ values to account for dictionary redundancy, with other parameters unchanged.
  • Total variation: For total-variation minimization, Nesterov’s framework uses the TV norm built from horizontal and vertical differences and a TV proximity operator.Evaluating that proximity operator is equivalent to solving a TV denoising problem.
  • Total variation: The TV proximity-operator approach can be computationally demanding and requires side-algorithm parameters whose robust selection is unclear.These issues make the approach difficult to apply to large-scale problems.
  • Numerical comparisons: Continuation remains efficient at high dynamic range, while RecPF fails to converge in the 60 and 80 dB experiments.NESTA with continuation requires 300–400 calls to A and A∗ to reach convergence.
  • Numerical comparisons: The paper reports NESTA as accurate and competitive with state-of-the-art alternatives, particularly for approximately sparse signal recovery.Its applications include recovery problems involving ℓ1 and total-variation norms.

7. Discussion.

The discussion presents NESTA as flexible and efficient but identifies a principal scope boundary: the paper focuses on orthonormal-row sampling matrices. It also outlines extensions to broader matrix classes and related sparse-recovery objectives.

  • Discussion: NESTA’s parameters were not fully optimized, so finer tuning of step sequences and continuation schedules could speed the algorithm.The authors also note that the number of continuation steps was not optimized for the desired accuracy.
  • Discussion: The paper focuses on A∗A being a projector, meaning that A has orthonormal rows.This setting enables fast computation of the iterate sequences and is computationally friendly for compressed sensing.
  • Extensions: When A∗A has well-clustered eigenvalues, conjugate-gradient steps can compute the required update efficiently, extending NESTA beyond projection matrices.A suitable rule for selecting λ is still needed to enforce the constraint.
  • Extensions: The discussion proposes applying Nesterov smoothing and accelerated gradients to related objectives such as the Dantzig selector and sums of ℓ1 and TV norms.These are presented as examples of possible extensions rather than evaluated results.
Loading 0904.3367v1…