{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T00:08:57Z","timestamp":1759190937055},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,5,9]],"date-time":"2016-05-09T00:00:00Z","timestamp":1462752000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1007\/s12532-016-0105-y","type":"journal-article","created":{"date-parts":[[2016,5,9]],"date-time":"2016-05-09T05:58:21Z","timestamp":1462773501000},"page":"253-269","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods"],"prefix":"10.1007","volume":"8","author":[{"given":"Robert","family":"Vanderbei","sequence":"first","affiliation":[]},{"given":"Kevin","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Han","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Lie","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,9]]},"reference":[{"key":"105_CR1","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1016\/0885-064X(87)90007-0","volume":"3","author":"I Adler","year":"1987","unstructured":"Adler, I., Karp, R.M., Shamir, R.: A simplex variant solving an $$m\\times d$$ m \u00d7 d linear program in $${O}(\\min (m_2, d_2)$$ O ( min ( m 2 , d 2 ) expected number of pivot steps. J. Complex. 3, 372\u2013387 (1987)","journal-title":"J. Complex."},{"key":"105_CR2","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1214\/10-AOS827","volume":"39","author":"A Belloni","year":"2011","unstructured":"Belloni, A., Chernozhukov, V.: $$\\ell _1$$ \u2113 1 -penalized quantile regression in high-dimensional sparse models. Ann. Stat. 39, 82\u2013130 (2011)","journal-title":"Ann. Stat."},{"key":"105_CR3","doi-asserted-by":"crossref","unstructured":"Cai, T.T., Zhang, A.: Sharp RIP bound for sparse signal and low-rank matrix recovery. Appl. Comput. Harmonic Anal. 35, 74\u201393 (2012)","DOI":"10.1016\/j.acha.2012.07.010"},{"key":"105_CR4","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489\u2013509 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"105_CR5","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.crma.2008.03.014","volume":"346","author":"EJ Cand\u00e8s","year":"2008","unstructured":"Cand\u00e8s, E.J.: The restricted isometry property and its implications for compressed sensing. C. R. Math. 346, 589\u2013592 (2008)","journal-title":"C. R. Math."},{"key":"105_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/S1064827596304010","volume":"20","author":"SS Chen","year":"1998","unstructured":"Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20, 33\u201361 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"105_CR7","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1090\/S0894-0347-08-00610-3","volume":"22","author":"A Cohen","year":"2009","unstructured":"Cohen, A., Dahmen, W., Devore, R.: Compressed sensing and best $$k$$ k -term approximation. J. Am. Math. Soc. 22, 211\u2013231 (2009)","journal-title":"J. Am. Math. Soc."},{"key":"105_CR8","volume-title":"Linear Programming and Extensions","author":"GB Dantzig","year":"1998","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1998)"},{"key":"105_CR9","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"105_CR10","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1073\/pnas.0437847100","volume":"100","author":"DL Donoho","year":"2003","unstructured":"Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via $$\\ell _1$$ \u2113 1 -minimization. Proc. Natl. Acad. Sci USA 100, 2197\u20132202 (2003)","journal-title":"Proc. Natl. Acad. Sci USA"},{"key":"105_CR11","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1109\/TIT.2005.860430","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L., Elad, M., Temlyakov, V.N.: Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory 52, 6\u201318 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"105_CR12","doi-asserted-by":"crossref","first-page":"2845","DOI":"10.1109\/18.959265","volume":"47","author":"DL Donoho","year":"2001","unstructured":"Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47, 2845\u20132862 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"105_CR13","doi-asserted-by":"crossref","first-page":"18914","DOI":"10.1073\/pnas.0909892106","volume":"106","author":"DL Donoho","year":"2009","unstructured":"Donoho, D.L., Maleki, A., Montanari, A.: Message passing algorithms for compressed sensing. Proc. Natl. Acad. Sci. USA 106, 18914\u201318919 (2009)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"105_CR14","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/0149053","volume":"49","author":"DL Donoho","year":"1989","unstructured":"Donoho, D.L., Stark, P.B.: Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49, 906\u2013931 (1989)","journal-title":"SIAM J. Appl. Math."},{"key":"105_CR15","doi-asserted-by":"crossref","unstructured":"Donoho, D.L., Tanner, J.: Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci. 102, 9452\u20139457 (2005)","DOI":"10.1073\/pnas.0502258102"},{"key":"105_CR16","doi-asserted-by":"crossref","unstructured":"Donoho, D. L., Tanner, J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. 102, 9446\u20139451 (2005)","DOI":"10.1073\/pnas.0502269102"},{"key":"105_CR17","doi-asserted-by":"crossref","first-page":"4273","DOI":"10.1098\/rsta.2009.0152","volume":"367","author":"DL Donoho","year":"2009","unstructured":"Donoho, D.L., Tanner, J.: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philos. Trans. Roy. Soc. S. A 367, 4273\u20134273 (2009)","journal-title":"Philos. Trans. Roy. Soc. S. A"},{"key":"105_CR18","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1109\/TIP.2011.2165289","volume":"21","author":"MF Duarte","year":"2012","unstructured":"Duarte, M.F., Baraniuk, R.G.: Kronecker compressive sensing. IEEE Trans. Image Process. 21, 494\u2013504 (2012)","journal-title":"IEEE Trans. Image Process."},{"key":"105_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-7011-4","volume-title":"Sparse and Redundant Representations\u2014From Theory to Applications in Signal and Image Processing","author":"M Elad","year":"2010","unstructured":"Elad, M.: Sparse and Redundant Representations\u2014From Theory to Applications in Signal and Image Processing. Springer, New York (2010)"},{"key":"105_CR20","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1109\/JSTSP.2007.910281","volume":"1","author":"M Figueiredo","year":"2008","unstructured":"Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1, 586\u2013597 (2008)","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"105_CR21","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF01581089","volume":"57","author":"JJ Forrest","year":"1992","unstructured":"Forrest, J.J., Goldfarb, D.: Steepest-edge simplex algorithms for linear programming. Math. Program. 57, 341\u2013374 (1992)","journal-title":"Math. Program."},{"key":"105_CR22","doi-asserted-by":"crossref","first-page":"2543","DOI":"10.1137\/100806278","volume":"49","author":"S Foucart","year":"2011","unstructured":"Foucart, S.: Hard thresholding pursuit: an algorithm for compressive sensing. SIAM J. Numer. Anal. 49, 2543\u20132563 (2011)","journal-title":"SIAM J. Numer. Anal."},{"key":"105_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-8176-4948-7","volume-title":"A Mathematical Introduction to Compressive Sensing","author":"S Foucart","year":"2013","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Springer, New York (2013)"},{"key":"105_CR24","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Strauss, M.J., Tropp, J.A., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 237\u2013246. ACM, New York (2007)","DOI":"10.1145\/1250790.1250824"},{"key":"105_CR25","doi-asserted-by":"crossref","unstructured":"Gill, P.E., Murray, W., Ponceleon, D.B., Saunders, M.A.: Solving reduced KKT systems in barrier methods for linear and quadratic programming. Tech. rep, DTIC Document (1991)","DOI":"10.21236\/ADA239191"},{"key":"105_CR26","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10208-009-9057-1","volume":"10","author":"MA Iwen","year":"2010","unstructured":"Iwen, M.A.: Combinatorial sublinear-time Fourier algorithms. Found. Comut. Math. 10, 303\u2013338 (2010)","journal-title":"Found. Comut. Math."},{"key":"105_CR27","unstructured":"Juditsky, A., Karzan, F.K., Nemirovski, A.: $$\\ell _1$$ \u2113 1 minimization via randomized first order algorithms. Universit\u00e9 Joseph Fourier, Tech. rep. (2014)"},{"key":"105_CR28","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1109\/JSTSP.2007.910971","volume":"1","author":"S Kim","year":"2007","unstructured":"Kim, S., Koh, K., Lustig, M., Boyd, S., Gorinevsky, D.: An interior-point method for large-scale $$l_1$$ l 1 -regularized least squares. IEEE Trans. Sel. Top. Signal Process. 1, 606\u2013617 (2007)","journal-title":"IEEE Trans. Sel. Top. Signal Process."},{"key":"105_CR29","unstructured":"Klee, V., Minty, G. J.: How good is the simplex method? Inequalities-III, pp. 159\u2013175 (1972)"},{"key":"105_CR30","unstructured":"Kutyniok, G.: Compressed sensing: theory and applications. CoRR . arXiv:1203.3815 (2012)"},{"key":"105_CR31","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1287\/opre.39.5.757","volume":"39","author":"IJ Lustig","year":"1991","unstructured":"Lustig, I.J., Mulvey, J.M., Carpenter, T.J.: Formulating two-stage stochastic programs for interior point methods. Oper. Res. 39, 757\u2013770 (1991)","journal-title":"Oper. Res."},{"key":"105_CR32","doi-asserted-by":"crossref","first-page":"3397","DOI":"10.1109\/78.258082","volume":"41","author":"S Mallat","year":"1993","unstructured":"Mallat, S., Zhang, Z.: Matching pursuits with time-frequency dictionaries. Signal Process. IEEE Trans. 41, 3397\u20133415 (1993)","journal-title":"Signal Process. IEEE Trans."},{"key":"105_CR33","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1145\/1859204.1859229","volume":"53","author":"D Needell","year":"2010","unstructured":"Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Commun. ACM 53, 93\u2013100 (2010)","journal-title":"Commun. ACM"},{"key":"105_CR34","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10208-008-9031-3","volume":"9","author":"D Needell","year":"2009","unstructured":"Needell, D., Vershynin, R.: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comut. Math. 9, 317\u2013334 (2009)","journal-title":"Found. Comut. Math."},{"key":"105_CR35","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.ejor.2007.03.026","volume":"187","author":"P-Q Pan","year":"2008","unstructured":"Pan, P.-Q.: A largest-distance pivot rule for the simplex algorithm. Eur. J. Oper. Res. 187, 393\u2013402 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"105_CR36","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1287\/moor.2014.0699","volume":"40","author":"I Post","year":"2015","unstructured":"Post, I., Ye, Y.: The simplex method is strongly polynomial for deterministic markov decision processes. Math. Oper. Res. 40, 859\u2013868 (2015)","journal-title":"Math. Oper. Res."},{"key":"105_CR37","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM (JACM) 51, 385\u2013463 (2004)","journal-title":"J. ACM (JACM)"},{"key":"105_CR38","doi-asserted-by":"crossref","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","volume":"50","author":"JA Tropp","year":"2004","unstructured":"Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50, 2231\u20132242 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"105_CR39","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0024-3795(91)90269-3","volume":"152","author":"R Vanderbei","year":"1991","unstructured":"Vanderbei, R.: Splitting dense columns in sparse linear systems. Linear Algebra Appl. 152, 107\u2013117 (1991)","journal-title":"Linear Algebra Appl."},{"key":"105_CR40","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1080\/10556789908805759","volume":"12","author":"R Vanderbei","year":"1999","unstructured":"Vanderbei, R.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 12, 451\u2013484 (1999)","journal-title":"Optim. Methods Softw."},{"key":"105_CR41","volume-title":"Linear Programming: Foundations and Extensions","author":"R Vanderbei","year":"2007","unstructured":"Vanderbei, R.: Linear Programming: Foundations and Extensions, 3rd edn. Springer, New York (2007)","edition":"3"},{"key":"105_CR42","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1287\/ijoc.5.2.134","volume":"5","author":"RJ Vanderbei","year":"1993","unstructured":"Vanderbei, R.J.: Alpo: another linear program optimizer. ORSA J. Comput. 5, 134\u2013146 (1993)","journal-title":"ORSA J. Comput."},{"key":"105_CR43","doi-asserted-by":"crossref","unstructured":"Vanderbei, R. J.: Linear programming. Foundations and extensions, International Series in Operations Research & Management Science, vol. 37 (2001)","DOI":"10.1007\/978-1-4757-5662-3"},{"key":"105_CR44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s12532-011-0034-8","volume":"4","author":"RJ Vanderbei","year":"2012","unstructured":"Vanderbei, R.J.: Fast Fourier optimization. Math. Prog. Comp. 4, 1\u201317 (2012)","journal-title":"Math. Prog. Comp."},{"key":"105_CR45","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/070703983","volume":"1","author":"W Yin","year":"2008","unstructured":"Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for $$\\ell _1$$ \u2113 1 -minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1, 143\u2013168 (2008)","journal-title":"SIAM J. Imaging Sci."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0105-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-016-0105-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0105-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T12:16:47Z","timestamp":1567858607000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-016-0105-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,9]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["105"],"URL":"https:\/\/doi.org\/10.1007\/s12532-016-0105-y","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,9]]}}}