Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
复制标题
DOI：
--
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Lijun Ding;Liwei Jiang;Yudong Chen;Qing Qu;Zhihui Zhu
中科院分区：
文献类型：
--
作者：
Lijun Ding;Liwei Jiang;Yudong Chen;Qing Qu;Zhihui Zhu
我们研究了一个低秩矩阵的鲁棒恢复从稀疏和严重损坏的高斯测量，没有先验知识的固有秩。我们考虑了鲁棒矩阵分解方法。我们采用了一个鲁棒的' 1损失函数，并通过使用矩阵变量的过度指定因子表示来处理未知秩的挑战。然后，我们使用递减步长的次梯度方法求解相关的非凸非光滑问题。我们证明了在感知矩阵和腐败的正则性条件下，即我们称为受限保向性（RDPP），即使在秩过指定的情况下，子梯度方法也能以次线性的速度收敛到精确的低秩解。此外，我们的结果在某种意义上更通用，一旦因子秩与未知秩匹配，它就会自动加速到线性速率。另一方面，我们证明了RDPP条件在一般设置下成立，例如在独立或对抗性稀疏损坏下的高斯测量，其中结果可能是独立的。数值验证了该方法的精确恢复和收敛速度。此外，我们的实验进一步表明，我们特殊的递减步长设计有效地防止了在过参数化模型下的鲁棒恢复过拟合，例如鲁棒矩阵感知和鲁棒深度图像先验学习。这种正则化效应值得进一步研究。
We study the robust recovery of a low-rank matrix from sparsely and grossly corrupted Gaussian measurements, with no prior knowledge on the intrinsic rank. We consider the robust matrix factorization approach. We employ a robust `1 loss function and deal with the challenge of the unknown rank by using an overspecified factored representation of the matrix variable. We then solve the associated nonconvex nonsmooth problem using a subgradient method with diminishing stepsizes. We show that under a regularity condition on the sensing matrices and corruption, which we call restricted direction preserving property (RDPP), even with rank overspecified, the subgradient method converges to the exact low-rank solution at a sublinear rate. Moreover, our result is more general in the sense that it automatically speeds up to a linear rate once the factor rank matches the unknown rank. On the other hand, we show that the RDPP condition holds under generic settings, such as Gaussian measurements under independent or adversarial sparse corruptions, where the result could be of independent interest. Both the exact recovery and the convergence rate of the proposed subgradient method are numerically verified in the overspecified regime. Moreover, our experiment further shows that our particular design of diminishing stepsize effectively prevents overfitting for robust recovery under overparameterized models, such as robust matrix sensing and learning robust deep image prior. This regularization effect is worth further investigation.