{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T11:50:36Z","timestamp":1789645836979,"version":"4.0.0"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-12-C0323"],"award-info":[{"award-number":["FA8750-12-C0323"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1443046"],"award-info":[{"award-number":["ACI-1443046"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1350888"],"award-info":[{"award-number":["CCF-1350888"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1251019"],"award-info":[{"award-number":["IIS-1251019"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>We describe a new algorithm called FrequentDirections for deterministic matrix sketching in the row-update model. The algorithm is presented an arbitrary input matrix A \\in \\mathbb{R}^{n \\times d} one row at a time. It performs O(d\\ell) operations per row and maintains a sketch matrix B \\in \\mathbb{R}^{\\ell \\times d} such that for any k &lt; \\ell, \\|A^TA - B^TB \\|_2 \\leq \\|A - A_k\\|_F^2 \/ (\\ell-k) {\\;and\\;} \\|A - \\pi_{B_k}(A)\\|_F^2 \\leq (1 + \\frac{k}{\\ell-k}) \\|A-A_k\\|_F^2. Here, A_k stands for the minimizer of \\|A - A_k\\|_F over all rank k matrices (similarly for B_k) and \\pi_{B_k}(A) is the rank k matrix resulting from projecting A on the row span of B_k. We show that both of these bounds are the best possible for the space allowed. The summary is mergeable and hence trivially parallelizable. Moreover, FrequentDirections outperforms exemplar implementations of existing streaming algorithms in the space-error tradeoff. This paper combines, simplifies, and extends the results of Liberty [Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013], Ghashami and Phillips [Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014], and Woodruff [Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems, 2014].<\/jats:p>","DOI":"10.1137\/15m1009718","type":"journal-article","created":{"date-parts":[[2016,9,15]],"date-time":"2016-09-15T12:09:47Z","timestamp":1473941387000},"page":"1762-1792","source":"Crossref","is-referenced-by-count":87,"title":["Frequent Directions: Simple and Deterministic Matrix Sketching"],"prefix":"10.1137","volume":"45","author":[{"given":"Mina","family":"Ghashami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edo","family":"Liberty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,9,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.10.004"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"D. Achlioptas,\n                      Database-friendly random projections\n                      , in Proceedings of the 20th ACM Symposium on Principles of Database Systems, 2001, http:\/\/dx.doi.org\/10.1016\/S0022-0000(03)00025-4 doi:10.1016\/S0022-0000(03)00025-4.","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"atypb3","unstructured":"D. Achlioptas, Z. S. Karnin, and E. Liberty,\n                      Near-optimal entrywise sampling for data matrices\n                      , in Proceedings of the 27th Annual Conference on Neural Information Processing Systems, 2013, pp. 1565-1573."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and F. McSherry,\n                      Fast computation of low rank matrix approximations\n                      , in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, http:\/\/dx.doi.org\/10.1145\/1219092.1219097 doi:10. 1145\/1219092.1219097.","DOI":"10.1145\/1219092.1219097"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/18.985947"},{"key":"atypb7","first-page":"272","author":"Arora S.","year":"2006","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"R. Berinde, G. Cormode, P. Indyk, and M. J. Strauss,\n                      Space-optimal heavy hitters with strong error bounds\n                      , in Proceedings of the ACM Symposium on Principals of Database Systems, 2009, http:\/\/dx.doi.org\/10.1145\/1862919.1862923 doi:10.1145\/1862919.1862923.","DOI":"10.1145\/1559795.1559819"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"C. Boutsidis, P. Drineas, and M. Magdon-Ismail,\n                      Near optimal column-based matrix reconstruction\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 2011, http:\/\/dx.doi.org\/10.1137\/12086755X doi:10.1137\/12086755X.","DOI":"10.1109\/FOCS.2011.21"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.105"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Brand,\n                      Incremental singular value decomposition of uncertain data with missing values\n                      , in Proceedings of the 7th European Conference on Computer Vision, 2002, http:\/\/dx.doi.org\/10.1007\/3-540-47969-4_47 doi:10.1007\/ 3-540-47969-4_47.","DOI":"10.1007\/3-540-47969-4_47"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"M. Charikar, K. Chen, and M. Farach-Colton,\n                      Finding frequent items in data streams\n                      , in Proceedings of the International Conference on Automata, Languages, and Programming, 2002, http:\/\/dx.doi.org\/10.14778\/1454159.1454225 doi:10.14778\/1454159.1454225.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and D. P. Woodruff,\n                      Numerical linear algebra in the streaming model\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, http:\/\/dx.doi.org\/10.1145\/1536414.1536445 doi:10. 1145\/1536414.1536445.","DOI":"10.1145\/1536414.1536445"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and D. P. Woodruff,\n                      Low rank approximation and regression in input sparsity time\n                      , in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 2013, http:\/\/dx.doi.org\/10.1145\/2488608.2488620 doi:10.1145\/2488608.2488620.","DOI":"10.1145\/2488608.2488620"},{"key":"atypb15","unstructured":"M. B. Cohen, C. Musco, and C. Musco,\n                      Ridge Leverage Scores for Low-Rank Approximation\n                      , preprint, http:\/\/arxiv.org\/abs\/1511.07263 arXiv:1511.07263, 2015."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"T. M. Cover and J. Thomas,\n                      Elements of Information Theory\n                      , Wiley, New York, 1991, http:\/\/dx.doi.org\/10.1002\/047174882X doi: 10.1002\/047174882X.","DOI":"10.1002\/047174882X"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"A. Dasgupta, R. Kumar, and T. Sarl\u00f3s,\n                      A sparse Johnson-Lindenstrauss transform\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, http:\/\/dx.doi.org\/10.1145\/1806689.1806737 doi:10.1145\/ 1806689.1806737.","DOI":"10.1145\/1806689.1806737"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"E. D. Demaine, A. L\u00f3pez-Ortiz, and J. I. Munro,\n                      Frequency estimation of internet packet streams with limited space\n                      , in Proceedings of the European Symposium on Algorithms, 2002, http:\/\/dx.doi.org\/10.1007\/3-540-45749-6_33 doi:10.1007\/3-540-45749-6_33.","DOI":"10.1007\/3-540-45749-6_33"},{"key":"atypb19","first-page":"292","author":"Deshpande A.","year":"2006","journal-title":"Berlin"},{"key":"atypb20","first-page":"223","author":"Drineas P.","year":"2003","journal-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"atypb22","first-page":"3475","volume":"13","author":"Drineas P.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.01.010"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.103"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"M. Ghashami, A. Desai, and J. M. Phillips,\n                      Improved practical matrix sketching with guarantees\n                      , in Proceedings of the 22nd Annual Symposium on Algorithms, 2014, http:\/\/dx.doi.org\/10.1109\/TKDE.2016.2539943 doi:10.1109\/ TKDE.2016.2539943.","DOI":"10.1109\/TKDE.2016.2539943"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.53"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons and Y. Matias,\n                      Synopsis data structures for massive data sets\n                      , in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999.","DOI":"10.1090\/dimacs\/050\/02"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"L. Golab, D. DeHaan, E. D. Demaine, A. Lopez-Ortiz, and J. I. Munro,\n                      Identifying frequent items in sliding windows over on-line packet streams\n                      , in Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement, 2003, http:\/\/dx.doi.org\/10.1145\/948205.948227 doi:10.1145\/948205.948227.","DOI":"10.1145\/948224.948227"},{"key":"atypb32","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , Vol. 3, The Johns Hopkins University Press, Baltimore, MD, 2012."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"P. Hall, D. Marshall, and R. Martin,\n                      Incremental eigenanalysis for classification\n                      , in Proceedings of the British Machine Vision Conference, 1998, http:\/\/dx.doi.org\/10.5244\/C.12.29 doi:10.5244\/C.12.29.","DOI":"10.5244\/C.12.29"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.94"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.101"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan,\n                      Communication Complexity\n                      , Cambridge University Press, Cambridge, UK, 1997, http:\/\/dx.doi.org\/10.1017\/CBO9780511574948 doi:10.1017\/CBO9780511574948.","DOI":"10.1017\/CBO9780511574948"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/83.855432"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"E. Liberty,\n                      Simple and deterministic matrix sketching\n                      , in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013, http:\/\/dx.doi.org\/10.1145\/2487575.2487623 doi:10. 1145\/2487575.2487623.","DOI":"10.1145\/2487575.2487623"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"R. Lidl and H. Niederreiter,\n                      Introduction to Finite Fields and Their Applications\n                      , Cambridge University Press, Cambridge, UK, 1986, http:\/\/dx.doi.org\/10.1017\/CBO9781139172769 doi:10.1017\/CBO9781139172769.","DOI":"10.1017\/CBO9781139172769"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v15-1544"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, H. Tamaki, P. Raghavan, and S. Vempala,\n                      Latent semantic indexing: A probabilistic analysis\n                      , in Proceedings of the 17th ACM Symposium on Principles of Database Systems, 1998, http:\/\/dx.doi.org\/10.1006\/jcss.2000.1711 doi:10.1006\/jcss.2000.1711.","DOI":"10.1006\/jcss.2000.1711"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0075-7"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"M. Rudelson and R. Vershynin,\n                      Non-asymptotic theory of random matrices: Extreme singular values\n                      , in Proceedings of the International Congress of Mathematics, 2010, http:\/\/dx.doi.org\/10.1142\/9789814324359_0111 doi:10. 1142\/9789814324359_0111.","DOI":"10.1142\/9789814324359_0111"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"T. Sarlos,\n                      Improved approximation algorithms for large matrices via random projections\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, http:\/\/dx.doi.org\/10.1109\/FOCS.2006.37 doi:10.1109\/FOCS.2006.37.","DOI":"10.1109\/FOCS.2006.37"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"S. S. Vempala,\n                      The Random Projection Method\n                      , American Mathematical Society, Providence, RI, 2004, http:\/\/dx.doi.org\/10.1145\/1189056.1189066 doi:10.1145\/1189056.1189066.","DOI":"10.1145\/1189056.1189066"},{"key":"atypb53","unstructured":"R. Vershynin,\n                      A note on sums of independent random matrices after Ahlswede-Winter\n                      , Lecture Notes, 2009."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-010-0281-z"},{"key":"atypb55","unstructured":"C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie,\n                      The Caltech-UCSD Birds-200-2011 Dataset\n                      , Computation & Neural Systems Technical Report, CNS-TR-2011-001, 2011; available online from \u016dlhttp:\/\/www.vision.caltech.edu\/visipedia\/CUB-200-2011.html."},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"K. Weinberger, A. Dasgupta, J. Langford, A. Smola, and J. Attenberg,\n                      Feature hashing for large scale multitask learning\n                      , in Proceedings of the 26th Annual International Conference on Machine Learning, 2009, http:\/\/dx.doi.org\/10.1145\/1553374.1553516 doi:10.1145\/1553374.1553516.","DOI":"10.1145\/1553374.1553516"},{"key":"atypb57","unstructured":"D. P. Woodruff,\n                      Low rank approximation lower bounds in row-update streams\n                      , in Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems, 2014."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1009718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:58Z","timestamp":1787336278000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1009718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/15M1009718"],"URL":"https:\/\/doi.org\/10.1137\/15m1009718","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}