Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method

Abstract

We propose an iterative algorithm for low-rank matrix completion that can be interpreted as both an iteratively reweighted least squares (IRLS) algorithm and a saddle-escaping smoothing Newton method applied to a non-convex rank surrogate objective. It combines the favorable data efficiency of previous IRLS approaches with an improved scalability by several orders of magnitude. Our method attains a local quadratic convergence rate already for a number of samples that is close to the information theoretical limit. We show in numerical experiments that unlike many state-of-the-art approaches, our approach is able to complete very ill-conditioned matrices with a condition number of up to $10^{10}$ from few samples.

15 pages, presented at the Workshop on "Beyond first-order methods in ML systems" at the $37^{t}h$ International Conference on Machine Learning (ICML), Vienna, Austria, 2020

References in corpus (9)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Manopt, a Matlab toolbox for optimization on manifolds
• A Simpler Approach to Matrix Completion
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Operator-Lipschitz estimates for the singular value functional calculus
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries

Cited by in corpus (1)

• Truncated Matrix Completion - An Empirical Study