{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:25:59Z","timestamp":1764174359586,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T00:00:00Z","timestamp":1488758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DARPA\/ONR","award":["N66001-08-1-2065"],"award-info":[{"award-number":["N66001-08-1-2065"]}]},{"name":"NSF CCF","award":["0743372"],"award-info":[{"award-number":["0743372"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"\n An\n approximate sparse recovery system<\/jats:italic>\n in \u2113\n 1<\/jats:sub>\n norm consists of parameters\n k<\/jats:italic>\n , \u03f5,\n N<\/jats:italic>\n ; an\n m<\/jats:italic>\n -by-\n N<\/jats:italic>\n measurement \u03a6; and a recovery algorithm\n R<\/jats:italic>\n . Given a vector,\n x<\/jats:bold>\n , the system approximates\n x<\/jats:italic>\n by x\u02c6 =\n R<\/jats:italic>\n (\u03a6\n x<\/jats:bold>\n ), which must satisfy \u2016 x\u02c6-\n x<\/jats:bold>\n \u2016\n 1<\/jats:sub>\n \u2264 (1+\u03f5)\u2016\n x<\/jats:bold>\n -\n x<\/jats:bold>\n k<\/jats:sub>\n \u2016\n 1<\/jats:sub>\n . We consider the \u201cfor all\u201d model, in which a single matrix \u03a6, possibly \u201cconstructed\u201d non-explicitly using the probabilistic method, is used for all signals\n x<\/jats:bold>\n . The best existing sublinear algorithm by Porat and Strauss [2012] uses\n O<\/jats:italic>\n (\u03f5\n \u22123<\/jats:sup>\n k<\/jats:italic>\n log (\n N<\/jats:italic>\n \/\n k<\/jats:italic>\n )) measurements and runs in time\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 1 \u2212 \u03b1<\/jats:sup>\n N<\/jats:italic>\n \u03b1<\/jats:sup>\n ) for any constant \u03b1 > 0.\n <\/jats:p>\n \n In this article, we improve the number of measurements to\n O<\/jats:italic>\n (\u03f5\n \u2212 2<\/jats:sup>\n k<\/jats:italic>\n log (\n N<\/jats:italic>\n \/\n k<\/jats:italic>\n )), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 1+\u03b2<\/jats:sup>\n poly(log\n N<\/jats:italic>\n ,1\/\u03f5)), with a modest restriction that\n k<\/jats:italic>\n \u2a7d\n N<\/jats:italic>\n 1 \u2212 \u03b1<\/jats:sup>\n and \u03f5 \u2a7d (log\n k<\/jats:italic>\n \/log\n N<\/jats:italic>\n )\n \u03b3<\/jats:sup>\n for any constants \u03b1, \u03b2, \u03b3 > 0. When\n k<\/jats:italic>\n \u2a7d log\n \n c<\/jats:italic>\n <\/jats:sup>\n N<\/jats:italic>\n for some\n c<\/jats:italic>\n > 0, the runtime is reduced to\n O<\/jats:italic>\n (\n k<\/jats:italic>\n poly(\n N<\/jats:italic>\n ,1\/\u03f5)). With no restrictions on \u03f5, we have an approximation recovery system with\n m<\/jats:italic>\n =\n O<\/jats:italic>\n (\n k<\/jats:italic>\n \/\u03f5log (\n N<\/jats:italic>\n \/\n k<\/jats:italic>\n )((log\n N<\/jats:italic>\n \/log\n k<\/jats:italic>\n )\n \u03b3<\/jats:sup>\n + 1\/\u03f5)) measurements.\n <\/jats:p>\n \n The overall architecture of this algorithm is similar to that of Porat and Strauss [2012] in that we repeatedly use a weak recovery system (with varying parameters) to obtain a top-level recovery algorithm. The weak recovery system consists of a two-layer hashing procedure (or with two unbalanced expanders for a deterministic algorithm). The algorithmic innovation is a novel encoding procedure that is reminiscent of network coding and that reflects the structure of the hashing stages. The idea is to encode the signal position index\n i<\/jats:italic>\n by associating it with a unique message\n m<\/jats:bold>\n \n i<\/jats:italic>\n <\/jats:sub>\n , which will be encoded to a longer message\n m<\/jats:bold>\n \u2032\n \n i<\/jats:italic>\n <\/jats:sub>\n (in contrast to Porat and Strauss [2012] in which the encoding is simply the identity). Portions of the message\n m<\/jats:bold>\n \u2032\n \n i<\/jats:italic>\n <\/jats:sub>\n correspond to repetitions of the hashing, and we use a regular expander graph to encode the linkages among these portions.\n <\/jats:p>\n \n The decoding or recovery algorithm consists of recovering the portions of the longer messages\n m<\/jats:bold>\n \u2032\n \n i<\/jats:italic>\n <\/jats:sub>\n and then decoding to the original messages\n m<\/jats:bold>\n \n i<\/jats:italic>\n <\/jats:sub>\n , all the while ensuring that corruptions can be detected and\/or corrected. The recovery algorithm is similar to list recovery introduced in Indyk et al. [2010] and used in Gilbert et al. [2013]. In our algorithm, the messages {\n m<\/jats:bold>\n \n i<\/jats:italic>\n <\/jats:sub>\n } are independent of the hashing, which enables us to obtain a better result.\n <\/jats:p>","DOI":"10.1145\/3039872","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T19:12:04Z","timestamp":1488913924000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["For-All Sparse Recovery in Near-Optimal Time"],"prefix":"10.1145","volume":"13","author":[{"given":"Anna C.","family":"Gilbert","sequence":"first","affiliation":[{"name":"Department of Mathematics. University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6420-653X","authenticated-orcid":false,"given":"Yi","family":"Li","sequence":"additional","affiliation":[{"name":"Division of Mathematics, SPMS. Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[{"name":"Department of Computer Science. Bar-Ilan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[{"name":"Department of Mathematics. University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2008.4797639"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.022"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884458"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496855"},{"volume-title":"Compressed sensing and best k-term approximation. J. Am. Math. Soc","year":"2009","author":"Cohen Albert","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2006.286461"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2007.914730"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73063"},{"volume-title":"Proceedings of 44th Annual Allerton Conference on Communication, Control, and Computing (Allerton).","year":"2006","author":"Gilbert Anna","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/100816705"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_39"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250824"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873692"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.82"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/mrm.21391"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.12.025"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.29"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095212"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.838377"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/135419.135437"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039872","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039872","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:31Z","timestamp":1750217791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3039872"],"URL":"https:\/\/doi.org\/10.1145\/3039872","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}