{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T00:45:06Z","timestamp":1772757906090,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,2,4]],"date-time":"2015-02-04T00:00:00Z","timestamp":1423008000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PF 709\/1-1, LO 1436\/3-1, LO 1436\/2-1"],"award-info":[{"award-number":["PF 709\/1-1, LO 1436\/3-1, LO 1436\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2015,2,4]]},"abstract":"<jats:p>\n            The problem of finding a minimum \u2113\n            <jats:sub>1<\/jats:sub>\n            -norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as\n            <jats:italic>basis pursuit<\/jats:italic>\n            . We propose a heuristic optimality check as a general tool for \u2113\n            <jats:sub>1<\/jats:sub>\n            -minimization, which often allows for early termination by \u201cguessing\u201d a primal-dual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art \u2113\n            <jats:sub>1<\/jats:sub>\n            -solvers that have been proposed during the last decade, on a large test set with a variety of explicitly given matrices and several right-hand sides per matrix reflecting different levels of solution difficulty. The results, as well as improvements by the proposed heuristic optimality check, are analyzed in detail to provide an answer to the question which algorithm is the best.\n          <\/jats:p>","DOI":"10.1145\/2689662","type":"journal-article","created":{"date-parts":[[2015,2,10]],"date-time":"2015-02-10T13:19:47Z","timestamp":1423574387000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Solving Basis Pursuit"],"prefix":"10.1145","volume":"41","author":[{"given":"Dirk A.","family":"Lorenz","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Braunschweig, Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas M.","family":"Tillmann","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,2,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Primal dual pursuit\u2014A homotopy based algorithm for the dantzig selector. Master's thesis","author":"Asif M. Salman","unstructured":"M. Salman Asif . 2008. Primal dual pursuit\u2014A homotopy based algorithm for the dantzig selector. Master's thesis , Georgia Institute of Technology . M. Salman Asif. 2008. Primal dual pursuit\u2014A homotopy based algorithm for the dantzig selector. Master's thesis, Georgia Institute of Technology."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756855"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497330963"},{"key":"e_1_2_1_4_1","volume-title":"Convex Optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press , New York, NY . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Jian-Feng Cai Stanley Osher and Zuowei Shen. 2009. Linearized Bregman iterations for compressed sensing. Math. Comp. 78 267 1515--1536.  Jian-Feng Cai Stanley Osher and Zuowei Shen. 2009. Linearized Bregman iterations for compressed sensing. Math. Comp. 78 267 1515--1536.","DOI":"10.1090\/S0025-5718-08-02189-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120697"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718814"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.173207"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.959265"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.929958"},{"key":"e_1_2_1_13_1","unstructured":"Junbo Duan Charles Soussen David Brie J\u00e9r\u00f4me Idier and Yu-Ping Wang. 2011. A sufficient condition on monotonic increase of the number of nonzero entry in the optimizer of L1 norm penalized least-square problem. arXiv:1104.3792 {stat.ML}.  Junbo Duan Charles Soussen David Brie J\u00e9r\u00f4me Idier and Yu-Ping Wang. 2011. A sufficient condition on monotonic increase of the number of nonzero entry in the optimizer of L1 norm penalized least-square problem. arXiv:1104.3792 {stat.ML}."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053604000000067"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2007.910281"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.828141"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20350"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_19_1","volume-title":"Minty","author":"Klee Victor","year":"1972","unstructured":"Victor Klee and George J . Minty . 1972 . How good is the simplex algorithm&quest; In Inequalities, (III Proceedings of the 3rd Symposium Dedicated to the Memory of Theodore S. Motzkin). Academic Press , New York, NY, 159--175. Victor Klee and George J. Minty. 1972. How good is the simplex algorithm&quest; In Inequalities, (III Proceedings of the 3rd Symposium Dedicated to the Memory of Theodore S. Motzkin). Academic Press, New York, NY, 159--175."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00200-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-005-3914-x"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2012.2236322"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9602-3"},{"key":"e_1_2_1_25_1","first-page":"085009","article-title":"Beyond convergence rates: Exact inversion with Tikhonov regularization with sparsity constraints. Inve","volume":"27","author":"Lorenz Dirk A.","year":"2011","unstructured":"Dirk A. Lorenz , Stefan Schiffler , and Dennis Trede . 2011 . Beyond convergence rates: Exact inversion with Tikhonov regularization with sparsity constraints. Inve . Prob. 27 , 085009 . Dirk A. Lorenz, Stefan Schiffler, and Dennis Trede. 2011. Beyond convergence rates: Exact inversion with Tikhonov regularization with sparsity constraints. Inve. Prob. 27, 085009.","journal-title":"Prob."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning (ICML). J. Langford and J. Pineau (Eds.)","author":"Mairal J.","unstructured":"J. Mairal and B. Yu . 2012. Complexity analysis of the Lasso regularization path . In Proceedings of the 29th International Conference on Machine Learning (ICML). J. Langford and J. Pineau (Eds.) , Omnipress, Madison, WI, 353--360. J. Mairal and B. Yu. 2012. Complexity analysis of the Lasso regularization path. In Proceedings of the 29th International Conference on Machine Learning (ICML). J. Langford and J. Pineau (Eds.), Omnipress, Madison, WI, 353--360."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'05)","volume":"5","author":"Malioutov Dmitry M.","unstructured":"Dmitry M. Malioutov , M\u00fcjdat \u00c7etin , and Alan S. Willsky . 2005. Homotopy continuation for sparse signal representation . In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'05) . Vol. 5 , IEEE, New York, NY, 733--736. Dmitry M. Malioutov, M\u00fcjdat \u00c7etin, and Alan S. Willsky. 2005. Homotopy continuation for sparse signal representation. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'05). Vol. 5, IEEE, New York, NY, 733--736."},{"key":"e_1_2_1_28_1","first-page":"13","article-title":"Iterative methods for solving linear ill-posed problems under precise information","volume":"2","author":"Nemirovskiy Arkadi S.","year":"1984","unstructured":"Arkadi S. Nemirovskiy and Boris T. Polyak . 1984 . Iterative methods for solving linear ill-posed problems under precise information . I. Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika 2 , 13 -- 25 , 203. Arkadi S. Nemirovskiy and Boris T. Polyak. 1984. Iterative methods for solving linear ill-posed problems under precise information. I. Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika 2, 13--25, 203.","journal-title":"I. Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/20.3.389"},{"key":"e_1_2_1_31_1","first-page":"40","article-title":"Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Annual Asilomar Conference on Signals","volume":"1","author":"Pati Y. C.","year":"1993","unstructured":"Y. C. Pati , R. Rezaiifar , and P. S. Krishnaprasad . 1993 . Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Annual Asilomar Conference on Signals , Systems and Computers. Vol. 1 , CA, 40 -- 44 . Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad. 1993. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Annual Asilomar Conference on Signals, Systems and Computers. Vol. 1, CA, 40--44.","journal-title":"Systems and Computers."},{"key":"e_1_2_1_32_1","volume-title":"Nonlinear Optimization","author":"Ruszczy\u0144ski Andrzej","unstructured":"Andrzej Ruszczy\u0144ski . 2006. Nonlinear Optimization . Princeton University Press , Princeton, NJ . Andrzej Ruszczy\u0144ski. 2006. Nonlinear Optimization. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_33_1","volume-title":"Minimization Methods for Non-Differentiable Functions","author":"Shor Naum Z.","unstructured":"Naum Z. Shor . 1985. Minimization Methods for Non-Differentiable Functions . Springer, New York , NY. Naum Z. Shor. 1985. Minimization Methods for Non-Differentiable Functions. Springer, New York, NY."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.834793"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864420"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909108"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714488"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772447"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/090747695"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Allen Y. Yang Zihan Zhou Arvind Ganesh S. Shankar Sastry and Yi Ma. 2010. A review of fast &ell;1-minimization algorithms for robust face recognition. arXiv:1007.3753 {cs.CV}.  Allen Y. Yang Zihan Zhou Arvind Ganesh S. Shankar Sastry and Yi Ma. 2010. A review of fast &ell; 1 -minimization algorithms for robust face recognition. arXiv:1007.3753 {cs.CV}.","DOI":"10.21236\/ADA525384"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/090777761"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/090760350"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/070703983"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2689662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2689662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:46Z","timestamp":1750272946000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2689662"}},"subtitle":["Heuristic Optimality Check and Solver Comparison"],"short-title":[],"issued":{"date-parts":[[2015,2,4]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2,4]]}},"alternative-id":["10.1145\/2689662"],"URL":"https:\/\/doi.org\/10.1145\/2689662","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,4]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}