Answers are grounded in this paper and cite their sources.
Computational study demonstrates quadratic convergence in ill-conditioned matrix completion from few samples, indicating superior scalability over existing methods.
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 10¹⁰ from few samples, while being competitive in its scalability.
No takes yet. Share an insight, caveat, or question.
Kümmerle et al. (2021) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: