  This paper studies the role of over-parametrization in solving non-convex
optimization problems. The focus is on the important class of low-rank matrix
sensing, where we propose an infinite hierarchy of non-convex problems via the
lifting technique and the Burer-Monteiro factorization. This contrasts with the
existing over-parametrization technique where the search rank is limited by the
dimension of the matrix and it does not allow a rich over-parametrization of an
arbitrary degree. We show that although the spurious solutions of the problem
remain stationary points through the hierarchy, they will be transformed into
strict saddle points (under some technical conditions) and can be escaped via
local search methods. This is the first result in the literature showing that
over-parametrization creates a negative curvature for escaping spurious
solutions. We also derive a bound on how much over-parametrization is requited
to enable the elimination of spurious solutions.
