The Landscape of Matrix Factorization Revisited
  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.
