Jun, 2016

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

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

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

    Sep, 2015

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

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

    May, 2016

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

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

    Jun, 2016

  • 放弃凸性以加速半定规划

    本研究探讨了正定半矩阵上凸函数的最小化问题，提出了分解梯度下降算法 (FGD) 的规则，并在标准条件下分析了其收敛性和收敛速率，同时证明了该算法在可重构矩阵分解等实际问题上的有效性，是首篇在一般凸函数下提供收敛率保证的研究。

    Sep, 2015

  • 关于 Brenier 的极分解的神经实现

    Brenier 在 1991 年证明了一条定理，将平方矩阵的 QR 分解（分解为 PSD × unitary）推广到任何向量场 F: R^d → R^d。这一被称为极分解定理的定理指出，任何场 F 都可以通过凸函数 u 的梯度和保测度映射 M 的复合来恢复，即 F = ∇u ∘ M。我们在机器学习领域提出了该理论的实际实现，并探索了其可能的应用。该定理与最优输运（OT）理论密切相关，我们借鉴了神经最优输运领域的最新进展，将潜力 u 参数化为一个输入凸神经网络。映射 M 可以通过使用 u^*（u 的凸共轭）的梯度点值进行计算，即 M = ∇u^* ∘ F，也可以作为一个辅助网络进行学习。由于 M 通常不是单射的，我们考虑在使用随机生成器近似逆映射估计不适定的逆映射 M^{-1} 的附加任务。我们展示了 Brenier 的极分解在非凸优化问题和非对数凹密度的抽样中的可能应用。

    Mar, 2024

  • 非凸 Burer-Monteiro 方法在光滑半定规划中的应用

    本文研究了一类包括最大割、随机块模型社区检测、鲁棒 PCA、相位恢复和旋转同步等应用的半定规划 SDP，表明以 Burer-Monteiro 公式为代表的低秩 SDP 几乎从不具有虚假的局部最优解。

    Jun, 2016

  • 低秩矩阵优化的非凸几何

    本文针对两个广泛使用的最小化问题：凸函数最小化问题和加上核范数的凸函数最小化问题，提出使用低秩分解和替代核范数的方法来加速求解问题，并证明其可以在全局范围内找到最优解。

    Nov, 2016

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

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

    Jun, 2021

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

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

    Nov, 2014

  • 非凸优化遇见低秩矩阵分解：概述

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

    Sep, 2018