{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:31:50Z","timestamp":1779294710592,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>\n            A low-rank approximation to a matrix\n            <jats:italic>A<\/jats:italic>\n            is a matrix with significantly smaller rank than\n            <jats:italic>A<\/jats:italic>\n            , and which is close to\n            <jats:italic>A<\/jats:italic>\n            according to some norm. Many practical applications involving the use of large matrices focus on low-rank approximations. By reducing the rank or dimensionality of the data, we reduce the complexity of analyzing the data. The singular value decomposition is the most popular low-rank matrix approximation. However, due to its expensive computational requirements, it has often been considered intractable for practical applications involving massive data. Recent developments have tried to address this problem, with several methods proposed to approximate the decomposition with better asymptotic runtime. We present an empirical study of these techniques on a variety of dense and sparse datasets. We find that a sampling approach of Drineas, Kannan and Mahoney is often, but not always, the best performing method. This method gives solutions with high accuracy much faster than classical SVD algorithms, on large sparse datasets in particular. Other modern methods, such as a recent algorithm by Rokhlin and Tygert, also offer savings compared to classical SVD algorithms. The older sampling methods of Achlioptas and McSherry are shown to sometimes take longer than classical SVD.\n          <\/jats:p>","DOI":"10.1145\/1921632.1921639","type":"journal-article","created":{"date-parts":[[2011,3,3]],"date-time":"2011-03-03T08:44:26Z","timestamp":1299141866000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":58,"title":["Fast Algorithms for Approximating the Singular Value Decomposition"],"prefix":"10.1145","volume":"5","author":[{"given":"Aditya Krishna","family":"Menon","sequence":"first","affiliation":[{"name":"University of California, San Diego"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles","family":"Elkan","sequence":"additional","affiliation":[{"name":"University of California, San Diego"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380858"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219097"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Ailon N."},{"key":"e_1_2_1_4_1","unstructured":"Anderson E. Bai Z. Bischof C. Demmel J. Dongarra J. Croz J. D. Greenbaum A. Hammarling S. McKenney A. Ostrouchov S. and Sorensen D. 1992. LAPACK User\u2019s Guide. SIAM Philadelphia PA. Anderson E. Bai Z. Bischof C. Demmel J. Dongarra J. Croz J. D. Greenbaum A. Hammarling S. McKenney A. Ostrouchov S. and Sorensen D. 1992. LAPACK User\u2019s Guide . SIAM Philadelphia PA."},{"key":"e_1_2_1_5_1","volume-title":"Notre Dame Mathematical Lectures","volume":"2","author":"Artin E.","year":"1942"},{"key":"e_1_2_1_6_1","unstructured":"AT&amp;T Laboratories Cambridge. 2002. The database of Faces. http:\/\/www.cl.cam.ac.uk\/research\/dtg\/attarchive\/facedatabase.html. (Accessed 5\/08). AT&amp;T Laboratories Cambridge . 2002. The database of Faces. http:\/\/www.cl.cam.ac.uk\/research\/dtg\/attarchive\/facedatabase.html. (Accessed 5\/08)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Berry M. Mezher D. Bernard P. and Sameh A. 2005. Handbook of Parallel Computing and Statistics. Chapman &amp; Hall\/CRC 117--164. Berry M. Mezher D. Bernard P. and Sameh A. 2005. Handbook of Parallel Computing and Statistics . Chapman &amp; Hall\/CRC 117--164.","DOI":"10.1201\/9781420028683.ch4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355990"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_28"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Panhellenic Conference on Informatics. 279--296","author":"Drineas P."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"e_1_2_1_15_1","unstructured":"Duff I. Grimes R. and Lewis J. 1998. Harwell-Boeing collection. http:\/\/math.nist.gov\/MatrixMarket\/collections\/hb.html. Duff I. Grimes R. and Lewis J. 1998. Harwell-Boeing collection. http:\/\/math.nist.gov\/MatrixMarket\/collections\/hb.html."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288367"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956812"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS\u201998)","author":"Frieze A."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62437.62487"},{"key":"e_1_2_1_20_1","unstructured":"Golub G. H. and Van Loan C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press Baltimore MD. Golub G. H. and Van Loan C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press Baltimore MD."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference of the European Chapter of the Association for Computer Linguistics (EACL).","author":"Gorrell G.","year":"2006"},{"key":"e_1_2_1_22_1","unstructured":"Har-Peled S. 2006. Low rank matrix approximation in linear time. http:\/\/valis.cs.uiuc.edu\/ sariel\/papers\/05\/lrank. Har-Peled S. 2006. Low rank matrix approximation in linear time. http:\/\/valis.cs.uiuc.edu\/ sariel\/papers\/05\/lrank."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Horn R. and Johnson C. 1991. Topics in Matrix Analysis. Cambridge University Press. Horn R. and Johnson C. 1991. Topics in Matrix Analysis . Cambridge University Press.","DOI":"10.1017\/CBO9780511840371"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Jolliffe I. 1986. Principal Component Analysis. Springer New York NY. Jolliffe I. 1986. Principal Component Analysis . Springer New York NY.","DOI":"10.1007\/978-1-4757-1904-8"},{"key":"e_1_2_1_25_1","unstructured":"Larsen R. M. 2005. PROPACK. http:\/\/sun.stanford.edu\/ rmunk\/PROPACK\/. Larsen R. M. 2005. PROPACK. http:\/\/sun.stanford.edu\/ rmunk\/PROPACK\/."},{"key":"e_1_2_1_26_1","unstructured":"Lewis D. D. 2004. Reuters-21578 text categorization test collection. http:\/\/www.daviddlewis.com\/resources\/testcollections\/reuters21578\/. Lewis D. D. 2004. Reuters-21578 text categorization test collection. http:\/\/www.daviddlewis.com\/resources\/testcollections\/reuters21578\/."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/11.1.50"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536446"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275505"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275505"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of KDD Cup and Workshop.","author":"Paterek A.","year":"2007"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736417"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining (SDM).","author":"Sun J."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.v1:1"},{"key":"e_1_2_1_37_1","unstructured":"Thomas G. 2007. Fast Walsh-Hadamard transform. http:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/6879. Thomas G. 2007. Fast Walsh-Hadamard transform. http:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/6879."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 6th International Conference on Optimization: Techniques and Applications.","author":"Tjahyadi R."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1162\/jocn.1991.3.1.71"},{"key":"e_1_2_1_40_1","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume":"65","author":"Vempala S. S.","year":"2004"},{"key":"e_1_2_1_41_1","unstructured":"Yarlagadda R. K. and Hershey J. E. 1997. Hadamard Matrix Analysis and Synthesis: With Applications to Communications and Signal\/Image Processing. Kluwer Academic Publishers. Yarlagadda R. K. and Hershey J. E. 1997. Hadamard Matrix Analysis and Synthesis: With Applications to Communications and Signal\/Image Processing . Kluwer Academic Publishers."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899359631"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921632.1921639","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921632.1921639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921632.1921639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1145\/1921632.1921639"],"URL":"https:\/\/doi.org\/10.1145\/1921632.1921639","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2]]},"assertion":[{"value":"2010-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}