{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T17:45:30Z","timestamp":1791913530828,"version":"4.3.4"},"reference-count":64,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of \u201ccomponents.\u201d Typically, these components are linear combinations of the rows and columns of the matrix, and are thus difficult to interpret in terms of the original features of the input data. In this paper, we propose and study matrix approximations that are explicitly expressed in terms of a small number of columns and\/or rows of the data matrix, and thereby more amenable to interpretation in terms of the original data. Our main algorithmic results are two randomized algorithms which take as input an $m\\times n$ matrix A and a rank parameter k. In our first algorithm, C is chosen, and we let $A'=CC^+A$, where $C^+$ is the Moore\u2013Penrose generalized inverse of C. In our second algorithm C, U, R are chosen, and we let $A'=CUR$. (C and R are matrices that consist of actual columns and rows, respectively, of A, and U is a generalized inverse of their intersection.) For each algorithm, we show that with probability at least $1-\\delta$, $\\|A-A'\\|_F\\leq(1+\\epsilon)\\,\\|A-A_k\\|_F$, where $A_k$ is the \u201cbest\u201d rank-k approximation provided by truncating the SVD of A, and where $\\|X\\|_F$ is the Frobenius norm of the matrix X. The number of columns of C and rows of R is a low-degree polynomial in k, $1\/\\epsilon$, and $\\log(1\/\\delta)$. Both the Numerical Linear Algebra community and the Theoretical Computer Science community have studied variants of these matrix decompositions over the last ten years. However, our two algorithms are the first polynomial time algorithms for such low-rank matrix approximations that come with relative-error guarantees; previously, in some cases, it was not even known whether such matrix decompositions exist. Both of our algorithms are simple and they take time of the order needed to approximately compute the top k singular vectors of A. The technical crux of our analysis is a novel, intuitive sampling method we introduce in this paper called \u201csubspace sampling.\u201d In subspace sampling, the sampling probabilities depend on the Euclidean norms of the rows of the top singular vectors. This allows us to obtain provable relative-error guarantees by deconvoluting \u201csubspace\u201d information and \u201csize-of-A\u201d information in the input matrix. This technique is likely to be useful for other matrix approximation and data analysis problems.<\/jats:p>","DOI":"10.1137\/07070471x","type":"journal-article","created":{"date-parts":[[2008,9,18]],"date-time":"2008-09-18T10:32:23Z","timestamp":1221733943000},"page":"844-881","source":"Crossref","is-referenced-by-count":295,"title":["Relative-Error $CUR$ Matrix Decompositions"],"prefix":"10.1137","volume":"30","author":[{"given":"Petros","family":"Drineas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,9,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and F. McSherry,\n                      Fast computation of low rank matrix approximations\n                      , J. ACM, 54 (2007).","DOI":"10.1145\/1219092.1219097"},{"key":"R2","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, pp. 611\u20136181.","DOI":"10.1145\/380752.380858"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan,\n                      Geometric approximation via coresets survey\n                      , in Current Trends in Combinatorial and Computational Geometry, E. Welzl, ed., Cambridge University Press, Cambridge, 2006.","DOI":"10.1017\/9781009701259.002"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"N. Ailon and B. Chazelle,\n                      Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 557\u2013563.","DOI":"10.1145\/1132516.1132597"},{"key":"R6","unstructured":"A. Ben-Israel and T. N. E. Greville,\n                      Generalized Inverses: Theory and Applications\n                      , Springer-Verlag, New York, 2003."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Y. Bengio, J. F. Paiement, P. Vincent, O. Delalleau, N. Le Roux, and M. Ouimet,\n                      Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering\n                      , in Annual Advances in Neural Information Processing Systems 16: Proceedings of the 2003 Conference, 2004, pp. 177\u2013184.","DOI":"10.1162\/0899766041732396"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/1067967.1067972"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. Bhatia,\n                      Matrix Analysis\n                      , Springer-Verlag, New York, 1997.","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436084"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0911029"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0913043"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Charikar, V. Guruswami, R. Kumar, S. Rajagopalan, and A. Sahai,\n                      Combinatorial feature selection problems\n                      , in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 631\u2013642.","DOI":"10.1109\/SFCS.2000.892331"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1038\/nature04226"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Dasgupta, P. Drineas, B. Harb, V. Josifovski, and M. W. Mahoney,\n                      Feature selection methods for text classification\n                      , in Proceedings of the 13th Annual ACM SIGKDD Conference, 2007, pp. 230\u2013239.","DOI":"10.1145\/1281192.1281220"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Deshpande, L. Rademacher, S. Vempala, and G. Wang,\n                      Matrix approximation and projective clustering via volume sampling\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1117\u20131126.","DOI":"10.1145\/1109557.1109681"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Deshpande and S. Vempala,\n                      Adaptive sampling and fast low-rank matrix approximation\n                      , Technical report TR06-042, Electronic Colloquium on Computational Complexity, 2006.","DOI":"10.1007\/11830924_28"},{"key":"R19","unstructured":"P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay,\n                      Clustering in large graphs and matrices\n                      , in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 291\u2013299."},{"key":"R20","unstructured":"P. Drineas and R. Kannan,\n                      Pass efficient algorithms for approximating large matrices\n                      , in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 223\u2013232."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442702"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"P. Drineas and M. W. Mahoney,\n                      Approximating a Gram matrix for improved kernel-based learning\n                      , in Proceedings of the 18th Annual Conference on Learning Theory, 2005, pp. 323\u2013337.","DOI":"10.1007\/11503415_22"},{"key":"R25","first-page":"2153","volume":"6","author":"Drineas P.","year":"2005","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.08.023"},{"key":"R27","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan,\n                      Polynomial time algorithm for column-row based relative-error low-rank matrix approximation\n                      , manuscript, 2005."},{"key":"R28","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan,\n                      Polynomial time algorithm for column-row based relative-error low-rank matrix approximation\n                      , Technical report 2006-04, DIMACS, 2006."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan,\n                      Sampling algorithms for $\\ell_2$ regression and applications\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1127\u20131136.","DOI":"10.1145\/1109557.1109682"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan,\n                      Subspace sampling and relative-error matrix approximation: Column-based methods\n                      , in Proceedings of the 10th International Workshop on Randomization and Computation, 2006, pp. 316\u2013326.","DOI":"10.1007\/11830924_30"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan,\n                      Subspace sampling and relative-error matrix approximation: Column-row-based methods\n                      , in Proceedings of the 14th Annual European Symposium on Algorithms, 2006, pp. 304\u2013314.","DOI":"10.1007\/11841036_29"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262185"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"A. Frieze, R. Kannan, and S. Vempala,\n                      Fast Monte-Carlo algorithms for finding low-rank approximations\n                      , in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 370\u2013378.","DOI":"10.1109\/SFCS.1998.743487"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011419012209"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436075"},{"key":"R37","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , Johns Hopkins University Press, Baltimore, 1996."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/280\/4620"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00301-1"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"R41","first-page":"1157","volume":"3","author":"Guyon I.","year":"2003","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R42","unstructured":"S. Har-Peled,\n                      Low rank matrix approximation in linear time\n                      , manuscript, 2006."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, New York, 1985.","DOI":"10.1017\/CBO9780511810817"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2002-3-3-research0011"},{"key":"R45","unstructured":"S. Lafon,\n                      Diffusion Maps and Geometric Harmonics\n                      , Ph.D. thesis, Yale University, 2004."},{"key":"R46","first-page":"361","volume":"5","author":"Lewis D. D.","year":"2004","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1086\/425587"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"M. W. Mahoney, M. Maggioni, and P. Drineas,\n                      Tensor-CUR decompositions for tensor-based data\n                      , in Proceedings of the 12th Annual ACM SIGKDD Conference, 2006, pp. 327\u2013336.","DOI":"10.1145\/1150402.1150440"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"P.G. Martinsson, V. Rokhlin, and M. Tygert,\n                      A randomized algorithm for the approximation of matrices\n                      , Technical report YALEU\/DCS\/TR-1361, Yale University Department of Computer Science, New Haven, CT, 2006.","DOI":"10.21236\/ADA458927"},{"key":"R50","unstructured":"M. Z. Nashed, ed.\n                      Generalized Inverses and Applications\n                      , Academic Press, New York, 1976."},{"key":"R51","doi-asserted-by":"crossref","unstructured":"B. N. Parlett,\n                      The Symmetric Eigenvalue Problem\n                      , Classics in Applied Mathematics, SIAM, Philadelphia, 1998.","DOI":"10.1137\/1.9781611971163"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1101\/gr.5741407"},{"key":"R53","unstructured":"L. Rademacher, S. Vempala, and G. Wang,\n                      Matrix approximation and projective clustering via iterative sampling\n                      , Technical report MIT-LCS-TR-983, Massachusetts Institute of Technology, Cambridge, MA, 2005."},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1998.3384"},{"key":"R55","unstructured":"M. Rudelson and R. Vershynin,\n                      Approximation of matrices\n                      , manuscript."},{"key":"R56","doi-asserted-by":"crossref","unstructured":"M. Rudelson and R. Vershynin,\n                      Sampling from large matrices: An approach through geometric functional analysis\n                      , J. ACM, 54 (2007).","DOI":"10.1145\/1255443.1255449"},{"key":"R57","doi-asserted-by":"crossref","unstructured":"T. Sarl\u00f3s,\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, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050451"},{"key":"R59","unstructured":"G. W. Stewart,\n                      Error analysis of the quasi-Gram-Schmidt algorithm\n                      , Technical report UMIACS TR-2004-17 CMSC TR-4572, University of Maryland, College Park, MD, 2004."},{"key":"R60","unstructured":"G. W. Stewart and J. G. Sun,\n                      Matrix Perturbation Theory\n                      , Academic Press, New York, 1990."},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1007\/s006070070031"},{"key":"R62","unstructured":"R. Vershynin,\n                      Coordinate restrictions of linear operators in $l_2^n$\n                      , manuscript."},{"key":"R63","unstructured":"C. K. I. Williams, C. E. Rasmussen, A. Schwaighofer, and V. Tresp,\n                      Observations on the Nystr\u00f6m method for Gaussian process prediction\n                      , Technical report, University of Edinburgh, 2002."},{"key":"R64","unstructured":"C. K. I. Williams and M. Seeger,\n                      Using the Nystr\u00f6m method to speed up kernel machines\n                      , in Annual Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference, 2002, pp. 682\u2013688."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/07070471X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:36:10Z","timestamp":1787333770000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/07070471X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/07070471X"],"URL":"https:\/\/doi.org\/10.1137\/07070471x","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}