Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points

Abstract

We study over-parametrization for low-rank matrix sensing by constructing an infinite hierarchy of lifted non-convex problems through tensor lifting and Burer–Monteiro factorization. Spurious solutions remain stationary through the hierarchy but become strict saddle points under technical conditions, allowing local search methods to escape them. We also derive a bound on how much over-parametrization is needed to eliminate spurious solutions.