OPTIMAL CUR MATRIX DECOMPOSITIONS

The CUR decomposition of an m x n matrix A finds an m x c matrix C with a subset of c < n columns of A, together with an r x n matrix R with a 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 matrix A, that is, parallel to A - CUR parallel to(2)(F) <= (1 + epsilon) parallel to A - A(k) parallel to(2)(F), where parallel to.parallel to(F) denotes the Frobenius norm and A(k) is the best m x n matrix of rank k constructed via the SVD. We present input-sparsity-time and deterministic algorithms for constructing such a CUR decomposition where c = O(k/epsilon) and r = O(k/epsilon) and rank(U) = k. Up to constant factors, our algorithms are simultaneously optimal in the values c, r, and rank(U).