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 - C U R\|F² ≤ (1+ε) \|A - Aₖ\|F², where \|.\|F denotes the Frobenius norm and Aₖ 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)$.