Optimal CUR Matrix Decompositions
This work provides improved algorithms for matrix approximation, which is a fundamental problem in numerical linear algebra and machine learning, with potential applications in data compression and dimensionality reduction.
The paper tackles the problem of efficiently computing CUR matrix decompositions that approximate a matrix with optimal error bounds, presenting algorithms that achieve input-sparsity-time and deterministic solutions with parameters c=O(k/ε) and r=O(k/ε), which are optimal up to constant factors.
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 $C U R$ approximates the matrix $A,$ that is, $ || A - CUR ||_F^2 \le (1+ε) || 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/ε)$ and $r=O(k/ε)$ and rank$(U) = k$. Up to constant factors, our algorithms are simultaneously optimal in $c, r,$ and rank$(U)$.