Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries

Abstract

We present a new, simple and computationally efficient iterative method for low rank matrix completion. Our method is inspired by the class of factorization-type iterative algorithms, but substantially differs from them in the way the problem is cast. Precisely, given a target rank $r$, instead of optimizing on the manifold of rank $r$ matrices, we allow our interim estimated matrix to have a specific over-parametrized rank $2r$ structure. Our algorithm, denoted R2RILS for rank $2r$ iterative least squares, has low memory requirements, and at each iteration it solves a computationally cheap sparse least-squares problem. We motivate our algorithm by its theoretical analysis for the simplified case of a rank-1 matrix. Empirically, R2RILS is able to recover ill conditioned low rank matrices from very few observations -- near the information limit, and it is stable to additive noise.

References in corpus (12)

• A Simpler Approach to Matrix Completion
• Recovering low-rank matrices from few coefficients in any basis
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Matrix Completion has No Spurious Local Minimum
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
• Low-rank Matrix Completion using Alternating Minimization
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Convergence of the Conjugate Gradient Method on Singular Systems

Cited by in corpus (5)

• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Truncated Matrix Completion - An Empirical Study
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points