Jan, 2017

低秩矩阵线性恢复的随机方差减少梯度下降

PDF
TL;DR本研究探讨通过非凸优化从线性测量（即矩阵感知）中估计低秩矩阵的问题，并建议了一种有效的随机方差减少梯度下降算法来解决此问题。我们的算法适用于有噪声和无噪声的情况。在有噪声的情况下，我们证明了该算法在最小化统计误差方面以线性速率收敛于未知低秩矩阵。在无噪声的情况下，我们的算法保证线性收敛于未知低秩矩阵，并在最优采样复杂度下实现了精确恢复。值得注意的是，我们提出的算法的总计算复杂度（定义为迭代复杂度乘以每次迭代时间复杂度）低于基于梯度下降的最新算法。用合成数据的实验证明了该算法优于现有算法。
low-rank matriceslinear measurementsnonconvex optimizationstochastic variance reduced gradient descent algorithmexact recovery
发现论文，激发创造
  • 非凸低秩矩阵估计的统一计算与统计框架

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

    Oct, 2016

  • 低秩矩阵恢复的黎曼优化保证

    本文研究了低秩矩阵恢复的一类黎曼优化算法，证明了当感知算子的受限等距常数小于 Cκ/√r 时，算法能够从几乎最小的测量中恢复低秩矩阵。

    Nov, 2015

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

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

    May, 2023

  • 具有复合优化的低秩矩阵恢复：良好的条件和快速收敛

    该研究提出了一种新的低秩矩阵恢复方法，采用非平滑惩罚形式，在某些具体情况下能够克服传统平滑方法的病态问题，同时具有自适应性和鲁棒性。数值实验说明了该方法在解决相位恢复、盲卷积、矩阵补全和稳健 PCA 等计算任务中的优势。

    Apr, 2019

  • 利用随机初始化的黎曼梯度下降快速全局收敛的低秩矩阵恢复

    本文提出了一种适用于 Riemann 流形上低秩矩阵恢复问题的新的全局分析框架，其中使用 Riemann 梯度下降算法最小化最小二乘损失函数，并研究了渐近行为以及精确收敛速率。

    Dec, 2020

  • 小随机梯度下降的非对称矩阵感知

    矩阵感知是从少量线性测量中重建低秩矩阵的问题，我们引入了连续微分方程，称其为 “扰动梯度流”，通过边界足够有界的累计误差，证明扰动梯度流迅速收敛到真实目标矩阵，从而提供了一种基于梯度下降的非对称矩阵感知的新证明方法。

    Sep, 2023

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

    通过矩阵分解和投影梯度下降算法解决约束最优化问题，提供了一种通用理论框架，当给定适当的初始化时，可以几何级数地收敛到具有统计意义的解，适用于许多具体模型。

    Sep, 2015

  • 低秩矩阵恢复的局部搜索的全局最优性

    该研究表明，使用非凸因式分解的参数化方法可以从不一致的线性测量中恢复低秩矩阵，且不存在虚假的局部最小值。并且在有噪声的测量中，所有局部最小值都非常靠近全局最优解。结合鞍点的曲率界限，保证了随机梯度下降从随机初始化出发以多项式时间全局收敛。

    May, 2016

  • 鲁棒低秩张量恢复：模型与算法

    本文在凸优化框架中研究了鲁棒性低秩张量恢复问题，并提出了具有全局收敛保证的定制优化算法，包括交替方向增广 Lagrange 算法和加速近端梯度方法。作者还提出了一种非凸模型，并通过实际应用展示了鲁棒性低秩张量恢复的实用有效性。

    Nov, 2013

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

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

    May, 2016