Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima
This reveals a critical limitation for applications requiring nonnegative constraints, such as in data analysis or machine learning, where existing robustness assumptions may not hold.
The paper investigates whether low-rank matrix recovery with nonnegative constraints retains benign nonconvexity, finding that it holds in fully-observed cases but fails in partially-observed cases even with small RIP constants, exposing a theoretical gap.
The classical low-rank matrix recovery problem is well-known to exhibit \emph{benign nonconvexity} under the restricted isometry property (RIP): local optimization is guaranteed to converge to the global optimum, where the ground truth is recovered. We investigate whether benign nonconvexity continues to hold when the factor matrices are constrained to be elementwise nonnegative -- a common practical requirement. In the simple setting of a rank-1 nonnegative ground truth, we confirm that benign nonconvexity holds in the fully-observed case with RIP constant $δ=0$. Surprisingly, however, this property fails to extend to the partially-observed case with any arbitrarily small RIP constant $δ\to0^{+}$, irrespective of rank overparameterization. This finding exposes a critical theoretical gap: the continuity argument widely used to explain the empirical robustness of low-rank matrix recovery fundamentally breaks down once nonnegative constraints are imposed.