The Landscape of Matrix Factorization Revisited
Preprint
Abstract
We revisit the landscape of the simple matrix factorization problem. For low-rank matrix factorization, prior work has shown that there exist infinitely many critical points all of which are either global minima or strict saddles. At a strict saddle the minimum eigenvalue of the Hessian is negative. Of interest is whether this minimum eigenvalue is uniformly bounded below zero over all strict saddles. To answer this we consider orbits of critical points under the general linear group. For each orbit we identify a representative point, called a canonical point. If a canonical point is a strict saddle, so is every point on its orbit. We derive an expression for the minimum eigenvalue of the Hessian at each canonical strict saddle and use this to show that the minimum eigenvalue of the Hessian over the set of strict saddles is not uniformly bounded below zero. We also show that a known invariance property of gradient flow ensures the solution of gradient flow only encounters critical points on an invariant manifold $\mathcal{M}_C$ determined by the initial condition. We show that, in contrast to the general situation, the minimum eigenvalue of strict saddles in $\mathcal{M}_{0}$ is uniformly bounded below zero. We obtain an expression for this bound in terms of the singular values of the matrix being factorized. This bound depends on the size of the nonzero singular values and on the separation between distinct nonzero singular values of the matrix.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix FactorizationIEEE Transactions on Information Theory, 2019
- A Geometric Analysis of Phase RetrievalFoundations of Computational Mathematics, 2017
- Canonical Correlation Analysis: An Overview with Application to Learning MethodsNeural Computation, 2004
- Independent component analysis: algorithms and applicationsNeural Networks, 2000
- Positive matrix factorization: A non‐negative factor model with optimal utilization of error estimates of data valuesEnvironmetrics, 1994
- Neural networks and principal component analysis: Learning from examples without local minimaNeural Networks, 1989
- Relations Between Two Sets of VariatesBiometrika, 1936
- Analysis of a complex of statistical variables into principal components.Journal of Educational Psychology, 1933