Fast linearized Bregman iteration for compressive sensing and sparse denoising.

*(English)*Zbl 1190.49040Summary: 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.

\[ \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.

##### MSC:

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 |