Fast matrix completion without the condition number

Abstract

We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix in the running time. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.

References in corpus (2)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion

Cited by in corpus (26)

• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• A Geometric Analysis of Phase Retrieval
• Matrix Completion has No Spurious Local Minimum
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• When Are Nonconvex Problems Not Scary?
• Low Rank Phase Retrieval
• Low-tubal-rank Tensor Completion using Alternating Minimization
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Nearly-optimal Robust Matrix Completion
• Convolutional Phase Retrieval via Gradient Descent
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Matrix Completion and Related Problems via Strong Duality
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Contextual Bandits with Latent Confounders: An NMF Approach
• Tensor Graphical Model: Non-convex Optimization and Statistical Inference