Fast linearized Bregman iteration for compressive sensing and sparse denoising

Bin Dong, Yu Mao, Stanley Osher, Wotao Yin

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.

Log of the residual versus iteration count, illustrating the long plateaus where the algorithm makes no progress.

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}$.

A recovered sparse signal featuring five spikes with varying amplitudes.

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

Abstract

We propose and analyze an extremely fast, efficient, and simple method for solving the problem:
BibTeX
@inproceedings{dong2010fast,
  author = {Bin Dong and Yu Mao and Stanley Osher and Wotao Yin},
  title = {{Fast linearized Bregman iteration for compressive sensing and sparse denoising}},
  booktitle = {Communications},
  year = {2010},
  doi = {10.4310/cms.2010.v8.n1.a6},
}
Figure