May, 2016

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

PDF
TL;DR利用正定矩阵在更高维度上的升阶和简单的梯度下降算法，我们能够以高概率线性收敛到全局最优解，从而有效地解决了矩阵 Completion 问题。
发现论文，激发创造
  • 非凸矩形矩阵完整性的无 L2,∞ 正则化梯度下降

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

    Jan, 2019

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

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

    Feb, 2024

  • 一类范约束矩阵问题的可证明 Burer-Monteiro 分解

    本文研究在具有强凸目标的低秩矩阵问题上使用投影梯度下降法。我们利用 Burer-Monteiro 分解方法隐式实现低秩性；这种分解方法引入了目标函数的非凸性。我们着重研究包括半正定（PSD）约束和特定矩阵范数约束在内的约束集。这些标准出现在量子态重构和相位恢复应用程序中。我们表明，非凸投影梯度下降在分解空间中偏爱局部线性收敛。我们通过一个新颖的下降引理建立我们的理论，该引理在不受限制的问题上最近的结果得到了非平凡的扩展。 这种算法称为投影因式梯度下降，简称 ProjFGD，并在量子状态重构和稀疏相位恢复应用程序方面表现出优异性能。

    Jun, 2016

  • Riemannian 优化在低秩矩阵补全中的保证

    研究嵌入低秩矩阵流形的黎曼优化方法在矩阵补全问题上的应用和收敛性，其中采样复杂度能进一步通过重新采样的黎曼梯度下降初始化方法减小，这取决于采样算子的像的非对称限制性同构性质和低秩矩阵流形的曲率。

    Mar, 2016

  • 非凸因式分解实现保证矩阵补全

    矩阵分解是一种常用的大规模矩阵补全方法，本文提出了一种理论保证，即在正则化条件下，优化算法可以收敛于矩阵分解的全局最优解，并恢复真实的低秩矩阵，其中的非对称矩阵分解的扰动分析是一项技术贡献。

    Nov, 2014

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

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

    Mar, 2018

  • 某些非凸矩阵问题的随机梯度下降全局收敛

    本研究展示了低秩最小二乘问题上的随机梯度下降算法的步长设定方案，并证明了在广泛的采样条件下，该算法能够从一个随机起始点全局收敛。

    Nov, 2014

  • 不对称低秩矩阵分解的梯度下降全局收敛性

    本研究论文首次证明了初始化的随机梯度下降算法可以在多项式时间内收敛到具有对称和非对称特点的低秩矩阵分解问题的全局最小值，该证明基于新的对称化技术和定量扰动分析方法，并可以拓展到其他相关的非凸问题。

    Jun, 2021

  • 矩阵分解的交替梯度下降收敛

    本文研究了交替梯度下降算法应用于非对称矩阵分解目标函数的收敛性分析，证明了在充分迭代步数内，随机初始化下可以收敛到较优解，此结果可以为更广泛的非凸低秩矩阵分解问题的收敛分析提供帮助，并在实验中得到了验证。

    May, 2023

  • 通过非凸矩阵分解高效可靠地找到低秩解

    本研究提出了一种基于矩阵分解的优化方法 —— 双因式梯度下降算法（BFGD），在一定条件下可以实现局部次线性收敛以及全局线性收敛，为实现矩阵分解优化问题提供了一种有效的解决思路。

    Jun, 2016