# A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation

arXiv: https://arxiv.org/abs/1610.05275 · HTML: https://mlsanity.com/paper/1610.05275/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2016.

## Built on by (most cited first, 21 of 21)

- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Joint Learning of Linear Time-Invariant Dynamical Systems](https://mlsanity.com/paper/2112.10955/) (2021)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021)
- [Federated Representation Learning in the Under-Parameterized Regime](https://mlsanity.com/paper/2406.04596/) (2024)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Representational Transfer Learning for Matrix Completion](https://mlsanity.com/paper/2412.06233/) (2024)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Simultaneous inference for generalized linear models with unmeasured confounders](https://mlsanity.com/paper/2309.07261/) (2023)
- [Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates](https://mlsanity.com/paper/2201.01652/) (2022)
- [Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems](https://mlsanity.com/paper/2205.13827/) (2022)
- [Exponentially Convergent Algorithms for Supervised Matrix Factorization](https://mlsanity.com/paper/2311.11182/) (2023)
- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Supervised Dictionary Learning with Auxiliary Covariates](https://mlsanity.com/paper/2206.06774/) (2022)
- [Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses](https://mlsanity.com/paper/2403.06056/) (2024)
- [Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion](https://mlsanity.com/paper/2409.19550/) (2024)

## Abstract (arXiv)

We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observations. In the general case with noisy observations, we show that our algorithm is guaranteed to linearly converge to the unknown low-rank matrix up to minimax optimal statistical error, provided an appropriate initial estimator. While in the generic noiseless setting, our algorithm converges to the unknown low-rank matrix at a linear rate and enables exact recovery with optimal sample complexity. In addition, we develop a new initialization algorithm to provide a desired initial estimator, which outperforms existing initialization algorithms for nonconvex low-rank matrix estimation. We illustrate the superiority of our framework through three examples: matrix regression, matrix completion, and one-bit matrix completion. We also corroborate our theory through extensive experiments on synthetic data.