{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T04:42:06Z","timestamp":1744605726212},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_73","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"883-894","source":"Crossref","is-referenced-by-count":9,"title":["Lower Bounds for Oblivious Subspace Embeddings"],"prefix":"10.1007","author":[{"given":"Jelani","family":"Nelson","sequence":"first","affiliation":[]},{"given":"Huy L.","family":"Nguy\u00ea\u0303n","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"73_CR1","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.\u00a039(1), 302\u2013322 (2009)","journal-title":"SIAM J. Comput."},{"key":"73_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nguy\n                    \n                      \n                    \n                    $\\tilde{\\hat{\\mbox{e}}}$\n                  n, H. L.: Eigenvalues of a matrix in the streaming model. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1729\u20131737 (2013)","DOI":"10.1137\/1.9781611973105.124"},{"key":"73_CR3","unstructured":"Boutsidis, C., Zouzias, A., Mahoney, M.W., Drineas, P.: Stochastic dimensionality reduction for k-means clustering. CoRR, abs\/1110.2897 (2011)"},{"key":"73_CR4","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Woodruff, D.P.: Numerical linear algebra in the streaming model. In: Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), pp. 205\u2013214 (2009)","DOI":"10.1145\/1536414.1536445"},{"key":"73_CR5","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Woodruff, D.P.: Low rank approximation and regression in input sparsity time. In: Proceedings of the 45th ACM Symposium on Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488620"},{"issue":"1","key":"73_CR6","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\u00a022(1), 60\u201365 (2003)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"73_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00211-007-0114-x","volume":"108","author":"J. Demmel","year":"2007","unstructured":"Demmel, J., Dumitriu, I., Holtz, O.: Fast linear algebra is stable. Numer. Math.\u00a0108(1), 59\u201391 (2007)","journal-title":"Numer. Math."},{"issue":"3","key":"73_CR8","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1214\/aoms\/1177693335","volume":"42","author":"D.L. Hanson","year":"1971","unstructured":"Hanson, D.L., Wright, F.T.: A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist.\u00a042(3), 1079\u20131083 (1971)","journal-title":"Ann. Math. Statist."},{"key":"73_CR9","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"73_CR10","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Meka, R., Nelson, J.: Almost optimal explicit Johnson-Lindenstrauss transformations. In: Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM), pp. 628\u2013639 (2011)","DOI":"10.1007\/978-3-642-22935-0_53"},{"key":"73_CR11","unstructured":"Mahoney, M.W., Drineas, P., Magdon-Ismail, M., Woodruff, D.P.: Fast approximation of matrix coherence and statistical leverage. In: Proceedings of the 29th International Conference on Machine Learning, ICML (2012)"},{"key":"73_CR12","doi-asserted-by":"crossref","unstructured":"Meng, X., Mahoney, M.W.: Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In: Proceedings of the 45th ACM Symposium on Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488621"},{"key":"73_CR13","doi-asserted-by":"crossref","unstructured":"Molinaro, M., Woodruff, D.P., Yaroslavtsev, G.: Beating the direct sum theorem in communication complexity with implications for sketching. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1738\u20131756 (2013)","DOI":"10.1137\/1.9781611973105.125"},{"key":"73_CR14","doi-asserted-by":"crossref","unstructured":"Nelson, J., Nguy\n                    \n                      \n                    \n                    $\\tilde{\\hat{\\mbox{e}}}$\n                  n, H.L.: OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2013)","DOI":"10.1109\/FOCS.2013.21"},{"key":"73_CR15","doi-asserted-by":"crossref","unstructured":"Nelson, J., Nguy\n                    \n                      \n                    \n                    $\\tilde{\\hat{\\mbox{e}}}$\n                  n, H.L.: Sparsity lower bounds for dimensionality-reducing maps. In: Proceedings of the 45th ACM Symposium on Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488622"},{"key":"73_CR16","doi-asserted-by":"crossref","unstructured":"Paul, S., Boutsidis, C., Magdon-Ismail, M., Drineas, P.: Random projections for support vector machines. In: AISTATS (2013)","DOI":"10.1145\/2641760"},{"key":"73_CR17","doi-asserted-by":"crossref","unstructured":"Sarl\u00f3s, T.: Improved approximation algorithms for large matrices via random projections. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143\u2013152 (2006)","DOI":"10.1109\/FOCS.2006.37"},{"key":"73_CR18","doi-asserted-by":"crossref","unstructured":"Tao, T.: Topics in random matrix theory. Graduate Studies in Mathematics, vol.\u00a0132. American Mathematical Society (2012)","DOI":"10.1090\/gsm\/132"},{"issue":"9","key":"73_CR19","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1109\/32.92917","volume":"17","author":"M.D. Vose","year":"1991","unstructured":"Vose, M.D.: A linear algorithm for generating random numbers with a given distribution. IEEE Transactions on Software Engineering\u00a017(9), 972\u2013975 (1991)","journal-title":"IEEE Transactions on Software Engineering"},{"key":"73_CR20","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"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-662-43948-7_73","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:21:07Z","timestamp":1558923667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}