低秩矩阵优化中的全局最优性
本文针对两个广泛使用的最小化问题:凸函数最小化问题和加上核范数的凸函数最小化问题,提出使用低秩分解和替代核范数的方法来加速求解问题,并证明其可以在全局范围内找到最优解。
Nov, 2016
该研究表明,使用非凸因式分解的参数化方法可以从不一致的线性测量中恢复低秩矩阵,且不存在虚假的局部最小值。并且在有噪声的测量中,所有局部最小值都非常靠近全局最优解。结合鞍点的曲率界限,保证了随机梯度下降从随机初始化出发以多项式时间全局收敛。
May, 2016
本文研究了一种适用于大规模数据集且通过使用特定形式的正则化来捕获因素中的额外结构的矩阵分解技术,该技术将已知的正则化器(如总变化和核范数)作为特定情况。 尽管所得到的优化问题是非凸的,但我们证明如果因素的大小足够大,在某些条件下,任何因素的局部最小值都可以得到全局最小值。我们还提供了一些实用的算法来解决矩阵分解问题,并导出了给定近似解的距离与全局最优解之间的距离范围。在大数据集上,神经钙成像视频分割和高光谱压缩恢复的示例显示了我们的方法的优势。
Aug, 2017
本研究提出了一种基于矩阵分解的优化方法 —— 双因式梯度下降算法(BFGD),在一定条件下可以实现局部次线性收敛以及全局线性收敛,为实现矩阵分解优化问题提供了一种有效的解决思路。
Jun, 2016
发展了一种新框架,旨在捕捉一般非凸低秩矩阵问题的共同局面,包括矩阵感知,矩阵完成和鲁棒 PCA,在优化风景线的现有分析的基础上进行了连接和简化,自然地导致了不对称矩阵完成和鲁棒 PCA 的新结果
Apr, 2017
本文从统计模型的角度出发,系统地讨论低秩矩阵分解非凸优化的可靠解法,总结出了两种方法:1. 根据问题特征设计初始值,进行迭代求解;2. 利用全局凸性分析,无需初始值,直接求解。文章阐述了这些方法在各种场景下的应用并剖析了其理论基础。
Sep, 2018
针对低秩矩阵完成问题,本文提出了一种基于几何目标函数的优化算法,解决了 Frobenius 度量方法的无法连续和解集不闭合的困难,并为特殊完成方案提供了强大的性能保证。
Jun, 2010
提出了一种基于对称半正定矩阵变量 X 进行定义的非线性凸程序的求解算法,该算法基于因数分解 X=YY^T,其中 Y 的列数确定 X 的秩。该因式分解唤起了将原问题重新表述为特定商流形上的优化的几何,并得出了二阶优化方法。此外,文章提供了一些关于分解秩的条件以确保与原始问题的等价性。该算法的效率在图的最大切割和稀疏主成分分析问题上得到了说明。
Jul, 2008
针对在低秩矩阵中最小化凸函数的问题,本文提出了一种高效的贪心算法,并给出其形式化的逼近保证。算法的每次迭代都涉及到计算某个矩阵的最大奇异值对应的左、右奇异向量,这可以在线性时间内完成。该算法可应用于矩阵完成和鲁棒低秩矩阵逼近等多个领域中的大型矩阵问题。
Jun, 2011
矩阵分解是一种常用的大规模矩阵补全方法,本文提出了一种理论保证,即在正则化条件下,优化算法可以收敛于矩阵分解的全局最优解,并恢复真实的低秩矩阵,其中的非对称矩阵分解的扰动分析是一项技术贡献。
Nov, 2014