Efficient CUR Matrix Decomposition via Relative-Error Double-Sided Least Squares Solving

摘要

Matrix CUR decomposition aims at representing a large matrix $A$ with the product $Ccdot Ucdot R$, where $C$ (resp. $R)$ consists of a small collection of the original columns (resp. rows), and $U$ is a small intermediate matrix connecting $C$ and $R$. While modern randomized CUR algorithms have provided many efficient methods of choosing representative columns and rows, there hasn't been a method to find the optimal U matrix. In this paper, we present a sublinear-time randomized method to find good choices of the $U$ matrix. Our proposed algorithm treats the task of finding $U$ as a double-sided least squares problem $minolimits_{Z}Vert A - CZR Vert_{F}$, and is able to guarantee a close-to-optimal solution by solving a down-sampled problem of much smaller size. We provide worst-case analysis on its approximation error relative to theoretical optimal low-rank approximation error, and we demonstrate empirically how this method can improve the approximation of several large-scale real data matrices with a small number of additional computations.