May, 2024

高效联邦低秩矩阵补全

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

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

    Feb, 2016

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

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

    Dec, 2013

  • 交替最小化法实现低秩矩阵完成

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

    Dec, 2012

  • 近乎最优的鲁棒矩阵完成

    本文提出了一种简单的投影梯度下降方法来估计低秩矩阵，用于解决鲁棒矩阵完成问题，并且包括清除一些受损条目的步骤，并在低秩矩阵完成问题中获得了最优观测次数和最优破坏次数的解决方法。同时，本文的结果还意味着，对于低秩矩阵完成问题的时间复杂度界限，取得了重要的改进。最后，通过将结果应用于鲁棒 PCA 问题，得到了高效的解决方案

    Jun, 2016

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

    本研究提供了一种有效和稳健的交替最小化框架来解决线性代数和机器学习中的一些问题，关注于都市中加权矩阵的低秩矩阵近似问题，并将运行时间从之前的 n^2k^2 降至 n^2k。

    Jun, 2023

  • 低秩矩阵补全：当代综述

    本文为低秩矩阵补全问题提供了最新的调查，对最新的 LRMC 技术进行了分类和详细说明，讨论了 LRMC 技术使用时需要考虑的问题，并介绍了基于卷积神经网络的 LRMC 算法，最后介绍了最新 LRMC 技术的恢复性能和计算复杂性。希望本文对初学者和从业者提供了有用的指导。

    Jul, 2019

  • 小初始化的梯度下降收敛性用于非正则化矩阵补全

    对称矩阵完成问题的研究表明，使用小初始化的梯度下降算法可以无需显式正则化地收敛到真实解，即使在过参数优化情况下也成立；同时，初始点越小，解的精确度越高。针对该问题的全局收敛性分析借助了一种新颖的弱耦合一致性评估方法，拓展了经典的留一法分析范畴。

    Feb, 2024

  • 低秩张量补全的并行矩阵分解

    本研究提出了一个新的模型以及应用交替最小化算法和两种自适应秩调整策略同时对低秩张量进行低秩矩阵分解，结果表明，该算法可以在比其他方法更少的数据采样下恢复各种合成低秩张量，而且实际数据的测试结果也有类似优势。

    Dec, 2013

  • 一种用于非负因子矩阵补全的交替方向算法

    本文介绍了一种基于非负矩阵因式分解和补全问题的算法，可以通过同时利用非负性和低秩性来获得更好的结果，并通过基于交替方向增广 Lagrange 方法的算法来解决该问题。该算法优于现有算法，并可用于恢复不完整图像。

    Mar, 2011

  • 基于误差反馈的低秩梯度压缩技术在 MIMO 无线联邦学习中的应用

    本文提出了一种用于增强多输入多输出（MIMO）无线系统中联邦学习（FL）通信效率的新方法。该方法基于交替最小二乘算法，利用低秩矩阵分解策略对本地梯度压缩进行过空中计算和误差反馈。所提出的协议被称为空中低秩压缩（Ota-LC），在保证相同推理性能的同时，相比现有基准方案具有更低的计算成本和通信开销。以 Cifar-10 数据集为例，当目标测试准确度为 80% 时，Ota-LC 相比基准方案至少可以降低 30% 的总通信开销，并将计算复杂度的阶数降低到梯度维度之和的倍数。

    Jan, 2024