Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Convergence of the linearized Bregman iteration for $\ell_1$ -norm minimization

Author(s): Jian-Feng Cai; Stanley Osher; Zuowei Shen.
Journal: Math. Comp. 78 (2009), 2127-2136.
MSC (2000): Primary 65K05, 65F22
Posted: March 6, 2009
MathSciNet review: 2521281
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

Abstract: One of the key steps in compressed sensing is to solve the basis pursuit problem $\min_{u\in\mathbb{R}^n}\{\Vert u\Vert _1:Au=f\}$ . 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.

References:

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 $\ell_1$ -minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143-168.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|