{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:54:01Z","timestamp":1776844441898,"version":"3.51.2"},"reference-count":35,"publisher":"American Mathematical Society (AMS)","issue":"267","license":[{"start":{"date-parts":[[2009,10,22]],"date-time":"2009-10-22T00:00:00Z","timestamp":1256169600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Finding a solution of a linear equation\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A u equals f\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mi>u<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>f<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">Au=f<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    with various minimization properties arises from many applications. One such application is compressed sensing, where an efficient and robust-to-noise algorithm to find a minimal\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l 1\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>\n                              \u2113\n                              \n                            <\/mml:mi>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell _1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    norm solution is needed. This means that the algorithm should be tailored for large scale and completely dense matrices\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A\">\n                        <mml:semantics>\n                          <mml:mi>A<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">A<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , while\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A u\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mi>u<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">Au<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A Superscript upper T Baseline u\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mi>A<\/mml:mi>\n                              <mml:mi>T<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mi>u<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">A^Tu<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    can be computed by fast transforms and the solution we seek is sparse. Recently, a simple and fast algorithm based on linearized Bregman iteration was proposed in [28, 32] for this purpose. This paper is to analyze the convergence of linearized Bregman iterations and the minimization properties of their limit. Based on our analysis here, we derive also a new algorithm that is proven to be convergent with a rate. Furthermore, the new algorithm is simple and fast in approximating a minimal\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l 1\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>\n                              \u2113\n                              \n                            <\/mml:mi>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell _1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    norm solution of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A u equals f\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mi>u<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>f<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">Au=f<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    as shown by numerical simulations. Hence, it can be used as another choice of an efficient tool in compressed sensing.\n                  <\/p>","DOI":"10.1090\/s0025-5718-08-02189-3","type":"journal-article","created":{"date-parts":[[2009,4,27]],"date-time":"2009-04-27T13:47:33Z","timestamp":1240840053000},"page":"1515-1536","source":"Crossref","is-referenced-by-count":242,"title":["Linearized Bregman iterations for compressed sensing"],"prefix":"10.1090","volume":"78","author":[{"given":"Jian-Feng","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanley","family":"Osher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zuowei","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2008,10,22]]},"reference":[{"key":"1","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":"https:\/\/id.crossref.org\/issn\/0044-4669","issn-type":"print"},{"key":"2","doi-asserted-by":"crossref","unstructured":"A. M. Bruckstein, D. L. Donoho, and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, 2008, to appear in SIAM Review.","DOI":"10.1137\/060657704"},{"key":"3","doi-asserted-by":"crossref","unstructured":"J.-F. Cai, R. H. Chan, L. Shen, and Z. Shen, Restoration of chopped and nodded images by framelets, SIAM J. Sci. Comput. 30 (2008), no. 3, 1205\u20131227.","DOI":"10.1137\/040615298"},{"key":"4","unstructured":"\\bysame, Simultaneously inpainting in image and transformed domains, 2008, preprint."},{"issue":"2","key":"5","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":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"6","unstructured":"\\bysame, Simultaneous cartoon and texture inpainting, 2008, preprint."},{"key":"7","unstructured":"J.-F. Cai and Z. Shen, Deconvolution: A wavelet frame approach, II, 2008, preprint."},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1088\/0266-5611\/23\/3\/008","article-title":"Sparsity and incoherence in compressive sampling","volume":"23","author":"Cand\u00e8s, Emmanuel","year":"2007","journal-title":"Inverse Problems","ISSN":"https:\/\/id.crossref.org\/issn\/0266-5611","issn-type":"print"},{"key":"9","isbn-type":"print","first-page":"1433","article-title":"Compressive sampling","author":"Cand\u00e8s, Emmanuel J.","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037190227"},{"issue":"2","key":"10","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":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"2","key":"11","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":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"12","key":"12","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":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"13","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":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"4","key":"14","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":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"4","key":"15","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":"https:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"key":"16","unstructured":"J. Darbon and S. Osher, Fast discrete optimization for sparse approximations and deconvolutions, 2007, preprint."},{"issue":"11","key":"17","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":"https:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"},{"issue":"1","key":"18","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":"https:\/\/id.crossref.org\/issn\/1930-8337","issn-type":"print"},{"issue":"4-6","key":"19","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1016\/j.jco.2007.04.002","article-title":"Deterministic constructions of compressed sensing matrices","volume":"23","author":"DeVore, Ronald A.","year":"2007","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"20","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":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"21","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":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"27","key":"22","doi-asserted-by":"publisher","first-page":"9452","DOI":"10.1073\/pnas.0502258102","article-title":"Neighborliness of randomly projected simplices in high dimensions","volume":"102","author":"Donoho, David L.","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA","ISSN":"https:\/\/id.crossref.org\/issn\/0027-8424","issn-type":"print"},{"issue":"9","key":"23","doi-asserted-by":"publisher","first-page":"2558","DOI":"10.1109\/TIT.2002.801410","article-title":"A generalized uncertainty principle and sparse representation in pairs of bases","volume":"48","author":"Elad, Michael","year":"2002","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"6","key":"24","doi-asserted-by":"publisher","first-page":"1579","DOI":"10.1109\/TIT.2003.811926","article-title":"On sparse representation in pairs of bases","volume":"49","author":"Feuer, Arie","year":"2003","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"25","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":"https:\/\/id.crossref.org\/isbn\/3540568506"},{"key":"26","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":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"issue":"2","key":"27","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":"https:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"key":"28","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"},{"issue":"64","key":"29","doi-asserted-by":"publisher","first-page":"4019","DOI":"10.1155\/IMRN.2005.4019","article-title":"Geometric approach to error-correcting codes and reconstruction of signals","author":"Rudelson, Mark","year":"2005","journal-title":"Int. Math. Res. Not.","ISSN":"https:\/\/id.crossref.org\/issn\/1073-7928","issn-type":"print"},{"issue":"3","key":"30","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1109\/TIT.2005.864420","article-title":"Just relax: convex programming methods for identifying sparse signals in noise","volume":"52","author":"Tropp, Joel A.","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"31","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.029"},{"key":"32","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"},{"key":"33","unstructured":"Y. Zhang, A simple proof for recoverability of \u2113\u2081-minimization: Go over or under?, 2005, Rice University CAAM Technical Report TR05-09."},{"key":"34","unstructured":"\\bysame, When is missing data recoverable?, 2006, Rice University CAAM Technical Report TR06-15."},{"issue":"2","key":"35","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1111\/j.1467-9868.2005.00503.x","article-title":"Regularization and variable selection via the elastic net","volume":"67","author":"Zou, Hui","year":"2005","journal-title":"J. R. Stat. Soc. Ser. B Stat. Methodol.","ISSN":"https:\/\/id.crossref.org\/issn\/1369-7412","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2009-78-267\/S0025-5718-08-02189-3\/S0025-5718-08-02189-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-267\/S0025-5718-08-02189-3\/S0025-5718-08-02189-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:08:32Z","timestamp":1776787712000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-267\/S0025-5718-08-02189-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,22]]},"references-count":35,"journal-issue":{"issue":"267","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["S0025-5718-08-02189-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-08-02189-3","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2008,10,22]]}}}