Optimal Column-Based Low-Rank Matrix Reconstruction

الأصل · EN

We prove that for any real-valued matrix X ∈ ᵐ × ⁿ, and positive integers r ≥ k, there is a subset of r columns of X such that projecting X onto their span gives a √r+1/r-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(r n mω m) arithmetic operations where ω is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in O(r n m²) arithmetic operations.