{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:27:25Z","timestamp":1787329645868,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["810367"],"award-info":[{"award-number":["810367"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We introduce a Generalized LU Factorization (GLU) for low-rank matrix approximation. We relate this to past approaches and extensively analyze its approximation properties. The established deterministic guarantees are combined with sketching ensembles satisfying Johnson\u2013Lindenstrauss properties to present complete bounds. Particularly good performance is shown for the subsampled randomized Hadamard transform (SRHT) ensemble. Moreover, the factorization is shown to unify and generalize many past algorithms, sometimes providing strictly better approximations. It also helps to explain the effect of sketching on the growth factor during Gaussian elimination.<\/jats:p>","DOI":"10.1137\/21m1391316","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T14:57:10Z","timestamp":1683817030000},"page":"559-591","source":"Crossref","is-referenced-by-count":6,"title":["An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation"],"prefix":"10.1137","volume":"44","author":[{"given":"James","family":"Demmel","sequence":"first","affiliation":[{"name":"Department of Mathematics, Computer Science, UC Berkeley, Berkeley, CA 94720 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Grigori","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, Inria, CNRS Universit\u00e9 de Paris, Laboratoire Jacques-Louis Lions, Paris, 75005 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3420-3490","authenticated-orcid":false,"given":"Alexander","family":"Rusciano","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, Inria, CNRS Universit\u00e9 de Paris, Laboratoire Jacques-Louis Lions, Paris, 75005 France."},{"name":"Department of Mathematics, UC Berkeley, Berkeley, CA 94709 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"ref1","first-page":"135","volume-title":"Proceedings of VECPAR 2014","author":"Baboulin M.","year":"2014"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050264"},{"key":"ref3","unstructured":"G. Ballard , \nJ. Demmel , \nI. Dumitriu , and \nA. Rusciano , A Generalized Rank-Revealing Factorization, preprint, https:\/\/arxiv.org\/abs\/arXiv:1909.06524v1, 2019."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/120874540"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/0126013"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/040616413"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"M. B. Cohen , \nS. Elder , \nC. Musco , \nC. Musco , and \nM. Persu , Dimensionality reduction for k-means clustering and low rank approximation, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC \u201915, ACM, New York, 2015, pp. 163\u2013172, https:\/\/doi.org\/10.1145\/2746539.2746569.","DOI":"10.1145\/2746539.2746569"},{"key":"ref9","unstructured":"M. B. Cohen , \nJ. Nelson , and \nD. P. Woodruff , Optimal approximate matrix product in terms of stable rank, in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Vol. 55, 2016, 11, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.11."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971446"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0114-x"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1063\/1.4748969"},{"key":"ref13","first-page":"3977","volume":"17","author":"Gittens A.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/16M1074527"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/130938700"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref18","volume-title":"Matrix Analysis","author":"Horn R. A.","year":"2013","edition":"2"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0376-5"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/120863691"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015957395"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"M. W. Mahoney  and \nP. Drineas , CUR matrix decompositions for improved data analysis, Proc. Natl. Acad. Sci. USA, 106 (2009), pp. 697\u2013702.","DOI":"10.1073\/pnas.0803205106"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00572-4"},{"key":"ref25","unstructured":"C. Musco  and \nC. Musco , Randomized block Krylov methods for stronger and faster approximate singular value decomposition, in Proceedings of the 28th International Conference on Neural Information Processing Systems, Vol. 1, NIPS\u201915, MIT Press, Cambridge, MA, 2015, pp. 1396\u20131404."},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"C. Musco  and \nD. P. Woodruff , Sublinear time low-rank approximation of positive semidefinite matrices, in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Washington, DC, 2017, pp. 672\u2013683, https:\/\/doi.org\/10.1109\/FOCS.2017.68.","DOI":"10.1109\/FOCS.2017.68"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"J. Nelson  and \nH. L. Nguyen , OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2013, pp. 117\u2013126, https:\/\/doi.org\/10.1109\/FOCS.2013.21.","DOI":"10.1109\/FOCS.2013.21"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436202"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"T. Sarlos , Improved approximation algorithms for large matrices via random projections, in Proceedings of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), IEEE, Washington, DC, 2006, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2016.04.006"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/0611023"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111590"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1391316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:26:14Z","timestamp":1787325974000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1391316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,11]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M1391316"],"URL":"https:\/\/doi.org\/10.1137\/21m1391316","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,11]]}}}