{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T09:02:05Z","timestamp":1762506125265},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,7,13]],"date-time":"2013-07-13T00:00:00Z","timestamp":1373673600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s12532-013-0056-5","type":"journal-article","created":{"date-parts":[[2013,7,12]],"date-time":"2013-07-12T11:55:34Z","timestamp":1373630134000},"page":"267-304","source":"Crossref","is-referenced-by-count":28,"title":["GPU accelerated greedy algorithms for compressed sensing"],"prefix":"10.1007","volume":"5","author":[{"given":"Jeffrey D.","family":"Blanchard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jared","family":"Tanner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,7,13]]},"reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"Alabi, T., Blanchard, J., Gordon, B., Steinbach, R.: Fast k-selection algorithms for graphics processing units. ACM J. Exp. Algorithmics 17(2), 4.2:1\u20134.2:29 (2012) (Article 4.2)","DOI":"10.1145\/2133803.2345676"},{"issue":"1","key":"56_CR2","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(80)90023-X","volume":"11","author":"D Allison","year":"1980","unstructured":"Allison, D., Noga, M.: Selection by distributive partitioning. Inf. Process. Lett. 11(1), 7\u20138 (1980)","journal-title":"Inf. Process. Lett."},{"key":"56_CR3","unstructured":"Beliakov, G.: Parallel calculation of the median and order statistics on GPUs with application to robust regression. Computing Research Repository abs\/1104.2 (2011)"},{"key":"56_CR4","unstructured":"Berg, E.v.d., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890\u2013912 (2008)"},{"key":"56_CR5","unstructured":"Blanchard, J.D., Tanner, J.: GAGA: GPU Accelerated Greedy Algorithms (2013). www.gaga4cs.org . Version 1.0.0"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"Blanchard, J.D., Tanner, J.: Performance comparisons of greedy algorithms in compressed sensing. www.math.grinnell.edu\/~blanchaj\/PCGACS_preprint.pdf (2013, submitted)","DOI":"10.1007\/s12532-013-0056-5"},{"issue":"3","key":"56_CR7","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.acha.2009.04.002","volume":"27","author":"T Blumensath","year":"2009","unstructured":"Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265\u2013274 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"2","key":"56_CR8","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1109\/JSTSP.2010.2042411","volume":"4","author":"T Blumensath","year":"2010","unstructured":"Blumensath, T., Davies, M.E.: Normalised iterative hard thresholding; guaranteed stability and performance. IEEE Select. Topics Signal Process. 4(2), 298\u2013309 (2010)","journal-title":"IEEE Select. Topics Signal Process."},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E.J.: Compressive sampling. In: International Congress of Mathematicians, Vol. III, pp. 1433\u20131452. Eur. Math. Soc., Z\u00fcrich (2006)","DOI":"10.4171\/022-3\/69"},{"issue":"8","key":"56_CR10","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"12","key":"56_CR11","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"56_CR12","doi-asserted-by":"crossref","unstructured":"Cevher, V.: An ALPS view of sparse recovery. In: 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5808\u20135811. IEEE (2011)","DOI":"10.1109\/ICASSP.2011.5947681"},{"issue":"5","key":"56_CR13","doi-asserted-by":"crossref","first-page":"2230","DOI":"10.1109\/TIT.2009.2016006","volume":"55","author":"W Dai","year":"2009","unstructured":"Dai, W., Milenkovic, O.: Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Inform. Theory 55(5), 2230\u20132249 (2009)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"56_CR14","unstructured":"Donoho, D.L.: Neighborly polytopes and sparse solution of underdetermined linear equations: Technical Report. Stanford University, Department of Statistics (2004)"},{"issue":"4","key":"56_CR15","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. Inform. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"7","key":"56_CR16","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1002\/cpa.20131","volume":"59","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: For most large underdetermined systems of equations, the minimal $$l_1$$ l 1 -norm near-solution approximates the sparsest near-solution. Commun. Pure Appl. Math. 59(7), 907\u2013934 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"4","key":"56_CR17","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1007\/s00454-005-1220-0","volume":"35","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete Comput. Geom. 35(4), 617\u2013652 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"56_CR18","doi-asserted-by":"crossref","unstructured":"Donoho, D.L., Tanner, J.: Sparse nonnegative solution of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27), 9446\u20139451 (2005) (electronic)","DOI":"10.1073\/pnas.0502269102"},{"issue":"11","key":"56_CR19","doi-asserted-by":"crossref","first-page":"4789","DOI":"10.1109\/TIT.2008.929958","volume":"54","author":"DL Donoho","year":"2008","unstructured":"Donoho, D.L., Tsaig, Y.: Fast solution of l1 minimization problems when the solution may be sparse. IEEE Trans. Inform. Theory 54(11), 4789\u20134812 (2008)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"56_CR20","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1109\/TIT.2011.2173241","volume":"58","author":"DL Donoho","year":"2012","unstructured":"Donoho, D.L., Tsaig, Y., Drori, I., Stark, J.L.: Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. IEEE Trans. Inform. Theory 58(2), 1094\u20131121 (2012)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"4","key":"56_CR21","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1109\/JSTSP.2007.910281","volume":"1","author":"MAT Figueiredo","year":"2007","unstructured":"Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE Select. Topics Signal Process. 1(4), 586\u2013597 (2007)","journal-title":"IEEE Select. Topics Signal Process."},{"issue":"6","key":"56_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(6), 2543\u20132563 (2011)","journal-title":"SIAM J. Numer. Anal."},{"key":"56_CR23","unstructured":"Hoberock, J., Bell, N.: Thrust: A parallel template library (2010). http:\/\/www.meganewtons.com\/ . Version 1.3.0, http:\/\/www.meganewtons.com\/"},{"key":"56_CR24","doi-asserted-by":"crossref","unstructured":"Kyrillidis, A., Cevher, V.: Recipes on hard thresholding methods. In: 2011 4th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 353\u2013356. IEEE (2011)","DOI":"10.1109\/CAMSAP.2011.6136024"},{"key":"56_CR25","unstructured":"Lee, S., Wright, S.J.: Implementing algorithms for signal and image reconstruction on graphical processing units (2008). http:\/\/pages.cs.wisc.edu\/swright\/GPUreconstruction\/gpu_image.pdf"},{"issue":"12","key":"56_CR26","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. IEEE Trans. Signal Process. 41(12), 3397\u20133415 (1993)","journal-title":"IEEE Trans. Signal Process."},{"issue":"02","key":"56_CR27","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1142\/S0129626411000187","volume":"21","author":"D Merrill","year":"2011","unstructured":"Merrill, D., Grimshaw, A.: High performance and scalable radix sorting: a case study of implementing dynamic parallelism for GPU computing. Parallel Process. Lett. 21(02), 245\u2013272 (2011)","journal-title":"Parallel Process. Lett."},{"key":"56_CR28","doi-asserted-by":"crossref","unstructured":"Monroe, L., Wendelberger, J., Michalak, S.: Randomized selection on the GPU. In: Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, HPG \u201911, pp. 89\u201398. ACM, New York (2011)","DOI":"10.1145\/2018323.2018338"},{"issue":"2","key":"56_CR29","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/S0097539792240406","volume":"24","author":"BK Natarajan","year":"1995","unstructured":"Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2), 227\u2013234 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"56_CR30","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.acha.2008.07.002","volume":"26","author":"D Needell","year":"2009","unstructured":"Needell, D., Tropp, J.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26(3), 301\u2013321 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"56_CR31","unstructured":"NVIDIA: Cuda toolkit 4.0 (2011). http:\/\/developer.nvidia.com\/cuda-toolkit-40"},{"issue":"10","key":"56_CR32","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. Inform. Theory 50(10), 2231\u20132242 (2004)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"12","key":"56_CR33","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","volume":"53","author":"JA Tropp","year":"2007","unstructured":"Tropp, J.A., Gilbert, A.C.: Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inform. Theory 53(12), 4655\u20134666 (2007)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"56_CR34","doi-asserted-by":"crossref","unstructured":"Wright, S.J., Nowak, R.D., Figueiredo, M.A.T.: Sparse reconstruction by separable approximation. In: Proceedings of the International Conference on Acoustics, Speech, and, Signal Processing (2008)","DOI":"10.1109\/ICASSP.2008.4518374"},{"issue":"1","key":"56_CR35","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(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-013-0056-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-013-0056-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-013-0056-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T13:16:59Z","timestamp":1715692619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-013-0056-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,13]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["56"],"URL":"https:\/\/doi.org\/10.1007\/s12532-013-0056-5","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,13]]}}}