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

arXiv2009.02905MaRDI QIDQ6348550

Christian Kümmerle, Claudio M. Verdun

Publication date: 7 September 2020

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.

Has companion code repository: https://github.com/THweinberger/specAna_matComp

This page was built for publication: Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348550)