# Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably

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

## Key facts

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

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

- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [Exponentially Convergent Algorithms for Supervised Matrix Factorization](https://mlsanity.com/paper/2311.11182/) (2023)
- [A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints](https://mlsanity.com/paper/2501.13830/) (2025)
- [Local Stochastic Factored Gradient Descent for Distributed Quantum State Tomography](https://mlsanity.com/paper/2203.11579/) (2022)
- [Supervised Dictionary Learning with Auxiliary Covariates](https://mlsanity.com/paper/2206.06774/) (2022)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Knowledge-Embedded Latent Projection for Robust Representation Learning](https://mlsanity.com/paper/2602.16709/) (2026)
- [Rethinking the Rank Threshold for LoRA Fine-Tuning](https://mlsanity.com/paper/2605.03724/) (2026)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [ODELoRA: Training Low-Rank Adaptation by Solving Ordinary Differential Equations](https://mlsanity.com/paper/2602.07479/) (2026)
- [Sparse Network Inference under Imperfect Detection and its Application to Ecological Networks](https://mlsanity.com/paper/2604.18820/) (2026)
- [AdaPaD: Adaptive Parallel Deflation for PEFT with Self-Correcting Rank Discovery](https://mlsanity.com/paper/2605.10741/) (2026)
- [A Block Tensor Train Burer-Monteiro Framework for Low-Rank Quantum State Tomography](https://mlsanity.com/paper/2609.09457/) (2026)

## Abstract (arXiv)

A rank-r matrix X ∈ ℝm × n can be written as a product U V^top, where U ∈ ℝm × r and V ∈ ℝn × r. One could exploit this observation in optimization: e.g., consider the minimization of a convex function f(X) over rank-r matrices, where the set of rank-r matrices is modeled via the factorization UV^top. Though such parameterization reduces the number of variables, and is more computationally efficient (of particular interest is the case r ll minm, n), it comes at a cost: f(UV^top) becomes a non-convex function w.r.t. U and V. We study such parameterization for optimization of generic convex objectives f, and focus on first-order, gradient descent algorithmic solutions. We propose the Bi-Factored Gradient Descent (BFGD) algorithm, an efficient first-order method that operates on the U, V factors. We show that when f is (restricted) smooth, BFGD has local sublinear convergence, and linear convergence when f is both (restricted) smooth and (restricted) strongly convex. For several key applications, we provide simple and efficient initialization schemes that provide approximate solutions good enough for the above convergence results to hold.