Convergence of the linearized Bregman iteration for -norm minimization

Authors:
Jian-Feng Cai, Stanley Osher and Zuowei Shen

Journal:
Math. Comp. **78** (2009), 2127-2136

MSC (2000):
Primary 65K05, 65F22

DOI:
https://doi.org/10.1090/S0025-5718-09-02242-X

Published electronically:
March 6, 2009

MathSciNet review:
2521281

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: One of the key steps in compressed sensing is to solve the basis pursuit problem . Bregman iteration was very successfully used to solve this problem in [40]. Also, a simple and fast iterative algorithm based on linearized Bregman iteration was proposed in [40], which is described in detail with numerical simulations in [35]. A convergence analysis of the smoothed version of this algorithm was given in [11]. The purpose of this paper is to prove that the linearized Bregman iteration proposed in [40] for the basis pursuit problem indeed converges.

**1.**D. P. Bertsekas,*Constrained optimization and Lagrange multiplier methods*, Computer Science and Applied Mathematics, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1982. MR**690767 (84k:90068)****2.**D. P. Bertsekas,*Nonlinear Programming*, Athena Scientific, Belmont, Massachussets, 1999.**3.**L. M. Brègman,*A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming*, Z. Vyčisl. Mat. i Mat. Fiz.**7**(1967), 620-631. MR**0215617 (35:6457)****4.**M. Burger, E. Resmerita, and L. He,*Error estimation for Bregman iterations and inverse scale space methods in image restoration*, Computing**81**(2007), no. 2-3, 109-135. MR**2354192 (2008k:94002)****5.**J.-F. Cai, E.J. Candès, and Z. Shen,*A singular value thresholding algorithm for matrix completion*, 2008, preprint.**6.**J.-F. Cai, R. Chan, L. Shen, and Z. Shen,*Restoration of chopped and nodded images by framelets*, SIAM J. Sci. Comput.**30**(2008), no. 3, 1205-1227. MR**2398862****7.**J.-F. Cai, R. H. Chan, L. Shen, and Z. Shen,*Convergence analysis of tight framelet approach for missing data recovery*, Adv. Comput. Math. (to appear), 2008.**8.**-,*Simultaneously inpainting in image and transformed domains*, 2008, preprint.**9.**J.-F. Cai, R. H. Chan, and Z. Shen,*A framelet-based image inpainting algorithm*, Appl. Comput. Harmon. Anal.**24**(2008), no. 2, 131-149. MR**2393979****10.**-,*Simultaneous cartoon and texture inpainting*, 2008, preprint.**11.**J.-F. Cai, S. Osher, and Z. Shen,*Linearized Bregman iterations for compressed sensing*, 2008, Math. Comp., to appear; see also UCLA CAM Report (08-06).**12.**-,*Linearized Bregman iterations for frame-based image deblurring*, 2008, preprint.**13.**J.-F. Cai and Z. Shen,*Deconvolution: A wavelet frame approach, II*, 2008, preprint.**14.**E. J. Candès,*Compressive sampling*, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 1433-1452. MR**2275736****15.**E. J. Candès and J. Romberg,*Quantitative robust uncertainty principles and optimally sparse decompositions*, Found. Comput. Math.**6**(2006), no. 2, 227-254. MR**2228740 (2007a:94035)****16.**E. J. Candès, J. Romberg, and T. Tao,*Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information*, IEEE Trans. Inform. Theory**52**(2006), no. 2, 489-509. MR**2236170 (2007e:94020)****17.**E. J. Candes and T. Tao,*Near-optimal signal recovery from random projections: universal encoding strategies?*, IEEE Trans. Inform. Theory**52**(2006), no. 12, 5406-5425. MR**2300700****18.**E. Cetin,*Reconstruction of signals from Fourier transform samples*, Signal Processing,**16**(1989), 129-148. MR**991553 (90c:94008)****19.**-,*An iterative algorithm for signal reconstruction from bispectrum*, IEEE Trans. Signal Proc.,**39**(1991), 2621-2628.**20.**A. Chai and Z. Shen,*Deconvolution: A wavelet frame approach*, Numer. Math.**106**(2007), no. 4, 529-587. MR**2317925 (2008i:42067)****21.**P. L. Combettes and J.-C. Pesquet,*Proximal thresholding algorithm for minimization over orthonormal bases*, SIAM J. Opt.**18**(2007), no. 4, 1351-1376 (electronic). MR**2373305 (2008k:90091)****22.**P. L. Combettes and V. R. Wajs,*Signal recovery by proximal forward-backward splitting*, Multiscale Model. Simul.**4**(2005), no. 4, 1168-1200 (electronic). MR**2203849****23.**J. Darbon and S. Osher,*Fast discrete optimization for sparse approximations and deconvolutions*, 2007, preprint.**24.**I. Daubechies, M. Defrise, and C. De Mol,*An iterative thresholding algorithm for linear inverse problems with a sparsity constraint*, Comm. Pure Appl. Math.**57**(2004), no. 11, 1413-1457. MR**2077704 (2005k:65106)****25.**I. Daubechies, G. Teschke, and L. Vese,*Iteratively solving linear inverse problems under general convex constraints*, Inverse Probl. Imaging**1**(2007), no. 1, 29-46. MR**2262744****26.**D. L. Donoho,*De-noising by soft-thresholding*, IEEE Trans. Inform. Theory**41**(1995), no. 3, 613-627. MR**1331258 (96b:94002)****27.**-,*Compressed sensing*, IEEE Trans. Inform. Theory**52**(2006), no. 4, 1289-1306. MR**2241189 (2007e:94013)****28.**M. Fortin and R. Glowinski,*Augmented Lagrangian methods*, Studies in Mathematics and its Applications, vol. 15, North-Holland Publishing Co., Amsterdam, 1983, Applications to the numerical solution of boundary value problems, Translated from the French by B. Hunt and D. C. Spicer. MR**724072 (85a:49004)****29.**T. Goldstein and S. Osher,*The split Bregman algorithm for l1 regularized problems*, 2008, UCLA CAM Reports (08-29).**30.**M. R. Hestenes,*Multiplier and gradient methods*, J. Optimization Theory Appl.**4**(1969), 303-320. MR**0271809 (42:6690)****31.**J.-B. Hiriart-Urruty and C. Lemaréchal,*Convex analysis and minimization algorithms. I*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305, Springer-Verlag, Berlin, 1993, Fundamentals. MR**1261420 (95m:90001)****32.**P. J. Huber,*Robust regression: asymptotics, conjectures and Monte Carlo*, Ann. Statist.**1**(1973), 799-821. MR**0356373 (50:8843)****33.**K. Ito and K. Kunisch,*The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces*, Math. Programming**46**(1990), no. 3, (Ser. A), 341-360. MR**1054143 (91i:90062)****34.**S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin,*An iterative regularization method for total variation-based image restoration*, Multiscale Model. Simul.**4**(2005), no. 2, 460-489 (electronic). MR**2162864 (2006c:49051)****35.**S. Osher, Y. Mao, B. Dong, and W. Yin,*Fast linearized bregman iteration for compressed sensing and sparse denoising*, 2008, UCLA CAM Reports (08-37).**36.**M. J. D. Powell,*A method for nonlinear constraints in minimization problems*, Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969, pp. 283-298. MR**0272403 (42:7284)****37.**F. Schöpfer, A. K. Louis, and T. Schuster,*Nonlinear iterative methods for linear ill-posed problems in Banach spaces*, Inverse Problems**22**(2006), no. 1, 311-329. MR**2194197 (2006j:65151)****38.**Y. Tsaig and D. L. Donono,*Extensions of compressed sensing*, Signal Processing**86**(2005), 533-548.**39.**W. Yin,*On linearized Bregman iterative algorithms*, private communication.**40.**W. Yin, S. Osher, D. Goldfarb, and J. Darbon,*Bregman iterative algorithms for -minimization with applications to compressed sensing*, SIAM J. Imaging Sci.**1**(2008), no. 1, 143-168.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65K05,
65F22

Retrieve articles in all journals with MSC (2000): 65K05, 65F22

Additional Information

**Jian-Feng Cai**

Affiliation:
Temasek Laboratories, National University of Singapore, 2 Science Drive 2, Singapore 117543

Email:
tslcaij@nus.edu.sg

**Stanley Osher**

Affiliation:
Department of Mathematics, UCLA, 520 Portola Plaza, Los Angeles, California 90095

Email:
sjo@math.ucla.edu

**Zuowei Shen**

Affiliation:
Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543

Email:
matzuows@nus.edu.sg

DOI:
https://doi.org/10.1090/S0025-5718-09-02242-X

Received by editor(s):
July 21, 2008

Received by editor(s) in revised form:
November 6, 2008

Published electronically:
March 6, 2009

Additional Notes:
Research supported by the Wavelets and Information Processing Programme under a grant from DSTA, Singapore.

Research partially supported by ONR grant N000140710810, and by the Department of Defense

Research supported by Grant R-146-000-113-112 from the National University of Singapore.

Article copyright:
© Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.