论文标题
稳健矩阵恢复的次级梯度方法的全局收敛：较小的初始化，嘈杂的测量和过度参数化
Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization
论文作者
论文摘要
在这项工作中，我们研究了自然非凸的次级方法（SUBGM）的性能，并使用$ \ ell_1 $ -loss对低级别基质恢复的非平滑配方进行表现，其目标是从有限的测量值中恢复低秩矩阵，其子集的子集可能会与噪声大量腐败。我们研究了一个真实解决方案等级未知和过度估计的场景。该等级的过度估计产生了一个过度参数化的模型，在这种模型中，自由度超过了所需的自由度。这种过度参数可能导致过度拟合或不利影响算法的性能。我们证明，一个具有较小初始化的简单subgm对测量中的过度参数和噪声是不可知的。特别是，我们表明，小初始化无效过度参数化对SUBGM性能的影响，从而导致其收敛速率的指数提高。此外，我们提供了第一个统一的框架，用于分析在离群和高斯噪声模型下SubGM的行为，表明SubGM收敛到真实解决方案，即使在任意且任意密集的噪声值之下，也许是令人惊讶的，即使是全球最佳的解决方案也不对应于地面真相。我们结果的核心是限制等轴测属性的强大变体，称为标志 - rip，它控制了$ \ ell_1 $ -loss与理想的预期损失的偏差的偏差。作为我们结果的副产品，我们考虑使用高斯测量值的稳健低矩阵恢复的子类，并表明要确保SubGM全局收敛的所需样品数量与过度指定的等级无关。
In this work, we study the performance of sub-gradient method (SubGM) on a natural nonconvex and nonsmooth formulation of low-rank matrix recovery with $\ell_1$-loss, where the goal is to recover a low-rank matrix from a limited number of measurements, a subset of which may be grossly corrupted with noise. We study a scenario where the rank of the true solution is unknown and over-estimated instead. The over-estimation of the rank gives rise to an over-parameterized model in which there are more degrees of freedom than needed. Such over-parameterization may lead to overfitting, or adversely affect the performance of the algorithm. We prove that a simple SubGM with small initialization is agnostic to both over-parameterization and noise in the measurements. In particular, we show that small initialization nullifies the effect of over-parameterization on the performance of SubGM, leading to an exponential improvement in its convergence rate. Moreover, we provide the first unifying framework for analyzing the behavior of SubGM under both outlier and Gaussian noise models, showing that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values, and--perhaps surprisingly--even if the globally optimal solutions do not correspond to the ground truth. At the core of our results is a robust variant of restricted isometry property, called Sign-RIP, which controls the deviation of the sub-differential of the $\ell_1$-loss from that of an ideal, expected loss. As a byproduct of our results, we consider a subclass of robust low-rank matrix recovery with Gaussian measurements, and show that the number of required samples to guarantee the global convergence of SubGM is independent of the over-parameterized rank.
