Revisiting the Landscape of Matrix Factorization

Prior work has shown that low-rank matrix factorization has infinitely many critical points, each of which is either a global minimum or a (strict) saddle point. We revisit this problem and provide simple, intuitive proofs of a set of extended results for low-rank and general-rank problems. We couple our investigation with a known invariant manifold M₀ of gradient flow. This restriction admits a uniform negative upper bound on the least eigenvalue of the Hessian map at all strict saddles in M₀. The bound depends on the size of the nonzero singular values and the separation between distinct singular values of the matrix to be factorized.