Optimal CUR matrix decompositions

Abstract

The CUR decomposition of an m × n matrix A finds an m × c matrix C with a small subset of c < n columns of A; together with an r × n matrix R with a small subset of r < m rows of A; as well as a c × r low rank matrix U such that the matrix CUR approximates the input matrix A; that is, k∥A - CUR∥ F2 ≤ (1 +ε)∥A - Aκ∥ F2; where ∥·∥F denotes the Frobenius norm, 0 < ε < 1 is an accuracy parameter, and Aκ is the best m × n matrix of rank k constructed via the SVD of A. We present input-sparsity-time and deterministic algorithms for constructing such a CUR matrix decomposition of A where c = O(κ=ε) and r = O(κ=ε) and rank(U) = κ. Up to constant factors, our construction is simultaneously optimal in c; r; and rank(U). © 2014 ACM.