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

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(\mu r^2{\kappa }^{2}n\max (\mu ,\log n))$ random observations of a $n_1\times n_2$ $\mu$-incoherent matrix of rank $r$ and condition number $\kappa$, where $n=\max (n_1,n_2)$, the algorithm linearly converges to the global optimum with high probability.

References in corpus (11)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Manopt, a Matlab toolbox for optimization on manifolds
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Incoherence-Optimal Matrix Completion
• Estimation of low-rank tensors via convex optimization
• Fast Algorithms for Robust PCA via Gradient Descent
• Fast matrix completion without the condition number
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
• Dropping Convexity for Faster Semi-definite Optimization
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion

Cited by in corpus (55)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• How to Escape Saddle Points Efficiently
• 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
• Matrix Completion has No Spurious Local Minimum
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Exploiting Shared Representations for Personalized Federated Learning
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• Fast Low Rank column-wise Compressive Sensing for Accelerated Dynamic MRI
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Blind Super-resolution of Point Sources via Projected Gradient Descent
• Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication
• Matrix Completion from $O(n)$ Samples in Linear Time
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• On the computational and statistical complexity of over-parameterized matrix sensing
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Inference for Heteroskedastic PCA with Missing Data
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Matrix Completion and Related Problems via Strong Duality
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Spectral Compressed Sensing via Projected Gradient Descent
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Implicit Regularization in Matrix Sensing via Mirror Descent
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Dynamic Matrix Recovery
• Robust spectral compressive sensing via vanilla gradient descent
• Pebbles, Graphs, and a Pinch of Combinatorics: Towards Tight I/O Lower Bounds for Statically Analyzable Programs
• Online Tensor Inference
• On the analysis of optimization with fixed-rank matrices: a quotient geometric view