Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent

2016/05/23 by Qinqing Zheng, John Lafferty, Zheng, Qinqing +1 · 9 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Numerical methods in inverse problems #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1605.07051

openalex publication_date 2016/05/23 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With O( μr² κ² n max(μ, log n)) random observations of a n₁ × n₂ μ-incoherent matrix of rank r and condition number κ, where n = max(n₁, n₂), the algorithm linearly converges to the global optimum with high probability.

Citations

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

Cited by

• Spectral Compressed Sensing via Projected Gradient Descent
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Matrix Completion from O(n) Samples in Linear Time
• Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completion
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis

Related

• Nonconvex Rectangular Matrix Completion via Gradient Descent without ℓ_2,∞ Regularization
• Nonconvex Deterministic Matrix Completion by Projected Gradient Descent Methods
• Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization
• Matrix Completion via Nonconvex Regularization: Convergence of the Proximal Gradient Algorithm
• Matrix Completion has No Spurious Local Minimum