Sep, 2015

投影梯度下降法的快速低秩估计：广义统计和算法保证

PDF
TL;DR通过矩阵分解和投影梯度下降算法解决约束最优化问题，提供了一种通用理论框架，当给定适当的初始化时，可以几何级数地收敛到具有统计意义的解，适用于许多具体模型。
rank constraintsmatrix factorizationprojected gradient descentoptimizationlow-rank matrix
发现论文，激发创造
  • 非凸优化遇见低秩矩阵分解：概述

    本文从统计模型的角度出发，系统地讨论低秩矩阵分解非凸优化的可靠解法，总结出了两种方法：1. 根据问题特征设计初始值，进行迭代求解；2. 利用全局凸性分析，无需初始值，直接求解。文章阐述了这些方法在各种场景下的应用并剖析了其理论基础。

    Sep, 2018

  • 通过缩放梯度下降可证明地加速病态低秩估计，即使过度参数化

    本研究论文介绍了一种名为 ScaledGD 的新算法，通过合适的预处理能够快速收敛于低秩对象，并在多种任务中保持梯度下降的低迭代成本，同时无论条件数如何，都能以恒定速率线性收敛，突出了在加速非凸统计估计中适当预处理的能力。

    Oct, 2023

  • 非凸低秩矩阵估计的统一计算与统计框架

    提出了一种基于梯度下降算法的非凸优化的低秩矩阵估计的统一框架，其通用性很强，可应用于噪声和无噪声观测，算法能够线性收敛到未知低秩矩阵的最小最优统计误差，同时也能够以线性速率收敛到未知低秩矩阵，并以最优样本复杂度实现精确恢复。

    Oct, 2016

  • 广义张量估计的最优统计和计算框架

    该论文提出了一种灵活的通用低秩张量估计问题的框架，包括计算成像、基因组学和网络分析等应用中的许多重要实例，并通过投影梯度下降的统一方法来克服这些问题的非凸性，以适应底层低秩结构，并证明该算法在估计误差的收敛速度上达到极小值最优率。

    Feb, 2020

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

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

    Nov, 2014

  • 通过缩放梯度下降加速恶态低秩矩阵估计

    本文提出一种新算法 ScaledGD，它是梯度下降方法的预处理或对角线缩放版本，其预处理器是自适应且具有最小的计算开销，在低秩矩阵感知，鲁棒主成分分析和矩阵完成等任务中实现了线性收敛，具有优秀的性能表现。

    May, 2020

  • 通过非凸梯度下降快速且极小化误差地估计低秩矩阵

    本文研究了从噪声测量中估计低秩矩阵的问题，并提出一种修改的非凸梯度下降方法，既能解决慢收敛的问题，又能保持极小值最优性，通过医学成像应用的实验，我们观察到，与先前的方法相比，重建误差显着减小。

    May, 2023

  • 排名限制与低秩分解的临界点之间的等价性

    本文研究了低秩优化问题中矩阵变量秩约束和低秩分解优化方法的自然联系，证明了低秩分解目标函数的所有二阶稳定点对应于原问题上投影梯度下降算法的不动点，并统一了现有的优化保证，为某些情况下特定的问题提供了新结果。最后，将结果应用于矩阵逆问题。

    Dec, 2018

  • 通过保证低秩矩阵估计对大数据的结构进行利用

    低秩建模在信号处理和机器学习中扮演着关键的角色，本文综述了利用凸和非凸方法对低秩矩阵估计进行计算上高效可证的方法，其中包括对低维子空间和流形的适当利用及其对计算和存储成本的显著降低。

    Feb, 2018

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

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

    Jun, 2016