{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T15:21:54Z","timestamp":1783610514042,"version":"3.55.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"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":["J. ACM"],"published-print":{"date-parts":[[2007,4]]},"abstract":"<jats:p>\n            Given a matrix\n            <jats:italic>A<\/jats:italic>\n            , it is often desirable to find a good approximation to\n            <jats:italic>A<\/jats:italic>\n            that has low rank. We introduce a simple technique for accelerating the computation of such approximations when\n            <jats:italic>A<\/jats:italic>\n            has strong spectral features, that is, when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to\n            <jats:italic>A<\/jats:italic>\n            . Our technique amounts to independently sampling and\/or quantizing the entries of\n            <jats:italic>A<\/jats:italic>\n            , thus speeding up computation by reducing the number of nonzero entries and\/or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix\n            <jats:italic>N<\/jats:italic>\n            to\n            <jats:italic>A<\/jats:italic>\n            , whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability,\n            <jats:italic>N<\/jats:italic>\n            has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to\n            <jats:italic>A<\/jats:italic>\n            +\n            <jats:italic>N<\/jats:italic>\n            is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm.\n          <\/jats:p>","DOI":"10.1145\/1219092.1219097","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":146,"title":["Fast computation of low-rank matrix approximations"],"prefix":"10.1145","volume":"54","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[{"name":"University of California at Santa Cruz, Santa Cruz, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Mcsherry","sequence":"additional","affiliation":[{"name":"Microsoft Research, Mountain View, California"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785860"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380859"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.598228"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598347035"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1037127"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th Annual Symposium on Discrete Algorithms","author":"Drineas P."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.927464"},{"key":"e_1_2_1_12_1","unstructured":"Golub G. and Van Loan C. 1996. Matrix computations 3rd ed. Johns Hopkins University Press Baltimore MD.   Golub G. and Van Loan C. 1996. Matrix computations 3rd ed. Johns Hopkins University Press Baltimore MD."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1711"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060654"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219097","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1219092.1219097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:42Z","timestamp":1750278162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1219092.1219097"],"URL":"https:\/\/doi.org\/10.1145\/1219092.1219097","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}