Optimal CUR Matrix Decompositions

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