论文标题
使用缩放亚级别方法的低率矩阵恢复：快速且稳健的收敛而无需条件编号
Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
论文作者
论文摘要
数据科学中的许多问题可以视为估计高度不完整，有时甚至是损坏的观察结果的低级别矩阵。一种流行的方法是诉诸矩阵分解，其中低级别基质因子通过一阶方法优化了平滑损耗函数，例如平方的残留总和。尽管近年来已经取得了巨大的进步，但自然平滑的配方遭受了两种不良条件的来源，在这种情况下，梯度下降的迭代复杂性在尺寸以及低秩矩阵的条件数量的情况下都较差。此外，平滑的表述对腐败并不强大。在本文中，我们提出了缩放的亚级别方法，以最大程度地减少一个非平滑和非covex公式的家族，特别是绝对误差的残留总和 - 即使在腐败的存在下，也可以以几乎不含尺寸的快速速率收敛，几乎无维度，并且独立于状态数量。当观测操作员满足某些混合和限制的等轴测特性时，我们说明了方法的有效性，并为诸如强大的低级别矩阵传感和二次抽样等各种问题提供了最先进的性能保证。
Many problems in data science can be treated as estimating a low-rank matrix from highly incomplete, sometimes even corrupted, observations. One popular approach is to resort to matrix factorization, where the low-rank matrix factors are optimized via first-order methods over a smooth loss function, such as the residual sum of squares. While tremendous progresses have been made in recent years, the natural smooth formulation suffers from two sources of ill-conditioning, where the iteration complexity of gradient descent scales poorly both with the dimension as well as the condition number of the low-rank matrix. Moreover, the smooth formulation is not robust to corruptions. In this paper, we propose scaled subgradient methods to minimize a family of nonsmooth and nonconvex formulations -- in particular, the residual sum of absolute errors -- which is guaranteed to converge at a fast rate that is almost dimension-free and independent of the condition number, even in the presence of corruptions. We illustrate the effectiveness of our approach when the observation operator satisfies certain mixed-norm restricted isometry properties, and derive state-of-the-art performance guarantees for a variety of problems such as robust low-rank matrix sensing and quadratic sampling.
