{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:09Z","timestamp":1750220109028,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-18-1-2562"],"award-info":[{"award-number":["N00014-18-1-2562"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"\n An\n \n \\ell _p<\/jats:tex-math>\n <\/jats:inline-formula>\n oblivious subspace embedding is a distribution over\n \n r \\times n<\/jats:tex-math>\n <\/jats:inline-formula>\n matrices\n \n \\Pi<\/jats:tex-math>\n <\/jats:inline-formula>\n such that for any fixed\n \n n \\times d<\/jats:tex-math>\n <\/jats:inline-formula>\n matrix\n A<\/jats:italic>\n ,\n \n \\[ \n\\Pr _{\\Pi }[\\textrm {for all }x, \\ \\Vert Ax\\Vert _p \\le \\Vert \\Pi Ax\\Vert _p \\le \\kappa \\Vert Ax\\Vert _p] \\ge 9\/10,\n\\]<\/jats:tex-math>\n <\/jats:disp-formula>\n where\n r<\/jats:italic>\n is the\n dimension<\/jats:italic>\n of the embedding,\n \n \\kappa<\/jats:tex-math>\n <\/jats:inline-formula>\n is the\n distortion<\/jats:italic>\n of the embedding, and for an\n n<\/jats:italic>\n -dimensional vector\n y<\/jats:italic>\n ,\n \n \\Vert y\\Vert _p = (\\sum _{i=1}^n |y_i|^p)^{1\/p}<\/jats:tex-math>\n <\/jats:inline-formula>\n is the\n \n \\ell _p<\/jats:tex-math>\n <\/jats:inline-formula>\n -norm. Another important property is the\n sparsity<\/jats:italic>\n of\n \n \\Pi<\/jats:tex-math>\n <\/jats:inline-formula>\n , that is, the maximum number of non-zero entries per column, as this determines the running time of computing\n \n \\Pi A<\/jats:tex-math>\n <\/jats:inline-formula>\n . While for\n \n p = 2<\/jats:tex-math>\n <\/jats:inline-formula>\n there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of\n \n 1 \\le p \\lt 2<\/jats:tex-math>\n <\/jats:inline-formula>\n , much less was known. In this article, we obtain nearly optimal tradeoffs for\n \n \\ell _1<\/jats:tex-math>\n <\/jats:inline-formula>\n oblivious subspace embeddings, as well as new tradeoffs for\n \n 1 \\lt p \\lt 2<\/jats:tex-math>\n <\/jats:inline-formula>\n . Our main results are as follows:\n \n \n (1)<\/jats:label>\n \n We show for every\n \n 1 \\le p \\lt 2<\/jats:tex-math>\n <\/jats:inline-formula>\n , any oblivious subspace embedding with dimension\n r<\/jats:italic>\n has distortion\n \n \\[ \n\\kappa = \\Omega \\left(\\frac{1}{\\left(\\frac{1}{d}\\right)^{1 \/ p} \\log ^{2 \/ p}r + \\left(\\frac{r}{n}\\right)^{1 \/ p - 1 \/ 2}}\\right).\n\\]<\/jats:tex-math>\n <\/jats:disp-formula>\n <\/jats:p>\n \n When\n \n r = {\\operatorname{poly}}(d) \\ll n<\/jats:tex-math>\n <\/jats:inline-formula>\n in applications, this gives a\n \n \\kappa = \\Omega (d^{1\/p}\\log ^{-2\/p} d)<\/jats:tex-math>\n <\/jats:inline-formula>\n lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for\n \n p = 1<\/jats:tex-math>\n <\/jats:inline-formula>\n is optimal up to\n \n {\\operatorname{poly}}(\\log (d))<\/jats:tex-math>\n <\/jats:inline-formula>\n factors.\n <\/jats:p>\n <\/jats:list-item>\n \n (2)<\/jats:label>\n \n We give sparse oblivious subspace embeddings for every\n \n 1 \\le p \\lt 2<\/jats:tex-math>\n <\/jats:inline-formula>\n . Importantly, for\n \n p = 1<\/jats:tex-math>\n <\/jats:inline-formula>\n , we achieve\n \n r = O(d \\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n \\kappa = O(d \\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n s = O(\\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n non-zero entries per column. The best previous construction with\n \n s \\le {\\operatorname{poly}}(\\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n is due to Woodruff and Zhang (COLT, 2013), giving\n \n \\kappa = \\Omega (d^2 {\\operatorname{poly}}(\\log d))<\/jats:tex-math>\n <\/jats:inline-formula>\n or\n \n \\kappa = \\Omega (d^{3\/2} \\sqrt {\\log n} \\cdot {\\operatorname{poly}}(\\log d))<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n r \\ge d \\cdot {\\operatorname{poly}}(\\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n ; in contrast our\n \n r = O(d \\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\kappa = O(d \\log d)<\/jats:tex-math>\n <\/jats:inline-formula>\n are optimal up to\n \n {\\operatorname{poly}}(\\log (d))<\/jats:tex-math>\n <\/jats:inline-formula>\n factors even for dense matrices.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n We also give (1)\n \n \\ell _p<\/jats:tex-math>\n <\/jats:inline-formula>\n oblivious subspace embeddings with an expected\n \n 1+\\varepsilon<\/jats:tex-math>\n <\/jats:inline-formula>\n number of non-zero entries per column for arbitrarily small\n \n \\varepsilon \\gt 0<\/jats:tex-math>\n <\/jats:inline-formula>\n , and (2) the first oblivious subspace embeddings for\n \n 1 \\le p \\lt 2<\/jats:tex-math>\n <\/jats:inline-formula>\n with\n \n O(1)<\/jats:tex-math>\n <\/jats:inline-formula>\n -distortion and dimension independent of\n n<\/jats:italic>\n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise\n \n \\ell _p<\/jats:tex-math>\n <\/jats:inline-formula>\n low-rank approximation. Our results give improved algorithms for these applications.\n <\/jats:p>","DOI":"10.1145\/3477537","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T09:53:03Z","timestamp":1643017983000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Tight Bounds for \u2113\n 1<\/sub>\n Oblivious Subspace Embeddings"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2148-0993","authenticated-orcid":false,"given":"Ruosong","family":"Wang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2017.7953381"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748049"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-015-0332-9"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/645413.757576"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/140963698"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884456"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688113"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746567"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/070696507"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.7146\/brics.v3i25.20006"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0473-8"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.22"},{"key":"e_1_3_3_19_2","unstructured":"Y. Li D. P. Woodruff and T. Yasuda. 2021. Exponentially improved dimensionality reduction for \\ell _1 : Subspace embeddings and independence testing. Retrieved from https:\/\/arXiv:2104.12946."},{"key":"e_1_3_3_20_2","unstructured":"M. Magdon-Ismail and A. Gittens. 2019. Fast fixed dimension L2-subspace embeddings of arbitrary accuracy with application to L1 and L2 tasks. Retrieved from https:\/\/arXiv:1909.12580."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"issue":"1","key":"e_1_3_3_22_2","first-page":"15","article-title":"A bound on the deviation probability for sums of non-negative random variables","volume":"4","author":"Maurer A.","year":"2003","unstructured":"A. Maurer. 2003. A bound on the deviation probability for sums of non-negative random variables. J. Inequal. Pure Appl. Math. 4, 1 (2003), 15.","journal-title":"J. Inequal. Pure Appl. Math."},{"key":"e_1_3_3_23_2","volume-title":"Private Communication","author":"Meng X.","year":"2019","unstructured":"X. Meng. 2019. Private Communication."},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","unstructured":"X. Meng and M. W. Mahoney. 2012. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. Retrieved from https:\/\/arXiv:1210.3135.","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488622"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_73"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52915-4"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993736"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055431"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310545"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608735"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_3_36_2","first-page":"546","volume-title":"Proceedings of the COLT","author":"Woodruff D. P.","year":"2013","unstructured":"D. P. Woodruff and Q. Zhang. 2013. Subspace embeddings and \\ell _p -regression using exponential random variables. In Proceedings of the COLT. 546\u2013567."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/130919258"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477537","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:37Z","timestamp":1750183837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,24]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3477537"],"URL":"https:\/\/doi.org\/10.1145\/3477537","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,1,24]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}