Jan, 2019

非凸矩形矩阵完整性的无 L2,∞ 正则化梯度下降

HTML
PDF
TL;DR本文介绍了如何通过改进梯度下降的技术和方法，将矩阵填充的采样率由O(poly(条件数)*mu^3*r^3*log^3n/n)降低至O(mu^2*r^2*条件数^14*log(n)/n)，并且这些技术和方法在改善其他相关问题的分析方面也具有潜在的用处。
发现论文，激发创造
  • 无需考虑条件数的快速矩阵填充

    本文介绍了第一种算法，可在多项式时间和样本复杂度内完成矩阵补全，其复杂度与矩阵的秩成正比，与矩阵的维度成线性关系，与矩阵的条件数成对数关系，并基于交替最小化扩展算法，对标准假设下受噪声影响的情况也有理论保证。

    Jul, 2014

  • 有限样本下精确快速矩阵补全

    该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O(nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。

    Nov, 2014

  • 采用Burer-Monteiro分解和梯度下降的矩形矩阵完成的收敛分析

    利用正定矩阵在更高维度上的升阶和简单的梯度下降算法，我们能够以高概率线性收敛到全局最优解，从而有效地解决了矩阵Completion问题。

    May, 2016

  • 可证明高效的在线矩阵完成算法: 非凸随机梯度下降

    该研究提出了一种可证明，高效的在线算法，用于矩阵完成问题。该算法使用随机梯度下降，具有快速的更新时间，并可自然地用于离线设置。

    May, 2016

  • 矩阵补全的留一法：原始和对偶分析

    本文介绍了一种基于Leave-one-out方法的技巧用于解决低秩矩阵完成问题，进而通过对Projected Gradient Descent和nuclear norm minimization等算法进行分析，得到了这些算法的收敛性保证以及较为精细的界限。

    Mar, 2018

  • 从含噪数据中恢复低秩张量的非凸方法

    我们提出了一个两阶段的非凸算法，用于从高度不完整和随机损坏的观测值中重建低秩张量，并在几乎线性时间内恢复所有单个张量因子，同时享受接近最优的统计保证，我们还讨论了如何扩展我们的方法以适应非对称张量。

    Nov, 2019

  • 最优低秩矩阵完成：半定松弛和特征向量分离

    通过将低秩矩阵补全问题重新表述为在投影矩阵的非凸集上的凸问题，并实施一个可证明最优的分离分支限界方案，推导出一类新的收敛松弛方法。数值实验表明，相比现有的收敛松弛方法，我们的新型收敛松弛方法将最优性差距降低了两个数量级。此外，我们展示了我们的分离分支限界方案的性能，并展示了它在解决矩阵完成问题方面的优异表现。

    May, 2023

  • 基于新的稀疏诱导正则化器的鲁棒低秩矩阵补全

    本文介绍了一种新的损失函数，名为混合常规-威尔士（HOW），以及与HOW相关的一种新的稀疏诱导正则化项。我们从理论上证明了该正则化项是准凸的，其对应的Moreau包络是凸的。此外，我们推导出该Moreau包络（即接近算子）的闭式解。与需要通过迭代来寻找相应接近算子的0<p<1的lp-范数之类的非凸正则化项相比，我们开发的正则化项具有闭式接近算子。我们将该正则化项应用于鲁棒矩阵完成问题，并基于交替方向乘法算法开发了一种高效算法。对所提出方法的收敛性进行了分析，并证明了任何生成的累积点都是一个驻点。最后，基于人工合成和真实数据集的实验结果表明，我们的算法在恢复性能方面优于现有方法。

    Oct, 2023

  • 小初始化的梯度下降收敛性用于非正则化矩阵补全

    对称矩阵完成问题的研究表明，使用小初始化的梯度下降算法可以无需显式正则化地收敛到真实解，即使在过参数优化情况下也成立；同时，初始点越小，解的精确度越高。针对该问题的全局收敛性分析借助了一种新颖的弱耦合一致性评估方法，拓展了经典的留一法分析范畴。

    Feb, 2024

  • 使用ReLU采样的对称矩阵补全

    对称半正定低秩矩阵完成问题进行研究，包括确定性依赖于矩阵元素的采样。首先通过实验证明该问题的全局最优点与梯度下降算法具有难以收敛的关系，但证明了在矩阵因子的秩较小且满足一定假设的情况下，非凸目标函数在一个低秩矩阵附近的商流形上是测地强凸的。此外，通过实验证明所提出的GD初始参数设计能够保证收敛到全局最小值。还进行广泛实验，比较了不同初始化、噪声水平、维度和秩对MC方法的收敛性和完成性能的影响。

    Jun, 2024