One of the key steps in compressed sensing is to solve the basis pursuit problem \n\n \n \n \n min<\/mml:mo>\n \n u<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:munder>\n {<\/mml:mo>\n \u2016<\/mml:mo>\n u<\/mml:mi>\n \n \u2016<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:msub>\n :<\/mml:mo>\n A<\/mml:mi>\n u<\/mml:mi>\n =<\/mml:mo>\n f<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n \\min _{u\\in \\mathbb {R}^n}\\{\\|u\\|_1:Au=f\\}<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>. 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.<\/p>","DOI":"10.1090\/s0025-5718-09-02242-x","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T14:39:02Z","timestamp":1246372742000},"page":"2127-2136","source":"Crossref","is-referenced-by-count":120,"title":["Convergence of the linearized Bregman iteration for \u2113\u2081-norm minimization"],"prefix":"10.1090","volume":"78","author":[{"given":"Jian-Feng","family":"Cai","sequence":"first","affiliation":[]},{"given":"Stanley","family":"Osher","sequence":"additional","affiliation":[]},{"given":"Zuowei","family":"Shen","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2009,3,6]]},"reference":[{"key":"1","series-title":"Computer Science and Applied Mathematics","isbn-type":"print","volume-title":"Constrained optimization and Lagrange multiplier methods","author":"Bertsekas, Dimitri P.","year":"1982","ISBN":"http:\/\/id.crossref.org\/isbn\/0120934809"},{"key":"2","unstructured":"D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, Massachussets, 1999."},{"key":"3","first-page":"620","article-title":"A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming","volume":"7","author":"Br\u00e8gman, L. M.","year":"1967","journal-title":"\\v{Z}. Vy\\v{c}isl. Mat i Mat. Fiz.","ISSN":"http:\/\/id.crossref.org\/issn\/0044-4669","issn-type":"print"},{"issue":"2-3","key":"4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00607-007-0245-z","article-title":"Error estimation for Bregman iterations and inverse scale space methods in image restoration","volume":"81","author":"Burger, M.","year":"2007","journal-title":"Computing","ISSN":"http:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"5","unstructured":"J.-F. Cai, E.J. Cand\u00e8s, and Z. Shen, A singular value thresholding algorithm for matrix completion, 2008, preprint."},{"issue":"3","key":"6","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/040615298","article-title":"Restoration of chopped and nodded images by framelets","volume":"30","author":"Cai, Jian-Feng","year":"2008","journal-title":"SIAM J. Sci. Comput.","ISSN":"http:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1007\/s10444-008-9084-5"},{"key":"8","unstructured":"\\bysame, Simultaneously inpainting in image and transformed domains, 2008, preprint."},{"issue":"2","key":"9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.acha.2007.10.002","article-title":"A framelet-based image inpainting algorithm","volume":"24","author":"Cai, Jian-Feng","year":"2008","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"10","unstructured":"\\bysame, Simultaneous cartoon and texture inpainting, 2008, preprint."},{"key":"11","unstructured":"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)."},{"key":"12","unstructured":"\\bysame, Linearized Bregman iterations for frame-based image deblurring, 2008, preprint."},{"key":"13","unstructured":"J.-F. Cai and Z. Shen, Deconvolution: A wavelet frame approach, II, 2008, preprint."},{"key":"14","first-page":"1433","article-title":"Compressive sampling","author":"Cand\u00e8s, Emmanuel J.","year":"2006"},{"issue":"2","key":"15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10208-004-0162-x","article-title":"Quantitative robust uncertainty principles and optimally sparse decompositions","volume":"6","author":"Cand\u00e8s, Emmanuel J.","year":"2006","journal-title":"Found. Comput. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","article-title":"Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information","volume":"52","author":"Cand\u00e8s, Emmanuel J.","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"12","key":"17","doi-asserted-by":"publisher","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","article-title":"Near-optimal signal recovery from random projections: universal encoding strategies?","volume":"52","author":"Candes, Emmanuel J.","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0165-1684(89)90092-3","article-title":"Reconstruction of signals from Fourier transform samples","volume":"16","author":"\u00c7etin, A. Enis","year":"1989","journal-title":"Signal Process.","ISSN":"http:\/\/id.crossref.org\/issn\/0165-1684","issn-type":"print"},{"key":"19","doi-asserted-by":"crossref","unstructured":"\\bysame, An iterative algorithm for signal reconstruction from bispectrum, IEEE Trans. Signal Proc., 39 (1991), 2621\u20132628.","DOI":"10.1109\/78.107412"},{"issue":"4","key":"20","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00211-007-0075-0","article-title":"Deconvolution: a wavelet frame approach","volume":"106","author":"Chai, Anwei","year":"2007","journal-title":"Numer. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1137\/060669498","article-title":"Proximal thresholding algorithm for minimization over orthonormal bases","volume":"18","author":"Combettes, Patrick L.","year":"2007","journal-title":"SIAM J. Optim.","ISSN":"http:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"4","key":"22","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1137\/050626090","article-title":"Signal recovery by proximal forward-backward splitting","volume":"4","author":"Combettes, Patrick L.","year":"2005","journal-title":"Multiscale Model. Simul.","ISSN":"http:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"key":"23","unstructured":"J. Darbon and S. Osher, Fast discrete optimization for sparse approximations and deconvolutions, 2007, preprint."},{"issue":"11","key":"24","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1002\/cpa.20042","article-title":"An iterative thresholding algorithm for linear inverse problems with a sparsity constraint","volume":"57","author":"Daubechies, Ingrid","year":"2004","journal-title":"Comm. Pure Appl. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.3934\/ipi.2007.1.29","article-title":"Iteratively solving linear inverse problems under general convex constraints","volume":"1","author":"Daubechies, Ingrid","year":"2007","journal-title":"Inverse Probl. Imaging","ISSN":"http:\/\/id.crossref.org\/issn\/1930-8337","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1109\/18.382009","article-title":"De-noising by soft-thresholding","volume":"41","author":"Donoho, David L.","year":"1995","journal-title":"IEEE Trans. Inform. Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"27","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","article-title":"Compressed sensing","volume":"52","author":"Donoho, David L.","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"28","series-title":"Studies in Mathematics and its Applications","isbn-type":"print","volume-title":"Augmented Lagrangian methods","volume":"15","author":"Fortin, Michel","year":"1983","ISBN":"http:\/\/id.crossref.org\/isbn\/0444866809"},{"key":"29","unstructured":"T. Goldstein and S. Osher, The split Bregman algorithm for l1 regularized problems, 2008, UCLA CAM Reports (08-29)."},{"key":"30","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF00927673","article-title":"Multiplier and gradient methods","volume":"4","author":"Hestenes, Magnus R.","year":"1969","journal-title":"J. Optim. Theory Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"key":"31","series-title":"Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","volume-title":"Convex analysis and minimization algorithms. I","volume":"305","author":"Hiriart-Urruty, Jean-Baptiste","year":"1993","ISBN":"http:\/\/id.crossref.org\/isbn\/3540568506"},{"key":"32","first-page":"799","article-title":"Robust regression: asymptotics, conjectures and Monte Carlo","volume":"1","author":"Huber, Peter J.","year":"1973","journal-title":"Ann. Statist.","ISSN":"http:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"issue":"3","key":"33","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01585750","article-title":"The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces","volume":"46","author":"Ito, K.","year":"1990","journal-title":"Math. Programming","ISSN":"http:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"2","key":"34","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1137\/040605412","article-title":"An iterative regularization method for total variation-based image restoration","volume":"4","author":"Osher, Stanley","year":"2005","journal-title":"Multiscale Model. Simul.","ISSN":"http:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"key":"35","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.21236\/ADA497867"},{"key":"36","first-page":"283","article-title":"A method for nonlinear constraints in minimization problems","author":"Powell, M. J. D.","year":"1969"},{"issue":"1","key":"37","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1088\/0266-5611\/22\/1\/017","article-title":"Nonlinear iterative methods for linear ill-posed problems in Banach spaces","volume":"22","author":"Sch\u00f6pfer, F.","year":"2006","journal-title":"Inverse Problems","ISSN":"http:\/\/id.crossref.org\/issn\/0266-5611","issn-type":"print"},{"key":"38","doi-asserted-by":"crossref","unstructured":"Y. Tsaig and D. L. Donono, Extensions of compressed sensing, Signal Processing 86 (2005), 533\u2013548.","DOI":"10.1016\/j.sigpro.2005.05.028"},{"key":"39","unstructured":"W. Yin, On linearized Bregman iterative algorithms, private communication."},{"key":"40","doi-asserted-by":"crossref","unstructured":"W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for \u2113\u2081-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143\u2013168.","DOI":"10.1137\/070703983"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2009-78-268\/S0025-5718-09-02242-X\/S0025-5718-09-02242-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-268\/S0025-5718-09-02242-X\/S0025-5718-09-02242-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T03:40:32Z","timestamp":1627616432000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-268\/S0025-5718-09-02242-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,6]]},"references-count":40,"journal-issue":{"issue":"268","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["S0025-5718-09-02242-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-09-02242-x","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,6]]}}}