{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:37:23Z","timestamp":1770741443689,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001732","name":"Danmarks Grundforskningsfond","doi-asserted-by":"publisher","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002739","name":"Aarhus Universitets Forskningsfond","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002739","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-019-00644-y","type":"journal-article","created":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T14:03:41Z","timestamp":1572617021000},"page":"338-354","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Using Toeplitz and Circulant Matrices for Johnson\u2013Lindenstrauss Transforms"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5651-1617","authenticated-orcid":false,"given":"Casper Benjamin","family":"Freksen","sequence":"first","affiliation":[]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,1]]},"reference":[{"issue":"4","key":"644_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson\u2013Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671\u2013687 (2003). \nhttps:\/\/doi.org\/10.1016\/S0022-0000(03)00025-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"644_CR2","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"N Ailon","year":"2009","unstructured":"Ailon, N., Chazelle, B.: The fast Johnson\u2013Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39(1), 302\u2013322 (2009). \nhttps:\/\/doi.org\/10.1137\/060673096","journal-title":"SIAM J. Comput."},{"issue":"4","key":"644_CR3","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00454-008-9110-x","volume":"42","author":"N Ailon","year":"2009","unstructured":"Ailon, N., Liberty, E.: Fast dimension reduction using Rademacher series on dual BCH codes. Discrete Comput. Geom. 42(4), 615\u2013630 (2009). \nhttps:\/\/doi.org\/10.1007\/s00454-008-9110-x","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"644_CR4","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2483699.2483701","volume":"9","author":"N Ailon","year":"2013","unstructured":"Ailon, N., Liberty, E.: An almost optimal unrestricted fast Johnson\u2013Lindenstrauss transform. ACM Trans. Algorithms 9(3), 21:1\u201321:12 (2013). \nhttps:\/\/doi.org\/10.1145\/2483699.2483701","journal-title":"ACM Trans. Algorithms"},{"key":"644_CR5","doi-asserted-by":"publisher","unstructured":"Blocki, J., Blum, A., Datta, A., Sheffet, O.: The Johnson\u2013Lindenstrauss transform itself preserves differential privacy. In: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS \u201912, pp. 410\u2013419. IEEE Computer Society, Washington, DC (2012). \nhttps:\/\/doi.org\/10.1109\/FOCS.2012.67","DOI":"10.1109\/FOCS.2012.67"},{"issue":"2","key":"644_CR6","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1109\/TIT.2014.2375327","volume":"61","author":"C Boutsidis","year":"2015","unstructured":"Boutsidis, C., Zouzias, A., Mahoney, M.W., Drineas, P.: Randomized dimensionality reduction for $$k$$-means clustering. IEEE Trans. Inf. Theory 61(2), 1045\u20131062 (2015). \nhttps:\/\/doi.org\/10.1109\/TIT.2014.2375327","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"644_CR7","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"EJ Candes","year":"2006","unstructured":"Candes, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489\u2013509 (2006). \nhttps:\/\/doi.org\/10.1109\/TIT.2005.862083","journal-title":"IEEE Trans. Inf. Theory"},{"key":"644_CR8","doi-asserted-by":"publisher","unstructured":"Cohen, M.B., Elder, S., Musco, C., Musco, C., Persu, M.: Dimensionality reduction for $$k$$-means clustering and low rank approximation. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC \u201915, pp. 163\u2013172. ACM, New York (2015). \nhttps:\/\/doi.org\/10.1145\/2746539.2746569","DOI":"10.1145\/2746539.2746569"},{"key":"644_CR9","doi-asserted-by":"publisher","unstructured":"Dasgupta, A., Kumar, R., Sarlos, T.: A sparse Johnson\u2013Lindenstrauss transform. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC \u201910, pp. 341\u2013350. ACM, New York (2010). \nhttps:\/\/doi.org\/10.1145\/1806689.1806737","DOI":"10.1145\/1806689.1806737"},{"issue":"1","key":"644_CR10","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2003). \nhttps:\/\/doi.org\/10.1002\/rsa.10073","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"644_CR11","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006). \nhttps:\/\/doi.org\/10.1109\/TIT.2006.871582","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"14","key":"644_CR12","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput 8(14), 321\u2013350 (2012). \nhttps:\/\/doi.org\/10.4086\/toc.2012.v008a014","journal-title":"Theory Comput"},{"issue":"3","key":"644_CR13","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1002\/rsa.20360","volume":"39","author":"A Hinrichs","year":"2011","unstructured":"Hinrichs, A., Vyb\u00edral, J.: Johnson\u2013Lindenstrauss lemma for circulant matrices. Random Struct. Algorithms 39(3), 391\u2013398 (2011). \nhttps:\/\/doi.org\/10.1002\/rsa.20360","journal-title":"Random Struct. Algorithms"},{"key":"644_CR14","doi-asserted-by":"publisher","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS \u201901, pp. 10\u201333. IEEE Computer Society, Washington, DC (2001). \nhttps:\/\/doi.org\/10.1109\/SFCS.2001.959878","DOI":"10.1109\/SFCS.2001.959878"},{"key":"644_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"WB Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26, 189\u2013206 (1984). \nhttps:\/\/doi.org\/10.1090\/conm\/026\/737400","journal-title":"Contemp. Math."},{"issue":"1","key":"644_CR16","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2559902","volume":"61","author":"DM Kane","year":"2014","unstructured":"Kane, D.M., Nelson, J.: Sparser Johnson\u2013Lindenstrauss transforms. J. ACM 61(1), 4:1\u20134:23 (2014). \nhttps:\/\/doi.org\/10.1145\/2559902","journal-title":"J. ACM"},{"issue":"3","key":"644_CR17","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1137\/100810447","volume":"43","author":"F Krahmer","year":"2011","unstructured":"Krahmer, F., Ward, R.: New and improved Johnson\u2013Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal. 43(3), 1269\u20131281 (2011)","journal-title":"SIAM J. Math. Anal."},{"key":"644_CR18","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Nelson, J.: Optimality of the Johnson\u2013Lindenstrauss lemma. In: Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS \u201917. IEEE Computer Society, Washington, DC (2017)","DOI":"10.1109\/FOCS.2017.64"},{"key":"644_CR19","doi-asserted-by":"publisher","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. In: Foundations and Trends\u2122 in Theoretical Computer Science, vol. 1, no 2. Publishers Inc., Hanover (2005). \nhttps:\/\/doi.org\/10.1561\/0400000002","DOI":"10.1561\/0400000002"},{"issue":"6","key":"644_CR20","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913\u20131926 (2011). \nhttps:\/\/doi.org\/10.1137\/080734029","journal-title":"SIAM J. Comput."},{"key":"644_CR21","doi-asserted-by":"publisher","unstructured":"Vempala, S.S.: The random projection method. In: DIMACS\u2014Series in Discrete Mathematics and Theoretical Computer Science, vol. 65. American Mathematical Society, Providence (2004). \nhttps:\/\/doi.org\/10.1007\/978-1-4615-0013-1_16","DOI":"10.1007\/978-1-4615-0013-1_16"},{"key":"644_CR22","unstructured":"Vu, K., Poirion, P.L., Liberti, L.: Using the Johnson\u2013Lindenstrauss lemma in linear and integer programming. ArXiv e-prints (2015)"},{"issue":"4","key":"644_CR23","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.jfa.2010.11.014","volume":"260","author":"J Vyb\u00edral","year":"2011","unstructured":"Vyb\u00edral, J.: A variant of the Johnson\u2013Lindenstrauss lemma for circulant matrices. J. Funct. Anal. 260(4), 1096\u20131105 (2011). \nhttps:\/\/doi.org\/10.1016\/j.jfa.2010.11.014","journal-title":"J. Funct. Anal."},{"key":"644_CR24","doi-asserted-by":"publisher","unstructured":"Weinberger, K., Dasgupta, A., Langford, J., Smola, A., Attenberg, J.: Feature hashing for large scale multitask learning. In: Proceedings of the 26th Annual International Conference on Machine Learning, ICML \u201909, pp. 1113\u20131120. ACM, New York (2009). \nhttps:\/\/doi.org\/10.1145\/1553374.1553516","DOI":"10.1145\/1553374.1553516"},{"key":"644_CR25","doi-asserted-by":"publisher","unstructured":"Woodruff, D.P.: Sketching as a tool for numerical linear algebra. In: Foundations and Trends\u2122 in Theoretical Computer Science, vol. 10, no 1\u20132. Publishers Inc., Hanover (2014). \nhttps:\/\/doi.org\/10.1561\/0400000060","DOI":"10.1561\/0400000060"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00644-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00644-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00644-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T00:10:11Z","timestamp":1604103011000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00644-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["644"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00644-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,1]]},"assertion":[{"value":"15 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}