Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation

Abstract

We propose practical algorithms for entrywise ${\ell }_p$-norm low-rank approximation, for $p=1$ or $p=\infty$. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approximations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain $(1+\epsilon )$-OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desiderata only assuming algorithm's hyperparameters are known a priori---or are at least approximable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46].

16 pages, 11 figures, to appear in UAI 2018

References in corpus (9)

• Matrix Completion has No Spurious Local Minimum
• Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
• Low-Rank Matrix Approximation in the Infinity Norm
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Provable quantum state tomography via non-convex methods
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Matrix ALPS: Accelerated Low Rank and Sparse Matrix Reconstruction
• Algorithms for ${\ell }_p$ Low Rank Approximation
• Bipartite Correlation Clustering -- Maximizing Agreements

Cited by in corpus (2)

• Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
• Learning regularization and intensity-gradient-based fidelity for single image super resolution