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:
- 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.
- 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