{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:35:35Z","timestamp":1776800135307,"version":"3.51.2"},"reference-count":36,"publisher":"American Mathematical Society (AMS)","issue":"297","license":[{"start":{"date-parts":[[2016,7,29]],"date-time":"2016-07-29T00:00:00Z","timestamp":1469750400000},"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                    In this paper we analyze the connection between the recently proposed adaptive inverse scale space methods for basis pursuit and the well-known orthogonal matching pursuit method for the recovery of sparse solutions to underdetermined linear systems. Furthermore, we propose a new greedy sparse recovery method, which approximates\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 more closely. A variant of our new approach can increase the support of the current iterate by many indices at once, resulting in an extremely efficient algorithm. Our new method has the advantage that there is a simple criterion to determine a posteriori if an\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                    minimizer was found. Numerical comparisons with orthogonal matching pursuit, weak orthogonal matching pursuit, hard thresholding pursuit and compressive sampling matching pursuit underline that our methods indeed inherit some advantageous properties from the inverse scale space flow.\n                  <\/p>","DOI":"10.1090\/mcom\/3004","type":"journal-article","created":{"date-parts":[[2015,7,29]],"date-time":"2015-07-29T09:08:32Z","timestamp":1438160912000},"page":"179-208","source":"Crossref","is-referenced-by-count":4,"title":["Fast sparse reconstruction: Greedy inverse scale space flows"],"prefix":"10.1090","volume":"85","author":[{"given":"Michael","family":"Moeller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoqun","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,7,29]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1109\/TSP.2009.2036064","article-title":"A subband adaptive iterative shrinkage\/thresholding algorithm","volume":"58","author":"Bayram, \u0130lker","year":"2010","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","article-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","volume":"2","author":"Beck, Amir","year":"2009","journal-title":"SIAM J. Imaging Sci."},{"key":"3","unstructured":"S. Becker, CoSaMP and OMP for sparse recovery, Matlab Central File Exchange, 08\/01\/11 (Updated 04\/20\/12)."},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.acha.2009.04.002","article-title":"Iterative hard thresholding for compressed sensing","volume":"27","author":"Blumensath, Thomas","year":"2009","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4310\/cms.2006.v4.n1.a7","article-title":"Nonlinear inverse scale space methods","volume":"4","author":"Burger, Martin","year":"2006","journal-title":"Commun. Math. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/1539-6746","issn-type":"print"},{"issue":"281","key":"6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1090\/S0025-5718-2012-02599-3","article-title":"An adaptive inverse scale space method for compressed sensing","volume":"82","author":"Burger, Martin","year":"2013","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"268","key":"7","doi-asserted-by":"publisher","first-page":"2127","DOI":"10.1090\/S0025-5718-09-02242-X","article-title":"Convergence of the linearized Bregman iteration for \u2113\u2081-norm minimization","volume":"78","author":"Cai, Jian-Feng","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"267","key":"8","doi-asserted-by":"publisher","first-page":"1515","DOI":"10.1090\/S0025-5718-08-02189-3","article-title":"Linearized Bregman iterations for compressed sensing","volume":"78","author":"Cai, Jian-Feng","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"12","key":"9","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":"12","key":"10","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":"5","key":"11","doi-asserted-by":"publisher","first-page":"2230","DOI":"10.1109\/TIT.2009.2016006","article-title":"Subspace pursuit for compressive sensing signal reconstruction","volume":"55","author":"Dai, Wei","year":"2009","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"12","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":"5","key":"13","doi-asserted-by":"publisher","first-page":"2197","DOI":"10.1073\/pnas.0437847100","article-title":"Optimally sparse representation in general (nonorthogonal) dictionaries via \ud835\udc59\u00b9 minimization","volume":"100","author":"Donoho, David L.","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA","ISSN":"https:\/\/id.crossref.org\/issn\/0027-8424","issn-type":"print"},{"key":"14","doi-asserted-by":"crossref","unstructured":"D.L. Donoho, A. Maleki, and A. Montanari, Message passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences 106 (2009), no. 45, 18914\u201318919.","DOI":"10.1073\/pnas.0909892106"},{"key":"15","unstructured":"E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman, Tech. report, 2009, UCLA CAM Report [09-31]."},{"issue":"6","key":"16","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1137\/100806278","article-title":"Hard thresholding pursuit: an algorithm for compressive sensing","volume":"49","author":"Foucart, Simon","year":"2011","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-1-4614-4565-4_30","article-title":"Stability and robustness of weak orthogonal matching pursuits","author":"Foucart, Simon","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781461445654"},{"issue":"3","key":"18","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":"19","unstructured":"P. Jain, A. Tewari, and I.S. Dhillon, Orthogonal matching pursuit with replacement, Tech. Report arXiv:1106.2774, 2011."},{"key":"20","doi-asserted-by":"crossref","unstructured":"A. Maleki, Coherence analysis of iterative thresholding algorithms, Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, IEEE Press, 2009, pp. 236\u2013243.","DOI":"10.1109\/ALLERTON.2009.5394802"},{"key":"21","doi-asserted-by":"crossref","unstructured":"A. Maleki and D.L. Donoho, Optimally tuned iterative reconstruction algorithms for compressed sensing, IEEE J. of Selected Topics in Sig. Processing 4 (2010), no. 2, 330\u2013341.","DOI":"10.1109\/JSTSP.2009.2039176"},{"key":"22","doi-asserted-by":"crossref","unstructured":"S.G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. on Sig. Processing 12 (1993), 3397\u20133415.","DOI":"10.1109\/78.258082"},{"issue":"3","key":"23","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1137\/110858136","article-title":"Multiscale methods for polyhedral regularizations","volume":"23","author":"Moeller, Michael","year":"2013","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"24","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.acha.2008.07.002","article-title":"CoSaMP: iterative signal recovery from incomplete and inaccurate samples","volume":"26","author":"Needell, D.","year":"2009","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"issue":"2","key":"25","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"},{"issue":"1","key":"26","doi-asserted-by":"publisher","first-page":"93","DOI":"10.4310\/cms.2010.v8.n1.a6","article-title":"Fast linearized Bregman iteration for compressive sensing and sparse denoising","volume":"8","author":"Osher, Stanley","year":"2010","journal-title":"Commun. Math. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/1539-6746","issn-type":"print"},{"key":"27","doi-asserted-by":"crossref","unstructured":"F. Parvaresh, H. Vikalo, S. Misra, and B. Hassibi, Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays, IEEE J. of Selected Topics in Signal Processing 2 (2008), 275\u2013285.","DOI":"10.1109\/JSTSP.2008.924384"},{"key":"28","doi-asserted-by":"crossref","unstructured":"Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, 1993, pp. 40\u201344.","DOI":"10.1109\/ACSSC.1993.342465"},{"key":"29","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/9783110226157.1","article-title":"Compressive sensing and structured random matrices","author":"Rauhut, Holger","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783110226140"},{"issue":"10","key":"30","doi-asserted-by":"publisher","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","article-title":"Greed is good: algorithmic results for sparse approximation","volume":"50","author":"Tropp, Joel A.","year":"2004","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"12","key":"31","doi-asserted-by":"publisher","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","article-title":"Signal recovery from random measurements via orthogonal matching pursuit","volume":"53","author":"Tropp, Joel A.","year":"2007","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"32","doi-asserted-by":"crossref","unstructured":"Joel A. Tropp, Algorithms for simultaneous sparse approximation: part II: Convex relaxation, Signal Process. 86 (2006), no. 3, 589\u2013602.","DOI":"10.1016\/j.sigpro.2005.05.031"},{"issue":"284","key":"33","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":"12","key":"34","doi-asserted-by":"publisher","first-page":"6285","DOI":"10.1109\/TSP.2011.2168216","article-title":"Orthonormal expansion \u2113\u2081-minimization algorithms for compressed sensing","volume":"59","author":"Yang, Zai","year":"2011","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"issue":"1","key":"35","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/070703983","article-title":"Bregman iterative algorithms for \ud835\udc59\u2081-minimization with applications to compressed sensing","volume":"1","author":"Yin, Wotao","year":"2008","journal-title":"SIAM J. Imaging Sci."},{"issue":"1","key":"36","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s10915-010-9408-8","article-title":"A unified primal-dual algorithm framework based on Bregman iteration","volume":"46","author":"Zhang, Xiaoqun","year":"2011","journal-title":"J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-7474","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-03004-X\/S0025-5718-2015-03004-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-03004-X\/S0025-5718-2015-03004-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:38:04Z","timestamp":1776796684000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-03004-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,29]]},"references-count":36,"journal-issue":{"issue":"297","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0025-5718-2015-03004-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3004","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,7,29]]}}}