TY - JOUR
T1 - Relative-error cur matrix decompositions
AU - Drineas, Petros
AU - Mahoney, Michael W.
AU - Muthukrishnan, S.
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of "components." 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 × n matrix A and a rank parameter κ. In our first algorithm, C is chosen, and we let A'=CC +A, where C + is the Moore-Penrose 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-δ, \\A-A'|| F ≤ (1 + ∈) ||A-A k|| f, where A k is the "best" rank-κ 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 κ, 1/∈, and log(1/δ). 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 κ singular vectors of A. The technical crux of our analysis is a novel, intuitive sampling method we introduce in this paper called "subspace sampling." 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 "subspace" information and "size-of-A" information in the input matrix. This technique is likely to be useful for other matrix approximation and data analysis problems.
AB - Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of "components." 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 × n matrix A and a rank parameter κ. In our first algorithm, C is chosen, and we let A'=CC +A, where C + is the Moore-Penrose 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-δ, \\A-A'|| F ≤ (1 + ∈) ||A-A k|| f, where A k is the "best" rank-κ 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 κ, 1/∈, and log(1/δ). 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 κ singular vectors of A. The technical crux of our analysis is a novel, intuitive sampling method we introduce in this paper called "subspace sampling." 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 "subspace" information and "size-of-A" information in the input matrix. This technique is likely to be useful for other matrix approximation and data analysis problems.
KW - Approximate least squares
KW - CUR matrix decomposition
KW - Data analysis
KW - Random sampling algorithms
UR - http://www.scopus.com/inward/record.url?scp=58849107202&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58849107202&partnerID=8YFLogxK
U2 - 10.1137/07070471X
DO - 10.1137/07070471X
M3 - Article
AN - SCOPUS:58849107202
SN - 0895-4798
VL - 30
SP - 844
EP - 881
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
IS - 2
ER -