{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:36Z","timestamp":1746331416337,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_45","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"538-550","source":"Crossref","is-referenced-by-count":4,"title":["For-All Sparse Recovery in Near-Optimal Time"],"prefix":"10.1007","author":[{"given":"Anna C.","family":"Gilbert","sequence":"first","affiliation":[]},{"given":"Yi","family":"Li","sequence":"additional","affiliation":[]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"45_CR1","doi-asserted-by":"publisher","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 T. Info. Theory\u00a052(2), 489\u2013509 (2006)","journal-title":"IEEE T. Info. Theory"},{"key":"45_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 693\u2013703. Springer, Heidelberg (2002)"},{"key":"45_CR3","doi-asserted-by":"crossref","unstructured":"Cohen, A., Dahmen, W., Devore, R.: Compressed sensing and best k-term approximation. J. Amer. Math. Soc., 211\u2013231 (2009)","DOI":"10.1090\/S0894-0347-08-00610-3"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: Combinatorial algorithms for compressed sensing. In: SIROCCO, pp. 280\u2013294 (2006)","DOI":"10.1007\/11780823_22"},{"issue":"4","key":"45_CR5","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D.L. Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE T. Info. Theory\u00a052(4), 1289\u20131306 (2006)","journal-title":"IEEE T. Info. Theory"},{"issue":"2","key":"45_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1109\/MSP.2007.914730","volume":"25","author":"M.F. Duarte","year":"2008","unstructured":"Duarte, M.F., Davenport, M.A., Takhar, D., Laska, J.N., Kelly, K.F., Baraniuk, R.G.: Single-pixel imaging via compressive sampling. IEEE Signal Processing Magazine\u00a025(2), 83\u201391 (2008)","journal-title":"IEEE Signal Processing Magazine"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Friedman, J., Kahn, J., Szemer\u00e9di, E.: On the second eigenvalue of random regular graphs. In: STOC, pp. 587\u2013598 (1989)","DOI":"10.1145\/73007.73063"},{"issue":"2","key":"45_CR8","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1137\/100816705","volume":"41","author":"A. Gilbert","year":"2012","unstructured":"Gilbert, A., Li, Y., Porat, E., Strauss, M.: Approximate sparse recovery: Optimizing time and measurements. SIAM J. Comput.\u00a041(2), 436\u2013453 (2012)","journal-title":"SIAM J. Comput."},{"key":"45_CR9","unstructured":"Gilbert, A., Strauss, M., Tropp, J., Vershynin, R.: Algorithmic linear dimension reduction in the \u21131 norm for sparse vectors. In: Allerton (2006)"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Strauss, M., Tropp, J., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: ACM STOC, pp. 237\u2013246 (2007)","DOI":"10.1145\/1250790.1250824"},{"key":"45_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-642-39206-1_39","volume-title":"Automata, Languages, and Programming","author":"A.C. Gilbert","year":"2013","unstructured":"Gilbert, A.C., Ngo, H.Q., Porat, E., Rudra, A., Strauss, M.J.: \u21132\/\u21132-foreach sparse recovery with low risk. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 461\u2013472. Springer, Heidelberg (2013)"},{"key":"45_CR12","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM\u00a056(4), 20:1\u201320:34","DOI":"10.1145\/1538902.1538904"},{"key":"45_CR13","doi-asserted-by":"crossref","unstructured":"Indyk, P., Ngo, H.Q., Rudra, A.: Efficiently decodable non-adaptive group testing. In: SODA, pp. 1126\u20131142 (2010)","DOI":"10.1137\/1.9781611973075.91"},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"Indyk, P., Ruzic, M.: Near-optimal sparse recovery in the \u21131 norm. In: FOCS, pp. 199\u2013207 (2008)","DOI":"10.1109\/FOCS.2008.82"},{"issue":"6","key":"45_CR15","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1002\/mrm.21391","volume":"58","author":"M. Lustig","year":"2007","unstructured":"Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: The application of compressed sensing for rapid MR imaging. Magn. Reson. Med.\u00a058(6), 1182\u20131195 (2007)","journal-title":"Magn. Reson. Med."},{"key":"45_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/978-3-642-32512-0_53","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"J. Nelson","year":"2012","unstructured":"Nelson, J., Nguy\u00ea\u0303n, H.L., Woodruff, D.P.: On deterministic sketching and streaming for sparse recovery and norm estimation. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 627\u2013638. Springer, Heidelberg (2012)"},{"key":"45_CR17","doi-asserted-by":"crossref","unstructured":"Parvaresh, F., Vardy, A.: Correcting errors beyond the guruswami-sudan radius in polynomial time. In: FOCS, pp. 285\u2013294 (2005)","DOI":"10.1109\/SFCS.2005.29"},{"key":"45_CR18","doi-asserted-by":"crossref","unstructured":"Porat, E., Strauss, M.J.: Sublinear time, measurement-optimal, sparse recovery for all. In: SODA, pp. 1215\u20131227 (2012)","DOI":"10.1137\/1.9781611973099.96"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Upfal, E.: Tolerating linear number of faults in networks of bounded degree. In: PODC, pp. 83\u201389 (1992)","DOI":"10.1145\/135419.135437"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:07Z","timestamp":1746264667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}