{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T17:57:14Z","timestamp":1794592634973,"version":"4.9.1"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Math. Anal."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Consider an $m \\times N$ matrix $\\Phi$ with the restricted isometry property of order k and level $\\delta$; that is, the norm of any k-sparse vector in $\\mathbb{R}^N$ is preserved to within a multiplicative factor of $1 \\pm \\delta$ under application of $\\Phi$. We show that by randomizing the column signs of such a matrix $\\Phi$, the resulting map with high probability embeds any fixed set of $p = O(e^k)$ points in $\\mathbb{R}^N$ into $\\mathbb{R}^m$ without distorting the norm of any point in the set by more than a factor of $1 \\pm 4 \\delta$. Consequently, matrices with the restricted isometry property and with randomized column signs provide optimal Johnson\u2013Lindenstrauss embeddings up to logarithmic factors in N. In particular, our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices; for partial Fourier and partial Hadamard matrices, we improve the recent bound $m \\gtrsim \\delta^{-4} \\log(p) \\log^4(N)$ given by Ailon and Liberty to $m \\gtrsim \\delta^{-2} \\log(p) \\log^4(N)$, which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries.<\/jats:p>","DOI":"10.1137\/100810447","type":"journal-article","created":{"date-parts":[[2011,5,26]],"date-time":"2011-05-26T18:14:30Z","timestamp":1306433670000},"page":"1269-1281","source":"Crossref","is-referenced-by-count":181,"title":["New and Improved Johnson\u2013Lindenstrauss Embeddings via the Restricted Isometry Property"],"prefix":"10.1137","volume":"43","author":[{"given":"Felix","family":"Krahmer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rachel","family":"Ward","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,5,26]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Ailon and B. Chazelle,\n                      Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform\n                      , in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, 2006, pp. 557\u2013563.","DOI":"10.1145\/1132516.1132597"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Ailon and E. Liberty,\n                      An almost optimal unrestricted fast Johnson-Lindenstrauss transform\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), SIAM, Philadelphia, 2011, pp. 185\u2013191.","DOI":"10.1137\/1.9781611973082.17"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"N. Ailon and E. Liberty,\n                      Fast dimension reduction using Rademacher series on dual BCH codes\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), SIAM, Philadelphia, 2008, pp. 1\u20139.","DOI":"10.21236\/ADA471857"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Ailon, E. Liberty, and A. Singer,\n                      Dense fast random projections and Lean Walsh transforms\n                      , in Proceedings of the Twelfth International Workshop on Randomization and Computation (RANDOM), 2008, pp. 512\u2013522.","DOI":"10.1007\/978-3-540-85363-3_40"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-007-9011-z"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1055425791"},{"key":"R9","unstructured":"J. Bourgain, S. Dilworth, K. Ford, S. Konyagin, and D. Kutzarova,\n                      Explicit constructions of RIP matrices and related problems\n                      , Duke Math. J., to appear."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.10.002"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Dasgupta, R. Kumar, and T. Sarlos,\n                      A sparse Johnson-Lindenstrauss transform\n                      , in Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 341\u2013350.","DOI":"10.1145\/1806689.1806737"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.04.002"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"T. Do, L. Gan, Y. Chen, N. Nguyen, and T. Tran,\n                      Fast and efficient dimensionality reduction using structurally random matrices\n                      , in Proceedings of the 2009 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2009, pp. 1821\u20131824.","DOI":"10.1109\/ICASSP.2009.4959960"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20132"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.10.004"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2010.04.004"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90043-3"},{"key":"R22","first-page":"1048","volume":"277","author":"Garnaev A.","year":"1984","journal-title":"Dokl. Akad. Nauk SSSR","ISSN":"https:\/\/id.crossref.org\/issn\/0002-3264","issn-type":"print"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177693335"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"P. Indyk,\n                      Algorithmic applications of low-distortion embeddings\n                      , in Proceedings of the Forty-Second IEEE Symposium on Foundations of Computer Science (FOCS), 2001, p. 10.","DOI":"10.1109\/SFCS.2001.959878"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"M. Iwen,\n                      Simple deterministically constructible RIP matrices with sublinear Fourier sampling requirements\n                      , in Proceedings of the Forty-Third Annual Conference on Information Sciences and Systems (CISS 2009), 2009, pp. 870\u2013875.","DOI":"10.1109\/CISS.2009.5054839"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"R29","unstructured":"D. Kane and J. Nelson,\n                      A Derandomized Sparse Johnson-Lindenstrauss Transform\n                      , Preprint, 2010."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"R31","unstructured":"H. Rauhut,\n                      Circulant and Toeplitz matrices in compressed sensing\n                      , in Proceedings of the Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS'09), Saint-Malo, France, 2009."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"H. Rauhut,\n                      Compressive sensing and structured random matrices\n                      , in Theoretical Foundations and Numerical Methods for Sparse Recovery, M. Fornasier, ed., Radon Series Comp. Appl. Math. 9, de Gruyter, 2010, pp. 1\u201392.","DOI":"10.1515\/9783110226157.1"},{"key":"R33","unstructured":"H. Rauhut, J. Romberg, and J. Tropp,\n                      Restricted isometries for partial random circulant matrices\n                      , Appl. Comput. Harmon. Anal., to appear."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"H. Rauhut and R. Ward,\n                      Sparse Legendre Expansions via $\\ell_1$ Minimization\n                      , Preprint, 2010.","DOI":"10.1109\/CISS.2010.5464911"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/08072975X"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20227"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"T. Sarlos,\n                      Improved approximation algorithms for large matrices via random projections\n                      , in Proceedings of the Forty-Seventh IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2034811"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2010.11.014"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2032712"}],"container-title":["SIAM Journal on Mathematical Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100810447","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:44:26Z","timestamp":1787316266000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100810447"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100810447"],"URL":"https:\/\/doi.org\/10.1137\/100810447","relation":{},"ISSN":["0036-1410","1095-7154"],"issn-type":[{"value":"0036-1410","type":"print"},{"value":"1095-7154","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}