Optimal Column-Based Low-Rank Matrix Reconstruction Venkatesan Guruswami Ali Kemal Sinop 10.1184/R1/6608099.v1 https://kilthub.cmu.edu/articles/journal_contribution/Optimal_Column-Based_Low-Rank_Matrix_Reconstruction/6608099 <p>We prove that for any real-valued matrix $X \in \R^{m \times n}$, and positive integers r≥k, there is a subset of r columns of X such that projecting X onto their span gives a r+1r−k+1−−−−−√-approximation to best rank-k approximation of X in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in O(rnmωlogm) arithmetic operations where ω is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in O(rnm2) arithmetic operations.</p> 1973-01-01 00:00:00 computer sciences