Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising

Stanley J. Osher, Yu Mao, Bin Dong, Wotao Yin

Introduction

In compressive sensing, the goal is to find the sparsest signal $u$ that explains observations $f$ through the system $Au = f$. This is typically framed as the Basis Pursuit problem, minimizing the $L_1$ norm of $u$ subject to linear constraints. While standard linear programming solvers exist, they often fail to scale to the massive, dense matrices encountered in modern signal processing. The Linearized Bregman (LB) algorithm was proposed as a simple, memory-efficient alternative, but it suffers from a significant drawback: stagnation.

The Stagnation Challenge

When the regularization parameter in LB is large—which is necessary for high accuracy—the algorithm enters long periods where the residual barely changes. It spends thousands of iterations in this state before suddenly "discovering" a new spike in the signal. This paper introduces an accelerated version that identifies and analytically "skips" these periods of stagnation.

Sparse signal recovery (left) and the corresponding log residual (right) showing characteristic stagnation plateaus.

As illustrated in the figure above, the residual plot exhibits long plateaus where the error remains nearly constant before a sharp drop. The authors realized these plateaus are not signs of failure, but predictable linear accumulation phases.

Methods: The "Kicking" Modification

The core innovation is the "Kicking" mechanism. By monitoring the signal $u$, the algorithm detects when the set of non-zero indices (the support) remains unchanged. During these phases, the auxiliary variable $v$ evolves linearly, allowing the authors to derive a formula that predicts exactly how many iterations are required for the next zero-element to cross the threshold and become non-zero.

Algorithm 2: The Linearized Bregman Iteration incorporating the Kicking mechanism to skip stagnation phases.

Instead of waiting for those iterations to pass, the algorithm "kicks" the variable $v$ directly to that future state in a single step. This turns a process that might take 10,000 slow steps into a single, mathematically justified jump.

Key Results and Performance

The accelerated algorithm demonstrates exceptional speed and robustness across various benchmarks, including Gaussian and partial DCT matrices:

  • Efficiency: On large partial DCT matrices ($21640 \times 50000$), the algorithm reaches high-precision solutions in approximately 8.5 seconds on standard 2008-era hardware.
  • High Dynamic Range: The kicking scheme allows the recovery of signals where spike magnitudes vary by a factor of $10^{10}$, a scenario where most standard algorithms struggle due to numerical precision issues.
  • Robustness to Noise: The method remains effective in denoising even when the Signal-to-Noise Ratio (SNR) is negative, meaning the noise is stronger than the underlying signal.

Conclusion

By recognizing that stagnation plateaus are predictable, the authors have transformed the Linearized Bregman Iteration into a high-performance tool for sparse optimization. Its simplicity and scalability make it ideal for large-scale compressive sensing and real-time signal processing where explicit matrix storage is impossible.

Summary updated

BibTeX
@inproceedings{osher2010fast,
  author = {Stanley J. Osher and Yu Mao and Bin Dong 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