{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:35:36Z","timestamp":1776800136462,"version":"3.51.2"},"reference-count":29,"publisher":"American Mathematical Society (AMS)","issue":"297","license":[{"start":{"date-parts":[[2016,5,15]],"date-time":"2016-05-15T00:00:00Z","timestamp":1463270400000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We provide a simple analysis of the Douglas-Rachford splitting algorithm in the context of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l Superscript 1\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>\n                              \u2113\n                              \n                            <\/mml:mi>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell ^1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    minimization with linear constraints, and quantify the asymptotic linear convergence rate in terms of principal angles between relevant vector spaces. In the compressed sensing setting, we show how to bound this rate in terms of the restricted isometry constant. More general iterative schemes obtained by\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l squared\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>\n                              \u2113\n                              \n                            <\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell ^2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -regularization and over-relaxation including the dual split Bregman method are also treated, which answers the question of how to choose the relaxation and soft-thresholding parameters to accelerate the asymptotic convergence rate. We make no attempt at characterizing the transient regime preceding the onset of linear convergence.\n                  <\/p>","DOI":"10.1090\/mcom\/2965","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T09:42:45Z","timestamp":1431682965000},"page":"209-238","source":"Crossref","is-referenced-by-count":29,"title":["Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit"],"prefix":"10.1090","volume":"85","author":[{"given":"Laurent","family":"Demanet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiangxiong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,5,15]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"F. J. Arag\u00f3n Artacho and J. M. Borwein, Global convergence of a non-convex Douglas-Rachford iteration, Journal of Global Optimization, pages 1\u201317, 2012.","DOI":"10.1007\/s10898-012-9958-4"},{"issue":"7","key":"2","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1364\/JOSAA.19.001334","article-title":"Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization","volume":"19","author":"Bauschke, Heinz H.","year":"2002","journal-title":"J. Opt. Soc. Amer. A","ISSN":"https:\/\/id.crossref.org\/issn\/1084-7529","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"579","DOI":"10.2307\/2005662","article-title":"Numerical methods for computing angles between linear subspaces","volume":"27","author":"Bj\u00f6rck, \u0226ke","year":"1973","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1137\/05064182X","article-title":"Fast discrete curvelet transforms","volume":"5","author":"Cand\u00e8s, Emmanuel","year":"2006","journal-title":"Multiscale Model. Simul.","ISSN":"https:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"issue":"12","key":"5","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","article-title":"Decoding by linear programming","volume":"51","author":"Candes, Emmanuel J.","year":"2005","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","article-title":"A first-order primal-dual algorithm for convex problems with applications to imaging","volume":"40","author":"Chambolle, Antonin","year":"2011","journal-title":"J. Math. Imaging Vision","ISSN":"https:\/\/id.crossref.org\/issn\/0924-9907","issn-type":"print"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/S1064827596304010","article-title":"Atomic decomposition by basis pursuit","volume":"20","author":"Chen, Scott Shaobing","year":"1998","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"5-6","key":"8","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1080\/02331930412331327157","article-title":"Solving monotone inclusions via compositions of nonexpansive averaged operators","volume":"53","author":"Combettes, Patrick L.","year":"2004","journal-title":"Optimization","ISSN":"https:\/\/id.crossref.org\/issn\/0233-1934","issn-type":"print"},{"issue":"3-4","key":"9","first-page":"727","article-title":"Iterative construction of the resolvent of a sum of maximal monotone operators","volume":"16","author":"Combettes, Patrick L.","year":"2009","journal-title":"J. Convex Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0944-6532","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF01581204","article-title":"On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators","volume":"55","author":"Eckstein, Jonathan","year":"1992","journal-title":"Math. Programming","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"11","unstructured":"E. Esser, Applications of Lagrangian based alternating direction methods and connections to split Bregman, CAM Report 09-31, UCLA, 2009."},{"issue":"6","key":"12","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1109\/TIT.2004.828141","article-title":"On sparse representations in arbitrary redundant bases","volume":"50","author":"Fuchs, Jean-Jacques","year":"2004","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"13","unstructured":"D. Gabay, Applications of the method of multipliers to variational inequalities, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, edited by M. Fortin and R. Glowinski, 1983."},{"key":"14","doi-asserted-by":"crossref","unstructured":"D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl. 2 (1976), no. 1, 17\u201340.","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1051\/m2an\/197509R200411","article-title":"Sur l\u2019approximation, par \u00e9l\u00e9ments finis d\u2019ordre un, et la r\u00e9solution, par p\u00e9nalisation-dualit\u00e9, d\u2019une classe de probl\u00e8mes de Dirichlet non lin\u00e9aires","volume":"9","author":"Glowinski, R.","year":"1975","journal-title":"Rev. Fran\\c{c}aise Automat. Informat. Recherche Op\\'{e}rationnelle S\\'{e}r. Rouge Anal. Num\\'{e}r.","ISSN":"https:\/\/id.crossref.org\/issn\/0397-9342","issn-type":"print"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/080725891","article-title":"The split Bregman method for \ud835\udc3f1-regularized problems","volume":"2","author":"Goldstein, Tom","year":"2009","journal-title":"SIAM J. Imaging Sci."},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1137\/070698920","article-title":"Fixed-point continuation for \ud835\udc59\u2081-minimization: methodology and convergence","volume":"19","author":"Hale, Elaine T.","year":"2008","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"18","unstructured":"D. Han and X. Yuan, Convergence analysis of the peaceman-rachford splitting method for nonsmooth convex optimization, 2012."},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1137\/110836936","article-title":"On the \ud835\udc42(1\/\ud835\udc5b) convergence rate of the Douglas-Rachford alternating direction method","volume":"50","author":"He, Bingsheng","year":"2012","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"20","doi-asserted-by":"crossref","unstructured":"F. J. Herrmann and G. Hennenfent, Non-parametric seismic data recovery with curvelet frames, Geophysical Journal International 173 (2008), no. 1, 233\u2013248.","DOI":"10.1111\/j.1365-246X.2007.03698.x"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"2397","DOI":"10.1137\/120902653","article-title":"Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems","volume":"23","author":"Hesse, Robert","year":"2013","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"2","key":"22","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1137\/120863290","article-title":"Augmented \u2113\u2081 and nuclear-norm models with a globally linearly convergent algorithm","volume":"6","author":"Lai, Ming-Jun","year":"2013","journal-title":"SIAM J. Imaging Sci."},{"issue":"3","key":"23","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1137\/S1052623401387623","article-title":"Active sets, nonsmoothness, and sensitivity","volume":"13","author":"Lewis, A. S.","year":"2002","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"6","key":"24","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/0716071","article-title":"Splitting algorithms for the sum of two nonlinear operators","volume":"16","author":"Lions, P.-L.","year":"1979","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"25","doi-asserted-by":"crossref","unstructured":"S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, In Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, SSVM \u201909, (2009), 464\u2013476, Springer-Verlag, Berlin, Heidelberg.","DOI":"10.1007\/978-3-642-02256-2_39"},{"issue":"284","key":"26","doi-asserted-by":"publisher","first-page":"2061","DOI":"10.1090\/S0025-5718-2013-02700-7","article-title":"A dual split Bregman method for fast \u2113\u00b9 minimization","volume":"82","author":"Yang, Yi","year":"2013","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"27","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1137\/090760350","article-title":"Analysis and generalizations of the linearized Bregman model","volume":"3","author":"Yin, Wotao","year":"2010","journal-title":"SIAM J. Imaging Sci."},{"issue":"2-3","key":"28","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1007\/s10915-012-9616-5","article-title":"Error forgetting of Bregman iteration","volume":"54","author":"Yin, Wotao","year":"2013","journal-title":"J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-7474","issn-type":"print"},{"key":"29","unstructured":"H. Zhang, W. Yin, and L. Cheng, Necessary and sufficient conditions of solution uniqueness in \u21131 minimization, Technical report, Rice University CAAM, 2012."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02965-2\/S0025-5718-2015-02965-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02965-2\/S0025-5718-2015-02965-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:38:08Z","timestamp":1776796688000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02965-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,15]]},"references-count":29,"journal-issue":{"issue":"297","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0025-5718-2015-02965-2"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2965","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":[[2015,5,15]]}}}