Relative-Error CUR Matrix Decompositions

By Petros Drineas, Michael W. Mahoney, S. Muthu Muthukrishnan. SIAM Journal on Matrix Analysis and Applications, 2007

546 citations recorded by the source corpus.

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\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-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-\delta$, $\|A-A'\|_F\leq(1+\epsilon)\,\|A-A_k\|_F$, where $A_k$ is the “best” 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 “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.

Subfields: Computational Mathematics, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/7ab959ec1915f63bb91dd706f6b177cef0abde84

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Subspace Embeddings for the Polynomial Kernel (2014, background): “(Theorem 5 of [6], restated) Suppose V is an n × k matrix with orthonormal columns, B ∈ Rn×m, and ∈ (0, 1].”
Low rank approximation with entrywise l1-norm error (2017, background): “, [14, 37]), in which one seeks a factorization CUR for which C is a subset of columns of A, R is a subset of rows of A, and ‖CUR −A‖ is as small as possible.”
FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting (2022, methodology): “Following the analysis in Theorem 3 from (Drineas et al., 2007), we have Using Theorem 5 from (Drineas et al., 2007), we have, with a probability at least 0 .”
An improved approximation algorithm for the column subset selection problem (2008, methodology): “Towards that end, we will use Theorem 7 of [15] with β = 1/2.”
Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems (2014, unknown): “[20, 21, 22, 23, 24].”
Fast Randomized Kernel Methods With Statistical Guarantees (2014, methodology): “See, e.g., work on CUR matrix decompositions [3, 4], work on the fast approximation of the statistical leverage scores [5], and the recent review of Randomized Linear Algebra [6] for more details.”
CUR matrix decompositions for improved data analysis (2009, background): “proof relies on matrix perturbation theory (15, 16).”
Divide-and-Conquer Matrix Factorization (2011, methodology): “1 of [6] th at will provide recovery guarantees for column projection relative to an arbitrary low-rank app roximation.”
Faster least squares approximation (2007, methodology): “Remark: In prior work [8, 9], nonuniform sampling probabilities were computed to satisfy (25) with β = 1.”
Numerical linear algebra in the streaming model (2009, background): “[13] is an approximation of a matrix A by the product of a matrix C whose columns are a subset of those of A, a matrix U , and a matrix R whose rows are a subset of those of A.”
Unsupervised feature selection for principal components analysis (2008, background): “holds with probability at least 1− 10−20, where C contains at most O(k log k/2(2)) columns of A [14, 15].”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, methodology): “Via the methods of Rudelson and Vershynin [117], they showed that sampling columns according to their leverage scores is likely to produce the required submatrix [50, 51].”
The Discrete Basis Problem (2006, background): “For more information, see [18] and references therein.”
Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “For γ = 0 , l γ j is the standard leverage score used by (Drineas, Mahoney, and Muthukrishnan 2008; Mahoney 2011).”