A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples

Author name not available (Why is that?)

Publication date: 3 June 2021

Abstract: We propose an iterative algorithm for low-rank matrix completion that can be interpreted as an iteratively reweighted least squares (IRLS) algorithm, a saddle-escaping smoothing Newton method or a variable metric proximal gradient method applied to a non-convex rank surrogate. It combines the favorable data-efficiency of previous IRLS approaches with an improved scalability by several orders of magnitude. We establish the first local convergence guarantee from a minimal number of samples for that class of algorithms, showing that the method attains a local quadratic convergence rate. Furthermore, we show that the linear systems to be solved are well-conditioned even for very ill-conditioned ground truth matrices. We provide extensive experiments, indicating that unlike many state-of-the-art approaches, our method is able to complete very ill-conditioned matrices with a condition number of up to

1 0^{10}

from few samples, while being competitive in its scalability.

Has companion code repository: https://github.com/ckuemmerle/MatrixIRLS

This page was built for publication: A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples

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