Abstract
We propose and analyze an extremely fast, efficient, and simple method for solving the basis pursuit problem. By introducing a "kicking" technique to the Linearized Bregman iteration, we overcome the inherent stagnation phases of the algorithm, enabling rapid sparse recovery and denoising even for signals with extreme dynamic ranges.
Introduction: The Challenge of Sparse Recovery
In compressive sensing and signal processing, the "Basis Pursuit" problem aims to find the simplest (sparsest) signal $u$ that satisfies a set of linear measurements $Au = f$. This is typically formulated as an $\ell_1$-minimization problem. While standard linear programming solvers exist, they often struggle with the massive, dense matrices encountered in modern real-world applications.
The Linearized Bregman iteration has emerged as a popular alternative due to its simplicity—essentially consisting of a gradient step followed by a soft-thresholding (shrinkage) operation. However, the algorithm suffers from a significant drawback: "stagnation."
The Stagnation Problem
During the execution of the standard Linearized Bregman algorithm, the residual often remains constant for many iterations. These "stagnation" phases occur while an internal auxiliary variable slowly accumulates enough "energy" to trigger a change in the signal's sparsity pattern. This leads to wasted computation where the signal $u$ does not change despite ongoing iterations.
As seen in Figure 3, the log of the residual exhibits long plateaus. These plateaus represent the deterministic accumulation phases that the authors set out to eliminate.
Methodology: The "Kicking" Acceleration
The core contribution of this work is the "kicking" scheme. The authors observed that during stagnation, the update direction for the auxiliary variable is constant. This allows for the derivation of an explicit formula to calculate exactly how many steps are required for the next zero-element of the signal to become non-zero.
By predicting the end of these phases, the algorithm can "kick" the variables straight to the boundary of the next "sign-subspace." This effectively collapses hundreds of manual iterations into a single computational step. For noisy data, the algorithm employs the Bregman distance as a stopping criterion, halting once the residual reaches the expected noise level $\sigma$.
Results and Performance
The method was evaluated using synthetic benchmarks, including Gaussian and partial DCT matrices. A key test involved recovering high dynamic range signals where the ratio between the largest and smallest non-zero entries reached $10^{10}$.
In tests with signals like the one shown in Figure 1, the original algorithm required approximately 80 iterations characterized by long plateaus. The "kicked" version reached the same solution in roughly 20 iterations, with the plateaus collapsed into single steps.
The algorithm demonstrated exceptional scalability, handling problems with $n=50,000$ variables in under 20 seconds on standard hardware. Furthermore, it proved robust in extreme denoising scenarios, recovering frequency components at signal-to-noise ratios (SNR) as low as -11 dB and achieving relative errors in the range of $10^{-5}$ to $10^{-6}$.
Conclusion
The accelerated Linearized Bregman iteration provides a powerful tool for sparse recovery. By mathematically predicting and bypassing stagnation phases, the "kicking" scheme offers massive speedups without sacrificing the simplicity or precision of the original algorithm. Future work will explore applications in 2D image denoising and more complex inverse problems involving convolution.
Summary updated