Low-Rank Matrix Recovery With Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
Low-Rank Matrix Recovery With Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
复制标题
使用缩放次梯度方法的低秩矩阵恢复：无需条件数的快速鲁棒收敛
DOI：
10.1109/tsp.2021.3071560
复制
发表时间：
2021
影响因子：
5.4
通讯作者：
Chi, Yuejie
中科院分区：
文献类型：
--
作者：
Tong, Tian;Ma, Cong;Chi, Yuejie
数据科学中的许多问题都可以被视为从高度不完整的，有时甚至是损坏的观测值中估计低秩矩阵。一种流行的方法是诉诸矩阵分解，其中低秩矩阵因子通过平滑损失函数（例如残差平方和）上的一阶方法进行优化。虽然近年来取得了巨大的进展，但自然光滑公式存在两个病态来源，其中梯度下降的迭代复杂度与低秩矩阵的维度和条件数的关系都很差。此外，光滑公式对腐败不具有鲁棒性。在本文中，我们提出了缩放次梯度方法，以尽量减少家庭的非光滑和非凸公式，特别是，绝对误差的残差和，这是保证收敛速度快，几乎是无量纲和独立的条件数，即使在腐败的存在。我们说明了我们的方法的有效性时，观察算子满足一定的混合范数限制等距属性，并获得国家的最先进的性能保证的各种问题，如鲁棒低秩矩阵传感和二次采样。
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 progress has 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.