The non-convex geometry of low-rank matrix optimization
By Qiuwei Li, Zhihui Zhu, Gongguo Tang. Information and Inference A Journal of the IMA, 2016
107 citations recorded by the source corpus.
This work considers two popular minimization problems: (i) the minimization of a general convex function f(X) with the domain being positive semi-definite matrices, and (ii) the minimization of a general convex function f(X) regularized by the matrix nuclear norm $\|X\|_{*}$ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable $X = UU^{\top } $ (for semi-definite matrices) or $X=UV^{\top } $ (for general matrices) and also replace the nuclear norm $\|X\|_{*}$ with $\big(\|U\|_{F}^{2}+\|V\|_{F}^{2}\big)/2$. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local-search algorithms to find a global optimizer even with random initializations.
Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis
View Paper: https://www.semanticscholar.org/paper/95af934c408384616f53bbbe9765e6513197d489
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
In Computational Theory and Mathematics
In Numerical Analysis
Citations in the corpus
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Theorem 32 (Global landscape for rankconstrained problems [32]): Let g(·) be a convex function.”
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, background): “For low rank matrix problems, there are generalizations such as weighted matrix factorization[Li et al., 2016] and 1-bit matrix sensing[Davenport et al., 2014] where the Hessian operator may behave differently as the settings we can analyze.”
- Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “…a geometric result (all saddle points in the objective function are strict and all local minima are global minima [Ge et al., 2015, 2017b, 2016, Li et al., 2019b]), and then invokes the stable manifold theorem to show the global convergence of gradient flow [Lee et al., 2016, Panageas and…”