Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach

Such problems appear in a variety of research fields and include image processing [12, 40], data analytics [13, 12], quantum computing [1, 19, 25], systems [30], and sensor localization [23] problems. There are numerous approaches that solve (1), both in its original non-convex form or through its convex relaxation; see [27, 16] and references therein. However, satisfying the rank constraint (or any nuclear norm constraints in the convex relaxation) per iteration requires SVD computations, which could be prohibitive in practice for large-scale settings. To overcome this obstacle, recent approaches reside on non-convex parametrization of the variable space and encode the low-rankness directly into the objective [22, 2, 39, 44, 14, 4, 43, 38, 45, 24, 31, 42, 32, 33].