Optimal Column-Based Low-Rank Matrix Reconstruction

2011/04/09 by Guruswami, Venkatesan, Sinop, Ali Kemal
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.1104.1732

Abstract

We prove that for any real-valued matrix X ∈ \R^{m × 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+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^ω log 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.

Related

• Near-Optimal Column-Based Matrix Reconstruction
• Low-rank approximation in the Frobenius norm by column and row subset selection
• Regularized Weighted Low Rank Approximation
• Low-rank binary matrix approximation in column-sum norm
• Fast monte-carlo algorithms for finding low-rank approximations