Optimal Column-Based Low-Rank Matrix Reconstruction

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

paper · pdf · doi:10.48550/arxiv.1104.1732

8 pages

arxiv created 2012/01/04 · arxiv updated 2015/03/18

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.

Cited by

• Guessing Efficiently for Constrained Subspace Approximation

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