{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T18:09:50Z","timestamp":1771610990551,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642392054","type":"print"},{"value":"9783642392061","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_39","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"461-472","source":"Crossref","is-referenced-by-count":10,"title":["\u21132\/\u21132-Foreach Sparse Recovery with Low Risk"],"prefix":"10.1007","author":[{"given":"Anna C.","family":"Gilbert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Baraniuk, R.G., Candes, E., Nowak, R., Vetterli, M.: Compressive sampling. IEEE Signal Processing Magazine\u00a025(2) (2008)","DOI":"10.1109\/MSP.2008.915557"},{"issue":"12","key":"39_CR2","doi-asserted-by":"publisher","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"E.J. Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Tao, T.: Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? IEEE Transactions on Information Theory\u00a052(12), 5406\u20135425 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"39_CR3","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":"39_CR4","unstructured":"Cohen, A., Dahmen, W., De Vore, R.A.: Near Optimal Approximation of Arbitrary Vectors from Highly Incomplete Measurements. Bericht. Inst. f\u00fcr Geometrie und Praktische Mathematik (2007)"},{"issue":"1","key":"39_CR5","doi-asserted-by":"publisher","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-term approximation. J. Amer. Math. Soc.\u00a022(1), 211\u2013231 (2009)","journal-title":"J. Amer. Math. Soc."},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Hemenway, B., Rudra, A., Strauss, M.J., Wootters, M.: Recovering simple signals. In: ITA, pp. 382\u2013391 (2012)","DOI":"10.1109\/ITA.2012.6181772"},{"issue":"6","key":"39_CR7","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1109\/JPROC.2010.2045092","volume":"98","author":"A.C. Gilbert","year":"2010","unstructured":"Gilbert, A.C., Indyk, P.: Sparse recovery using sparse matrices. Proceedings of the IEEE\u00a098(6), 937\u2013947 (2010)","journal-title":"Proceedings of the IEEE"},{"issue":"2","key":"39_CR8","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1137\/100816705","volume":"41","author":"A.C. Gilbert","year":"2012","unstructured":"Gilbert, A.C., Li, Y., Porat, E., Strauss, M.J.: Approximate sparse recovery: Optimizing time and measurements. SIAM J. Comput.\u00a041(2), 436\u2013453 (2012)","journal-title":"SIAM J. Comput."},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Ngo, H., Porat, E., Rudra, A., Strauss, M.J.: L2\/L2-foreach sparse recovery with low risk. ArXiv e-prints, arXiv:1304.6232 (April 2013)","DOI":"10.1007\/978-3-642-39206-1_39"},{"issue":"1","key":"39_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TIT.2007.911222","volume":"54","author":"V. Guruswami","year":"2008","unstructured":"Guruswami, V., Rudra, A.: Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory\u00a054(1), 135\u2013150 (2008)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"39_CR11","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"V. Guruswami","year":"1999","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of reed-solomon and algebraic-geometry codes. IEEE Transactions on Information Theory\u00a045(6), 1757\u20131767 (1999)","journal-title":"IEEE Transactions on Information Theory"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P., Ruzic, M.: Near-optimal sparse recovery in the l1 norm. In: FOCS, pp. 199\u2013207 (2008)","DOI":"10.1109\/FOCS.2008.82"},{"issue":"9","key":"39_CR13","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.jpdc.2004.03.021","volume":"64","author":"D. Irony","year":"2004","unstructured":"Irony, D., Toledo, S., Tiskin, A.: Communication lower bounds for distributed-memory matrix multiplication. J. Parallel Distrib. Comput.\u00a064(9), 1017\u20131026 (2004)","journal-title":"J. Parallel Distrib. Comput."},{"key":"39_CR14","doi-asserted-by":"publisher","first-page":"2148","DOI":"10.1109\/18.720535","volume":"44","author":"A. Lapidoth","year":"1998","unstructured":"Lapidoth, A., Narayan, P.: Reliable communication under channel uncertainty. IEEE Transactions on Information Theory\u00a044, 2148\u20132177 (1998)","journal-title":"IEEE Transactions on Information Theory"},{"key":"39_CR15","unstructured":"Lehman, A.R., Lehman, E.: Network coding: does the model need tuning? In: SODA, pp. 499\u2013504 (2005)"},{"key":"39_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/3-540-57785-8_183","volume-title":"STACS 94","author":"R.J. Lipton","year":"1994","unstructured":"Lipton, R.J.: A new approach to information theory. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 699\u2013708. Springer, Heidelberg (1994)"},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1090\/S0002-9904-1949-09320-5","volume":"55","author":"L.H. Loomis","year":"1949","unstructured":"Loomis, L.H., Whitney, H.: An inequality related to the isoperimetric inequality. Bull. Amer. Math. Soc.\u00a055, 961\u2013962 (1949)","journal-title":"Bull. Amer. Math. Soc."},{"key":"39_CR18","doi-asserted-by":"crossref","unstructured":"Ngo, H.Q., Porat, E., R\u00e9, C., Rudra, A.: Worst-case optimal join algorithms. In: PODS, pp. 37\u201348 (2012)","DOI":"10.1145\/2213556.2213565"},{"key":"39_CR19","unstructured":"Ngo, H.Q., Porat, E., Rudra, A.: Efficiently decodable compressed sensing by list-recoverable codes and recursion. In: STACS, pp. 230\u2013241 (2012)"},{"key":"39_CR20","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":"39_CR21","doi-asserted-by":"crossref","unstructured":"Price, E., Woodruff, D.P.: (1\u2009+\u2009\u03b5)-approximate sparse recovery. In: FOCS, pp. 295\u2013304 (2011)","DOI":"10.1109\/FOCS.2011.92"},{"key":"39_CR22","unstructured":"Rudra, A.: List Decoding and Property Testing of Error Correcting Codes. PhD thesis, University of Washington (2007)"},{"key":"39_CR23","unstructured":"Tishby, N., Pereira, F.C., Bialek, W.: The information bottleneck method. In: The 37th Annual Allerton Conference on Communication, Control, and Computing, pp. 368\u2013377 (1999)"}],"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-642-39206-1_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:34:02Z","timestamp":1557898442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}