# Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 59 references that are in the map.
- First posted on arXiv 29 Apr 2022.

## Builds on (most cited first, 23 of 23)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization](https://mlsanity.com/paper/1706.03131/) (2017)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [A Family of Inexact SQA Methods for Non-Smooth Convex Minimization with Provable Convergence Guarantees Based on the Luo-Tseng Error Bound Property](https://mlsanity.com/paper/1605.07522/) (2016)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [Newton acceleration on manifolds identified by proximal-gradient methods](https://mlsanity.com/paper/2012.12936/) (2020)
- [Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis](https://mlsanity.com/paper/1311.6547/) (2013)
- [QSDPNAL: A two-phase augmented Lagrangian method for convex quadratic semidefinite programming](https://mlsanity.com/paper/1512.08872/) (2015)
- [Inexact Successive Quadratic Approximation for Regularized Optimization](https://mlsanity.com/paper/1803.01298/) (2018)
- [Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identification](https://mlsanity.com/paper/2012.02522/) (2020)
- [A Globally Convergent Proximal Newton-Type Method in Nonsmooth Convex Optimization](https://mlsanity.com/paper/2011.08166/) (2020)
- [Variable metric inexact line-search based methods for nonsmooth optimization](https://mlsanity.com/paper/1506.00385/) (2015)
- [Sharper Bounds for Proximal Gradient Algorithms with Errors](https://mlsanity.com/paper/2203.02204/) (2022)

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

- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization](https://mlsanity.com/paper/2406.15713/) (2024)
- [Alternating minimization for square root principal component pursuit](https://mlsanity.com/paper/2501.00471/) (2024)
- [Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximation](https://mlsanity.com/paper/2506.08535/) (2025)
- [Fast and Effective Computation of Generalized Symmetric Matrix Factorization](https://mlsanity.com/paper/2603.19147/) (2026)

## Abstract (arXiv)

This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the global optima of the original nuclear-norm-regularized problem through aperiodic inexact proximal gradient steps on it. The proposed approach adaptively adjusts the rank for the BM decomposition and can provably identify an optimal rank for the BM decomposition problem automatically in the course of optimization through tools of manifold identification. BM-Global hence also spends significantly less time on parameter tuning than existing matrix-factorization methods, which require an exhaustive search for finding this optimal rank. Extensive experiments on real-world large-scale problems of recommendation systems, regularized kernel estimation, and molecular conformation confirm that BM-Global can indeed effectively escapes spurious local minima at which existing BM approaches are stuck, and is a magnitude faster than state-of-the-art algorithms for low-rank matrix optimization problems involving a nuclear-norm regularizer. Based on this research, we have released an open-source package of the proposed BM-Global at https://www.github.com/leepei/BM-Global/.