# Geometry of Factored Nuclear Norm Regularization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2017.

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

- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [Exact Sparse Orthogonal Dictionary Learning](https://mlsanity.com/paper/2103.09085/) (2021)

## Abstract (arXiv)

This work investigates the geometry of a nonconvex reformulation of minimizing a general convex loss function f(X) regularized by the matrix nuclear norm |X|_*. Nuclear-norm regularized matrix inverse problems are at the heart of many applications in machine learning, signal processing, and control. The statistical performance of nuclear norm regularization has been studied extensively in literature using convex analysis techniques. Despite its optimal performance, the resulting optimization has high computational complexity when solved using standard or even tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer-Monteiro to factor the matrix variable X into the product of two smaller rectangular matrices X=UVT and also replace the nuclear norm |X|_* with (|U|F2+|V|F2)/2. In spite of the nonconvexity of the factored formulation, we prove that when the convex loss function f(X) is (2r,4r)-restricted well-conditioned, each critical point of the factored problem either corresponds to the optimal solution X^star of the original convex optimization or is a strict saddle point where the Hessian matrix has a strictly negative eigenvalue. Such a geometric structure of the factored formulation allows many local search algorithms to converge to the global optimum with random initializations.