A First-order Augmented Lagrangian Method for Compressed Sensing

Necdet Serhat Aybat, Garud Iyengar

Abstract

We present the First-order Augmented Lagrangian (FAL) algorithm, a novel approach for solving the basis pursuit problem in compressed sensing. FAL operates by inexactly solving a sequence of $\ell_1$-regularized least squares sub-problems using an accelerated proximal gradient method. Each update is computationally efficient, reducing to simple "shrinkage" operations. Theoretically, FAL achieves $\epsilon$-optimal solutions within $O(\log(1/\epsilon))$ iterations and $O(1/\epsilon)$ matrix-vector multiplications. Empirically, FAL demonstrates superior performance compared to state-of-the-art solvers, often achieving 2x to 6x speedups and uniquely identifying signal support without the need for post-processing thresholding.

Introduction

Compressed sensing (CS) has revolutionized signal processing by enabling the reconstruction of sparse, high-dimensional signals from a limited number of linear measurements. The core mathematical challenge is the basis pursuit problem: finding the signal $x$ with the minimum $\ell_1$-norm that satisfies the linear constraint $Ax = b$.

While basis pursuit can be formulated as a linear program, traditional interior-point or simplex methods are computationally prohibitive for large-scale applications. Existing first-order methods offer better scalability but often struggle with convergence rates or precision in noiseless environments. The FAL algorithm addresses these limitations by combining the robustness of the Augmented Lagrangian framework with the efficiency of accelerated proximal gradient methods.

The FAL Algorithm

Methodology

FAL transforms the constrained basis pursuit problem into a sequence of unconstrained sub-problems. Instead of enforcing $Ax = b$ strictly at every step, the algorithm employs an Augmented Lagrangian penalty term. This allows the constraint to be "relaxed" into the objective function, which is then solved iteratively.

Key components of the FAL framework include:

  • Accelerated Proximal Gradient (APG): Each sub-problem is addressed using a variant of Tseng’s APG algorithm. This minimizes the number of expensive matrix-vector multiplications ($Ax$ and $A^Ty$), which are the primary computational bottlenecks.
  • Shrinkage Operators: The core update step in FAL reduces to a "shrinkage" or soft-thresholding operation. This operation is computationally trivial, allowing for high-speed iterations.
  • Inexact Sub-problem Solving: A critical efficiency gain in FAL comes from solving sub-problems "inexactly." The algorithm moves to the next iteration once a sufficient level of progress is made, rather than wasting cycles on perfect convergence for intermediate steps.

Theoretical Complexity

The authors establish that FAL converges to an optimal solution whenever that solution is unique—a condition met with high probability in compressed sensing. While the theoretical upper bound for reaching an $\epsilon$-optimal solution is $O(1/\epsilon)$ matrix-vector multiplications, numerical experiments suggest a much faster practical convergence rate of $O(\log(1/\epsilon))$.

Experimental Evaluation

Datasets and Setup

The algorithm was benchmarked against leading solvers (including YALL1, SPGL1, NESTA, and SPA) using two primary data sources:

  1. Synthetic Random Instances: Signals featuring a massive 100dB dynamic range, where the largest components are $10^5$ times larger than the smallest. These were measured using partial Discrete Cosine Transform (DCT) matrices.
  2. CaltechTest: A specialized benchmark suite of "hard" compressed sensing problems designed to challenge solvers with extreme dynamic ranges and complex signal structures.

Key Results

  • Superior Speed: In noiseless scenarios, FAL consistently outperformed competitors. It was at least 2 times faster than YALL1 and SPGL1, and approximately 6 times faster than NESTA and SPA.
  • High Precision: FAL reached machine precision (15 digits of accuracy) in roughly 45 main iterations. In contrast, competing solvers often required thousands of iterations to achieve comparable accuracy.
  • Automatic Support Identification: A standout feature of FAL is its ability to correctly identify the "support" (the indices of non-zero components) of the target signal. Unlike other solvers that produce "noisy" solutions requiring manual thresholding, FAL naturally identifies zero components, even in signals with high dynamic ranges.
  • Hard Problem Robustness: On the CaltechTest suite, FAL was the only solver to accurately identify the true signal support across all instances while maintaining top-tier speed (e.g., solving the "Caltech1" instance in 0.6 seconds vs. 7.8 seconds for SPA).

Discussion and Limitations

FAL represents a significant advancement for basis pursuit, particularly in high-precision and high-dynamic-range applications. However, its design is highly specialized for the $\ell_1$-norm. While this specialization drives its elite performance, it makes the algorithm less versatile than general-purpose frameworks like SPA, which can handle a broader range of non-smooth convex constraints.

Additionally, while FAL includes a robust parameter update rule based on signal sparsity, peak performance still benefits from prior knowledge of the signal's characteristics. Future work may focus on further refining the algorithm for high-noise environments (basis pursuit denoising), where the performance gap between FAL and existing solvers is currently less dramatic than in the noiseless case.

Conclusion

The First-order Augmented Lagrangian method provides a powerful, high-speed solution for compressed sensing. By leveraging inexact sub-problem solving and accelerated proximal gradients, it offers a unique combination of theoretical convergence guarantees and practical efficiency, making it an ideal candidate for large-scale signal recovery tasks.

Summary updated

Abstract

We propose a first-order augmented Lagrangian algorithm (FAL) for solving the basis pursuit problem. FAL computes a solution to this problem by inexactly solving a sequence of L1-regularized least squares sub-problems. These sub-problems are solved using an infinite memory proximal gradient algorithm wherein each update reduces to "shrinkage" or constrained "shrinkage". We show that FAL converges to an optimal solution of the basis pursuit problem whenever the solution is unique, which is the case with very high probability for compressed sensing problems. We construct a parameter sequence such that the corresponding FAL iterates are eps-feasible and eps-optimal for all eps>0 within O(log(1/eps)) FAL iterations. Moreover, FAL requires at most O(1/eps) matrix-vector multiplications of the form Ax or A^Ty to compute an eps-feasible, eps-optimal solution. We show that FAL can be easily extended to solve the basis pursuit denoising problem when there is a non-trivial level of noise on the measurements. We report the results of numerical experiments comparing FAL with the state-of-the-art algorithms for both noisy and noiseless compressed sensing problems. A striking property of FAL that we observed in the numerical experiments with randomly generated instances when there is no measurement noise was that FAL always correctly identifies the support of the target signal without any thresholding or post-processing, for moderately small error tolerance values.
BibTeX
@article{aybat2012first,
  author = {Necdet Serhat Aybat and Garud Iyengar},
  title = {{A First-order Augmented Lagrangian Method for Compressed Sensing}},
  journal = {SIAM J. Optim.},
  year = {2012},
  doi = {10.1137/100786721},
}
Figure