用于对称非负矩阵分解和图聚类的非单调梯度算法

arXiv cs.LG 论文
symmetric-nmf nonnegative-matrix-factorization graph-clustering optimization barzilai-borwein algorithm machine-learning

摘要

介绍了一种用于对称非负矩阵分解的非单调梯度算法SNMPBB，该算法相比现有方法实现了显著加速，并扩展至图聚类和低秩近似。

arXiv:2606.02887v1 公告类型：新 摘要：对称非负矩阵分解（Symmetric NMF）将矩阵近似为 $WW^T$，其中 $W$ 是非负矩形因子。它在图聚类和机器学习中有广泛应用。与NMF不同，对称问题的投影梯度方法此前被认为收敛速度较慢。为解决这一问题，我们引入了SNMPBB，这是非单调投影Barzilai-Borwein方法在对称NMF上的首次适应，表明梯度算法比此前认为的有效得多。我们进一步将SNMPBB扩展至使用图拉普拉斯正则化的图聚类（Graph-SNMPBB），以及使用低秩近似的大规模问题（LAI-SNMPBB）。对于所有变体，我们证明了全局收敛于一阶稳定点，并且Barzilai-Borwein曲率信息在随机近似中得以保留。在合成数据上，SNMPBB在相似残差下比替代方法SymANLS实现了6倍加速，且在高秩时优势更大。在六个真实聚类基准测试中，Graph-SNMPBB在精度上达到或超过SymANLS。最后，LAI-SNMPBB在34个SuiteSparse矩阵上的运行时间和残差质量均优于现有最优方法LAI-SymPGNCG。
查看原文
查看缓存全文

缓存时间: 2026/06/03 09:40 

# 一种非单调梯度算法用于对称非负矩阵分解和图聚类
来源: https://arxiv.org/abs/2606.02887
查看 PDF (https://arxiv.org/pdf/2606.02887)

> **摘要:** 对称非负矩阵分解 (Symmetric NMF) 通过非负矩形因子 $W$ 将矩阵近似为 $WW^T$。它在图聚类和机器学习中有着广泛的应用。与 NMF 相比，针对对称问题的投影梯度方法此前被认为收敛缓慢。为了解决这一问题，我们引入了 SNMPBB，这是首个将非单调投影 Barzilai-Borwein 方法应用于对称 NMF 的算法，证明了梯度算法比以往理解的更为有效。我们进一步将 SNMPBB 扩展到采用图拉普拉斯正则化的图聚类 (Graph-SNMPBB)，以及采用低秩近似的大规模问题 (LAI-SNMPBB)。对于所有变体，我们证明了全局收敛到一阶稳定点，并且 Barzilai-Borwein 曲率信息在随机近似下得以保留。在合成数据上，对于相似的残差，SNMPBB 相比替代方法 SymANLS 实现了 6 倍的加速，且在高秩情况下优势更大。在六个真实世界的聚类基准测试中，Graph-SNMPBB 的准确率与 SymANLS 相当或更优。最后，在 34 个 SuiteSparse 矩阵上，LAI-SNMPBB 在运行时间和残差质量上均优于最先进的 LAI-SymPGNCG。

## 提交历史

来自: Johannes Brust [查看邮件 (https://arxiv.org/show-email/f0e56e0e/2606.02887)] **[v1]** 2026 年 6 月 1 日星期一 20:59:33 UTC (148 KB)

相似文章

Flash-GMM：一种用于可扩展软聚类的内存高效内核

Hugging Face Daily Papers

Flash-GMM 引入了一个用于高斯混合模型的融合Triton内核，实现了20倍加速，并能在单个GPU上训练比之前大100倍的数据集，使软聚类成为近似最近邻搜索中k-means的可行替代方案。

Orth-Dion: 消除分布式低秩谱优化中的几何失配

arXiv cs.LG

本文指出了Dion低秩谱优化器中的几何失配，并提出了Orth-Dion，该方案用QR正交化替换列归一化，以在相同通信成本下弥合与Muon等全秩方法的收敛差距，并在大规模语言模型预训练中进行了验证。