Guaranteed Matrix Completion via Non-convex Factorization

Abstract

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization can be solved very efficiently by standard algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of this formulation. In this paper, we establish a theoretical guarantee for the factorization formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization formulation, and recover the true low-rank matrix. We study the local geometry of a properly regularized factorization formulation and prove that any stationary point in a certain local region is globally optimal. A major difference of our work from the existing results is that we do not need resampling in either the algorithm or its analysis. Compared to other works on nonconvex optimization, one extra difficulty lies in analyzing nonconvex constrained optimization when the constraint (or the corresponding regularizer) is not "consistent" with the gradient direction. One technical contribution is the perturbation analysis for non-symmetric matrix factorization.

77 pages. Accepted to IEEE Transaction on Information theory. A detailed description of the proof ideas is added, compared to version 2

References in corpus (13)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
• Non-convex Robust PCA
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Fast matrix completion without the condition number
• Statistical guarantees for the EM algorithm: From population to sample-based analysis
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Fast Exact Matrix Completion with Finite Samples

Cited by in corpus (124)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• 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
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Optimization for deep learning: theory and algorithms
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• When Are Nonconvex Problems Not Scary?
• The Numerics of Phase Retrieval
• Robust Matrix Completion via Maximum Correntropy Criterion and Half Quadratic Optimization
• The Non-convex Geometry of Low-rank Matrix Optimization
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Improving Fairness for Data Valuation in Horizontal Federated Learning
• Fast Low-Rank Bayesian Matrix Completion with Hierarchical Gaussian Prior Models
• Low-tubal-rank Tensor Completion using Alternating Minimization
• On exponential convergence of SGD in non-convex over-parametrized learning
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Dropping Convexity for Faster Semi-definite Optimization
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Stochastic dynamical modeling of turbulent flows
• Latent Function Decomposition for Forecasting Li-ion Battery Cells Capacity: A Multi-Output Convolved Gaussian Process Approach
• Nonconvex Demixing From Bilinear Measurements
• Complete Dictionary Recovery over the Sphere
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Hyperspectral Super-Resolution via Global-Local Low-Rank Matrix Estimation
• Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Matrix completion with deterministic pattern - a geometric perspective
• Matrix Completion with Deterministic Sampling: Theories and Methods
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Composite optimization for robust blind deconvolution
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Convolutional Phase Retrieval via Gradient Descent
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• Quartic First-Order Methods for Low-Rank Minimization
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning
• On Asymptotic Linear Convergence Rate of Iterative Hard Thresholding for Matrix Completion
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• Inference for Heteroskedastic PCA with Missing Data
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Nonconvex Robust Low-rank Matrix Recovery
• Entropy Penalized Semidefinite Programming
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning
• Fast Convergence for Langevin Diffusion with Manifold Structure
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• The nonsmooth landscape of blind deconvolution
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps
• Riemannian Perspective on Matrix Factorization
• Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Escaping Saddle Points with the Successive Convex Approximation Algorithm
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Global Optimality in Distributed Low-rank Matrix Factorization
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information
• Matrix Completion via Nonconvex Regularization: Convergence of the Proximal Gradient Algorithm
• A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• Implicit Regularization in Matrix Sensing via Mirror Descent
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• A Non-monotone Alternating Updating Method for A Class of Matrix Factorization Problems
• Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise
• Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing
• Discrete-Aware Matrix Completion via Proximal Gradient
• Submodular + Concave
• On Recovering the Best Rank-r Approximation from Few Entries
• The Sparse Reverse of Principal Component Analysis for Fast Low-Rank Matrix Completion
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• Provable Low Rank Phase Retrieval
• Online high rank matrix completion
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• One-dimensional System Arising in Stochastic Gradient Descent
• Learning Mixtures of Low-Rank Models
• Continuous-time Models for Stochastic Optimization Algorithms