Optimal cur matrix decompositions

The CUR decomposition of an m × n matrix A finds an m × c matrix C with a subset of c < n columns of A, together with an r × n matrix R with a subset of r < m rows of A, as well as a c × r low-rank matrix U such that the matrix CUR approximates the matrix A, that is, ∥A-CUR∥2 F ≤ (1 + ϵ) ∥A-Ak∥2 F, where ∥. ∥F denotes the Frobenius norm and Ak is the best m × 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/ϵ) and r = O(k/ϵ) and rank(U) = k. Up to constant factors, our algorithms are simultaneously optimal in the values c, r, and rank(U).