Source-linked AI summary
Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising
Stanley Osher, Yu Mao, Bin Dong, Wotao Yin
TL;DR
The paper addresses fast solution of ℓ1 basis pursuit for compressive sensing and denoising of sparse, potentially undersampled signals. It improves linearized Bregman iteration with “kicking” and analyzes its convergence. The authors report efficient approach to sparse solutions and remarkable denoising properties for undersampled sparse signals.
Problem
Basis pursuit requires efficiently finding sparse solutions to underdetermined systems, while denoising methods for sparse signals, especially undersampled ones, need further development.
Method
The paper analyzes linearized Bregman iterative regularization, adds a “kicking” acceleration scheme, and applies Bregman iteration to sparse-signal denoising.
Results
The method approaches sparse solutions efficiently and has remarkable denoising properties for undersampled sparse signals.
Takeaways & Limitations
Linearized Bregman iteration is presented as a competitive method for compressive sensing and as applicable to undersampled sparse-signal denoising.
Takeaways & Limitations
The Bregman distance is not a distance in the usual sense, and the analysis assumes properties such as coercivity for existence of solutions.
Abstract
from arXiv · showhide
We propose and analyze an extremely fast, efficient, and simple method for solving the problem:min{parallel to u parallel to(1) : Au = f, u is an element of R-n}.This method was first described in [J. Darbon and S. Osher, preprint, 2007], with more details in [W. Yin, S. Osher, D. Goldfarb and J. Darbon, SIAM J. Imaging Sciences, 1(1), 143-168, 2008] and rigorous theory given in [J. Cai, S. Osher and Z. Shen, Math. Comp., to appear, 2008, see also UCLA CAM Report 08-06] and [J. Cai, S. Osher and Z. Shen, UCLA CAM Report, 08-52, 2008]. The motivation was compressive sensing, which now has a vast and exciting history, which seems to have started with Candes, et. al. [E. Candes, J. Romberg and T. Tao, 52(2), 489-509, 2006] and Donoho, [D. L. Donoho, IEEE Trans. Inform. Theory, 52, 1289-1306, 2006]. See [W. Yin, S. Osher, D. Goldfarb and J. Darbon, SIAM J. Imaging Sciences 1(1), 143-168, 2008] and [J. Cai, S. Osher and Z. Shen, Math. Comp., to appear, 2008, see also UCLA CAM Report, 08-06] and [J. Cai, S. Osher and Z. Shen, UCLA CAM Report, 08-52, 2008] for a large set of references. Our method introduces an improvement called "kicking" of the very efficient method of [J. Darbon and S. Osher, preprint, 2007] and [W. Yin, S. Osher, D. Goldfarb and J. Darbon, SIAM J. Imaging Sciences, 1(1), 143-168, 2008] and also applies it to the problem of denoising of undersampled signals. The use of Bregman iteration for denoising of images began in [S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, Multiscale Model. Simul, 4(2), 460-489, 2005] and led to improved results for total variation based methods. Here we apply it to denoise signals, especially essentially sparse signals, which might even be undersampled.
1 Introduction
The paper targets basis pursuit for compressive sensing and develops a fast linearized Bregman approach, including “kicking” and denoising of undersampled sparse signals.
- Basis pursuit seeks u ∈ R^n satisfying Au = f while minimizing its ℓ1 norm.
- The paper assumes A A^T is invertible and uses coercivity of J to ensure existence, while strict or strong convexity yields uniqueness.
- Compressive sensing can recover the sparsest solution satisfying Au = f under appropriate circumstances.
- Large-scale dense sensing matrices and sparse solutions make conventional linear programming solvers poorly tailored to the problem.
- The paper improves linearized Bregman iteration with “kicking,” which is intended to accelerate an already fast and accurate method.
- Bregman iterative regularization is applied to denoise sparse signals, including signals that are undersampled.
2 Bregman and Linearized Bregman Iterative Algorithms
This section introduces Bregman and linearized Bregman iterations for constrained optimization, specializes them to ℓ1 regularization, and reviews convergence and denoising-related properties.
- Bregman iteration solves the constrained problem through a sequence of unconstrained optimization problems.
- For J(u)=∥u∥1, Bregman iteration can reach a solution of the constrained problem in finitely many steps.
- Linearized Bregman iteration replaces unavailable explicit solvers with iterative updates and, for J(u)=µ∥u∥1, reduces to a two-line algorithm.
- The ℓ1-specialized update uses an auxiliary variable and soft thresholding.
- Prior analyses establish convergence of the iterates under step-size conditions and convergence to the unique solution in the strictly convex formulation.
- The Bregman distance need not be a usual distance, but it measures closeness and decreases toward a noise-free approximation while the residual remains above the noise level.
- The residual condition ∥A u^k−f∥ > σ supplies a stopping criterion for denoising.
3 Convergence
Linearized Bregman convergence is monotone and becomes exponential while the active support and signs remain fixed, but proceeds through stagnation phases as new spikes appear.
- If the iterates converge, their limit satisfies Au∞ = f.
- The residual norm is nonincreasing under the step-size condition δ < 2/∥AAT∥.
- When the support subspace remains fixed, uk converges to the least-residual point in that subspace at an exponential rate.
- With relatively large µ, signs typically remain unchanged for long intervals, producing rapid within-subspace convergence followed by stagnation.
- Each newly appearing spike can trigger another rapid convergence phase, while larger µ lengthens the intervening stagnation.
4 Fast Implementation
The kicking modification accelerates linearized Bregman iteration by jumping across stagnation intervals while preserving the original convergence theory.
- The basic algorithm solves the ℓ1 problems through iterative updates involving matrix multiplication and shrinkage.
- During stagnation, the increment of v is fixed, allowing u and v to be calculated explicitly.
- Kicking detects an unchanged iterate and advances u to the stagnation’s critical point.
- The kicked output sequence is a subsequence of the original sequence, so the original convergence conclusions remain valid.
- Figure 2 shows the original stagnation intervals collapsing to single steps, dramatically reducing total computation.
5 Numerical Results
The numerical experiments evaluate the algorithm on basis pursuit, noisy recovery, high-dynamic-range signals, and undersampled sinusoidal signals. Results include efficient recovery under structured measurement matrices, residual convergence, and noise-dependent reconstruction behavior.
- 5.1 Efficiency: The experiments test basis pursuit with underdetermined Gaussian and partial DCT matrices for sparse signals.The matrix dimensions follow sparsity-dependent compressed-sensing scalings, and experiments use signals with 0.05n or 0.02n nonzeros.
- 5.1 Efficiency: Partial DCT matrices permit much larger tests because matrix-vector products use fast DCT and inverse-DCT transforms.The matrices are implicitly stored rather than formed densely.
- 5.2 Robustness to Noise: The noisy-recovery experiments vary noise level, matrix size, and sparsity, using Gaussian or partial DCT measurements.The stopping rule triggers when residual standard deviation falls below σ or iterations exceed 1000.
- 5.3 Recovery of Signal with High Dynamical Range: For high-dynamic-range signals, the algorithm reaches a 10^-11 residual in fewer than 300 iterations without noise.The experiments use n=4000, 0.02n nonzeros, and µ=10^10.
- 5.3 Recovery of Signal with High Dynamical Range: With noise, smaller signal magnitudes are recovered well when measurements contain less noise, while sinusoidal experiments reconstruct frequencies reliably from random samples.Figure 3 reports SNR=23.1084, relative error=0.020764, and 102 iterations for one partial-DCT case.
6 Conclusion
The paper concludes that linearized Bregman algorithms provide a competitive and efficient approach to compressed sensing, with kicking accelerating convergence even for large µ. The process also shows denoising properties for undersampled sparse signals and may apply to broader problem classes.
- 6 Conclusion: Kicking accelerates the linearized Bregman algorithm even when µ is extremely large, allowing sparse solutions to be approached efficiently.The conclusion emphasizes both algorithmic simplicity and the special structure of the iteration.
- 6 Conclusion: The process has denoising properties for undersampled sparse signals.The paper identifies this as an area for further work.
- 6 Conclusion: The results suggest that linearized Bregman algorithms can solve a broad category of problems.The authors mention possible extensions to very underdetermined inverse problems in partial differential equations.