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

Jun, 2016

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

Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably

Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, Sujay Sanghavi

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

Abstract

A rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ can be written as a product $U V^\top$, where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. One could exploit this observation in optimization: e.g., consider the minimization of a convex function $f(X)$ over rank-$r$ matrices, where the set of rank-$r$ matrices is modeled via the facto

matrix factorization convex optimization first-order algorithm sublinear convergence linear convergence

发现论文，激发创造

放弃凸性以加速半定规划

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

Sep, 2015

低秩矩阵优化的非凸几何

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

Nov, 2016

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

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

Sep, 2018

半定凸问题的低秩优化

提出了一种基于对称半正定矩阵变量 X 进行定义的非线性凸程序的求解算法，该算法基于因数分解 X=YY^T，其中 Y 的列数确定 X 的秩。该因式分解唤起了将原问题重新表述为特定商流形上的优化的几何，并得出了二阶优化方法。此外，文章提供了一些关于分解秩的条件以确保与原始问题的等价性。该算法的效率在图的最大切割和稀疏主成分分析问题上得到了说明。

Jul, 2008

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

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

Jun, 2021

低秩矩阵优化中的全局最优性

本文研究将矩阵分解后进行优化以减少计算量，并分析了具有全局收敛特性的目标函数

Feb, 2017

二进制分解矩阵

研究低秩矩阵分解问题，其中一个因子具有 {0,1} 约束条件，第二个因子可以加入凸约束条件；提出一种基于近期非负矩阵分解算法的解决方案，可通过组合数学中的 Littlewood-Offord 引理，在 O (m r 2^r + mnr + r^2 n) 次操作下准确计算低秩分解。

Jan, 2014

结构化低秩矩阵分解：全局最优、算法和应用

本文研究了一种适用于大规模数据集且通过使用特定形式的正则化来捕获因素中的额外结构的矩阵分解技术，该技术将已知的正则化器（如总变化和核范数）作为特定情况。尽管所得到的优化问题是非凸的，但我们证明如果因素的大小足够大，在某些条件下，任何因素的局部最小值都可以得到全局最小值。我们还提供了一些实用的算法来解决矩阵分解问题，并导出了给定近似解的距离与全局最优解之间的距离范围。在大数据集上，神经钙成像视频分割和高光谱压缩恢复的示例显示了我们的方法的优势。

Aug, 2017

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

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

Jun, 2016

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

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

Sep, 2015