The Global Optimization Geometry of Low-Rank Matrix Optimization
- 5 January 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (2) , 1308-1331
Abstract
This paper considers general rank-constrained optimization problems that minimize a general objective function ${f}( {X})$ over the set of rectangular ${n}\times {m}$ matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize $ {X}$ into $ {U} {V} ^{\mathrm {T}}$ where $ {U}$ and $ {V}$ are ${n}\times {r}$ and ${m}\times {r}$ matrices, respectively, and then optimize over the small matrices $ {U}$ and $ {V}$ . We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find ${n}\times {r}$ and ${m}\times {r}$ matrices $ {U}$ and $ {V}$ such that $ {U} {V} ^{\mathrm {T}}$ approximates a given matrix $ {X}^\star $ . Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where $\mathrm {rank}( {X}^\star) = {r}$ , but also for the over-parameterization case where $\mathrm {rank}( {X}^\star) < {r}$ and the under-parameterization case where $\mathrm {rank}( {X}^\star) > {r}$ . These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.
Keywords
All Related Versions
Funding Information
- NSF (CCF-1409261, CCF-1464205, 2008460, CAREER CCF-1149225)
- DARPA Lagrange Program (N660011824020)
This publication has 30 references indexed in Scilit:
- Poisson Noise Reduction with Non-local PCAJournal of Mathematical Imaging and Vision, 2013
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- A Singular Value Thresholding Algorithm for Matrix CompletionSIAM Journal on Optimization, 2010
- Interior-Point Method for Nuclear Norm Approximation with Application to System IdentificationSIAM Journal on Matrix Analysis and Applications, 2010
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- The learnability of quantum statesProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2007
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Local Minima and Convergence in Low-Rank Semidefinite ProgrammingMathematical Programming, 2004
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003
- A Generalized Solution of the Orthogonal Procrustes ProblemPsychometrika, 1966