Optimal CUR Matrix Decompositions

The CUR decomposition of an m x n matrix A finds an m x c matrix C with a small subset of c < n columns of A, together with an r x n matrix R with a small subset of r < m rows of A, as well as a c x r low rank matrix U such that the matrix CUR approximates the input matrix A, that is, 11A CUR < (1 5)11A Ak el where 11.11F denotes the Frobenius norm, 0 < s < 1 is an accuracy parameter, and Ak is the best m x 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(k/s) and r = O(k/s) and rank(U) = k. Up to constant factors, our construction is simultaneously optimal in c, r, and rank(U).