Jun, 2023

高效交替最小化与带权低秩近似的应用

PDF
TL;DR本研究提供了一种有效和稳健的交替最小化框架来解决线性代数和机器学习中的一些问题，关注于都市中加权矩阵的低秩矩阵近似问题，并将运行时间从之前的 n^2k^2 降至 n^2k。
weighted low rank approximationnumerical linear algebramachine learningalternating minimizationmatrix factorization
发现论文，激发创造
  • 交替最小化法实现低秩矩阵完成

    本文首次理论分析了交替极小化算法在矩阵完成和矩阵感知问题中的表现，证明了在满足某些条件下，该算法可以快速收敛到真实矩阵，同时具有更简单的分析方法。

    Dec, 2012

  • 交替最小化法保证加权低秩逼近的恢复

    本文提出一种简单的交替最小化算法，提供了带权重低秩矩阵恢复的可证明的等保障，并不需要关于噪声的假设，其误差随交替次数按指数级递减，初始矩阵可以由 SVD 或随机初始化得到，这是一种非常简单的算法，可以显着扩展矩阵补全的结果，特别是那些存在于现有研究工作中的二进制权重问题。

    Feb, 2016

  • 理解矩阵补全的交替最小化方法

    使用一种基于交替最小化的新算法，在标准不连贯性假设下，可从一个未知的低秩矩阵中恢复随机子样本的条目，并减少至少一次方之秩和相似矩阵的条件数的交替最小化方法的样本大小要求。

    Dec, 2013

  • 带权重或缺失数据的低秩矩阵逼近是 NP 难的

    本文研究了带权低秩逼近算法的计算复杂度，并证明了即使在寻求秩为一的逼近解时，找到近似解也是 NP 难的，该证明基于最大边双团问题的约化并适用于严格正权重和二进制权重。

    Dec, 2010

  • 矩阵补全问题中交替最小化算法的注记

    研究了从部分元素中重建低秩矩阵的问题，分析了两种交替最小化算法的变体，证明了当相关矩阵具有秩 $r=1$、有界正元素且图的度和直径在矩阵规模的对数范围内时，两种算法都可以在多项式时间内从任意初始状态开始近似重建矩阵，并提供了模拟结果表明基于信息传递更新的第二个算法表现更好。

    Feb, 2016

  • 通过采样杠杆元素实现更紧凑的低秩近似

    本文提出了一种新的随机算法，该算法采用特别偏向采样的方法，使误差最小化，可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近，并具有 better dependence on error ε，是一种高度可并行化的优化方法。此外，本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。

    Oct, 2014

  • 基于学习的低秩逼近

    本文介绍了一种基于学习的算法来解决低秩分解问题，并且通过学习用稀疏矩阵来代替随机矩阵可以减小近似误差。同时，给出了针对稀疏矩阵学习问题的泛化界及近似算法。

    Oct, 2019

  • 通过迭代重新加权最小二乘法恢复低秩矩阵

    使用迭代重加权最小二乘算法，同时结合核范数和近似低秩解的最小化，有效地从少量线性测量中恢复矩阵，并通过实验证明在矩阵完成问题中具有竞争力。

    Oct, 2010

  • 低秩约束下的大规模凸优化

    针对在低秩矩阵中最小化凸函数的问题，本文提出了一种高效的贪心算法，并给出其形式化的逼近保证。算法的每次迭代都涉及到计算某个矩阵的最大奇异值对应的左、右奇异向量，这可以在线性时间内完成。该算法可应用于矩阵完成和鲁棒低秩矩阵逼近等多个领域中的大型矩阵问题。

    Jun, 2011

  • 高效联邦低秩矩阵补全

    我们开发并分析了一种基于梯度下降（GD）的解决方案，称为交替 GD 和最小化（AltGDmin），以在联邦环境中高效解决低秩矩阵完成（LRMC）问题。我们的理论保证（迭代和样本复杂度界限）表明 AltGDmin 是联邦环境中最高效的解决方案之一，速度最快，并且在所有迭代解 LRMC 的方法中具有第二最佳的样本复杂度。此外，我们还证明了两个重要的推论：（a）我们为 AltGDmin 解决有噪声的 LRMC 问题提供了保证。（b）我们展示了如何利用引理改进 AltMin 的样本复杂度保证，AltMin 是最快的集中式解决方案。

    May, 2024