zbMATH — the first resource for mathematics

Fast linearized Bregman iteration for compressive sensing and sparse denoising. (English) Zbl 1190.49040
Summary: We propose and analyze an extremely fast, efficient, and simple method for solving the problem:
\[ \min \{\| u\| _1: Au=f,\;u\in\mathbb R^n\}. \]
This method was first described in [J. Darbon and S. Osher, Fast discrete optimizations for sparse approximations and deconvolutions, preprint (2007)], with more details in [W. Yin, S. Osher, D. Goldfarb and J. Darbon, SIAM J. Imaging Sci. 1, No. 1, 143–168, electronic only (2008; Zbl 1203.90153)] and rigorous theory given in [J. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comp., to appear (2008); see also UCLA CAM Report 08-06); Convergence of the linearized Bregman iteration for \(\ell_1\)-norm minimization, UCLA CAM Report, 08-52 (2008)]. The motivation was compressive sensing. Our method introduces an improvement called “kicking” of the very efficient method of [Darbon and Osher (loc. cit.)] and [Yin, Osher, Goldfarb and Darbon (loc. cit.)] 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, No. 2, 460–489 (2005; Zbl 1090.94003)] 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.

49M30 Other numerical methods in calculus of variations (MSC2010)
90-08 Computational methods for problems pertaining to operations research and mathematical programming
65K10 Numerical optimization and variational techniques
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Full Text: DOI Euclid arXiv