非负低秩矩阵恢复存在虚假局部最优，导致优化失败。
Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima
- 在非负约束下，低秩恢复问题失去良性非凸性。
- 即使观测完全且稀疏性参数极小，仍会引入虚假解。
- 适用于研究非负矩阵优化的理论局限与新方法需求。
低秩矩阵恢复在受限等距性（RIP）下通常具有良性非凸性：所有二阶临界点均为全局最优，因此局部优化方法可保证恢复真值。针对投影梯度法在非负低秩恢复中表现优异的现象，本文研究了当因子矩阵元素非负时，这种良性几何是否依然成立。在秩1非负真值的简单情形下，当观测完全且RIP常数δ=0时，良性非凸性仍成立。然而，这一性质极为不稳定：在任意小的RIP常数δ>0的不完全观测情形，或更高秩真值r⋆>1时，无论搜索秩r≥r⋆如何过参数化，该性质均不成立。这些结果挑战了基于稳定性解释非凸方法成功性的主流观点，表明分析非负低秩恢复需采用根本不同的理论工具。
原文摘要 · Abstract (English)
Low-rank matrix recovery is well-known to exhibit benign nonconvexity under the restricted isometry property (RIP): every second-order critical point is globally optimal, so local methods provably recover the ground truth. Motivated by the strong empirical performance of projected gradient methods for nonnegative low-rank recovery problems, we investigate whether this benign geometry persists when the factor matrices are constrained to be elementwise nonnegative. 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$. This benign nonconvexity, however, is unstable. It fails to extend to the partially-observed case with any arbitrarily small RIP constant $δ>0$, and to higher-rank ground truths $r^{\star}>1$, regardless of how much the search rank $r\ge r^{\star}$ is overparameterized. Together, these results undermine the standard stability-based explanation for the empirical success of nonconvex methods and suggest that fundamentally different tools are needed to analyze nonnegative low-rank recovery.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。