2017/05/18 by Flavio Chierichetti, Sreenivas Gollapudi, Chierichetti, Flavio +10 · 5 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Approximation algorithm #Approximation error #Combinatorics #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Eigenvalues and eigenvectors #FOS: Computer and information sciences #Low-rank approximation #Mathematics #Matrix (chemical analysis) #Physics #Pure mathematics #Quantum mechanics #Rank (graph theory) #Simple (philosophy) #Singular value #Singular value decomposition #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications #Work (physics) #cs.DS
paper · pdf · doi:10.48550/arxiv.1705.06730
published in arXiv (Cornell University), 806-814 (Cornell University) · To appear in ICML
arxiv created 2017/05/18 · openalex publication_date 2017/05/18 · arxiv updated 2017/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entrywise ℓp-approximation error, for any p ≥ 1; the case p = 2 is the classical SVD problem. We obtain the first provably good approximation algorithms for this version of low-rank approximation that work for every value of p ≥ 1, including p = ∞. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.