Abstract
In the field of compressed sensing, recovering sparse signals from underdetermined linear systems is a fundamental challenge. This paper presents PARNES, an algorithm designed to solve the Basis Pursuit Denoising (BPDN) problem with high precision and speed. PARNES leverages NESTA-LASSO, a modified version of Nesterov’s accelerated proximal gradient method that incorporates a provably optimal prox-center updating strategy. We demonstrate that under the Restricted Isometry Property (RIP), NESTA-LASSO achieves local linear convergence. By integrating this into a Pareto root-finding framework, PARNES provides a robust solver that matches or exceeds the performance of current state-of-the-art tools like SPGL1 and FISTA, particularly in high-dynamic-range scenarios.
Introduction
The recovery of a sparse signal $x$ from a limited set of noisy measurements $b = Ax + z$ is central to modern signal processing. This task is typically framed as one of two optimization problems: the LASSO problem, which minimizes the least-squares error subject to an $\ell_1$-norm constraint, or the Basis Pursuit Denoising (BPDN) problem, which minimizes the $\ell_1$-norm subject to a maximum allowable error $\sigma$.
While first-order methods are preferred for large-scale data due to their low memory requirements, they often suffer from sublinear convergence rates, requiring many iterations to achieve high-precision results. This paper introduces a method to accelerate these first-order solvers by strategically "restarting" the optimization process to adapt to the local geometry of the problem.
The NESTA-LASSO Framework
The core of our approach is NESTA-LASSO. Standard accelerated gradient methods, such as those proposed by Nesterov, typically achieve an iteration complexity of $O(1/\sqrt{\epsilon})$ to reach an accuracy of $\epsilon$. These methods rely on a fixed "prox-center" or reference point throughout the execution.
We introduce a Prox-Center Update modification. By restarting the algorithm every $K$ iterations and resetting the prox-center to the current best estimate of the solution, we transform the convergence behavior. We prove that if the sensing matrix $A$ satisfies the Restricted Isometry Property (RIP) and the solution is sufficiently sparse, NESTA-LASSO is guaranteed to be locally linearly convergent. This means that once the algorithm nears the optimal solution, the error begins to decrease exponentially rather than polynomially.
Optimal Restart Strategy
A key contribution of this work is the derivation of the optimal restart interval. We found that the number of iterations $K$ between prox-center updates should be chosen carefully; our analysis suggests an optimal value $K_{opt}$ that facilitates the transition to linear convergence as the algorithm identifies the signal's support.
The PARNES Algorithm
To solve the BPDN problem, we utilize the Pareto root-finding method. This approach treats the BPDN problem as finding the root of a non-linear equation that describes the trade-off between the $\ell_1$-norm of the signal and the residual error (the Pareto curve).
PARNES (Pareto-based NESTA) uses NESTA-LASSO as the inner solver to evaluate points along this curve. By combining the rapid local convergence of NESTA-LASSO with the global root-finding efficiency of the Pareto framework, PARNES becomes a highly effective tool for high-precision sparse recovery.
Numerical Results
We evaluated PARNES against several benchmarks, including synthetic sparse signals and real-world data from the SPARCO toolbox.
- High Dynamic Range Performance: In tests involving signals with a 100 dB dynamic range—where low-magnitude components are often lost by standard solvers—PARNES achieved a relative accuracy of $6.93 \times 10^{-4}$ using only 632 function calls. In contrast, the baseline NESTA algorithm required over 15,000 calls to achieve a significantly lower accuracy of $4.12 \times 10^{-3}$.
- Efficiency vs. State-of-the-Art: When compared to SPGL1 and FISTA, PARNES consistently required fewer matrix-vector multiplications to reach the same convergence criteria, particularly on approximately sparse signals generated from Haar wavelet coefficients.
Discussion and Limitations
While PARNES shows significant empirical and theoretical promise, its linear convergence guarantee currently relies on the Restricted Isometry Property. In practice, RIP can be difficult to verify for arbitrary matrices, though it is known to hold for many random ensembles. Furthermore, while the algorithm performs excellently on approximately sparse data, our current formal proof of linear convergence is restricted to exactly sparse signals. Extending this theoretical framework to the approximately sparse case remains a primary objective for future work.
Conclusion
PARNES represents a significant step forward in first-order optimization for compressed sensing. By introducing a simple yet mathematically rigorous prox-center update to Nesterov's method, we achieve the high-precision convergence typically associated with second-order methods while maintaining the scalability of first-order approaches.
Summary updated