对称非负矩阵分解的随机算法

Feb, 2024

Randomized Algorithms for Symmetric Nonnegative Matrix Factorization

Koby Hayashi, Sinan G. Aksoy, Grey Ballard, Haesun Park

TL;DR对称非负矩阵分解是一种在数据分析和机器学习中利用非负、低秩矩阵及其转置来近似表示对称矩阵的技术。为了设计更快速和更可扩展的对称非负矩阵分解算法，我们开发了两种随机化算法来计算。第一种算法利用随机矩阵草图计算初始低秩输入矩阵，并利用此输入迅速计算对称非负矩阵分解。第二种算法利用随机杠杆得分采样来近似解决受限最小二乘问题。实验证明，这两种方法在实践中都非常有效，通过将它们应用于大型真实数据集上的图聚类任务，我们展示了这些方法在保持解决方案质量的同时显著提速，无论是在大规模稠密问题还是大规模稀疏问题上。

Abstract

symmetric nonnegative matrix factorization (SymNMF) is a technique in data analysis and machine learning that approximates a symmetric matrix with a product of a nonnegative, low-rank matrix and its transpose. To design faster and more scalable algorithms for SymNMF we develop two

发现论文，激发创造

计算非负矩阵分解 - 可证明的

该研究论文旨在研究非负矩阵分解问题，提出适用于每个常数r的精确和近似NMF的多项式时间算法，同时在3-SAT子指数时间算法假设下展示了精确NMF的难度证明，并提供了一个可以运行在n，m和r的多项式时间内的算法，该算法对输入具有可分离性的假设，并可将该算法应用于许多实际设置中。

Nov, 2011

使用线性规划分解非负矩阵

本论文提出了一种新的基于线性规划的计算非负矩阵分解的方法，其中关键思想是使用数据中最显著的特征来表示其他特征，以实现低秩近似且扩展到更一般的噪声模型并具有高效可扩展性的算法。

Jun, 2012

非负矩阵分解的原因和方法

本文介绍了非负矩阵分解的稀疏特征提取功能，并探讨了如何解决通常情况下NP困难的NMF问题，介绍了一个称为近可分离NMF的问题子类，可以高效地解决一些在有噪声的情况下的NMF问题。最后简要描述了NMF在数学和计算机科学领域的若干相关问题。

Jan, 2014

压缩非负矩阵分解快速准确

本研究提出了借助结构化随机压缩技术，分别应用于传统非负矩阵分解和分离式非负矩阵分解，以应对数据结构日益复杂、数据集日益庞大的情况，结果表明这种压缩技术比传统方法更快速高效。

May, 2015

快速对称非负矩阵分解中的对称丢弃

本文介绍了一种解决对称非负矩阵分解问题的快速算法，该算法通过将对称问题转化为非对称的形式进行求解，并证明了这种方法能够在达到全局最优解的同时具有强收敛性，实验表明该算法在数据分析和聚类任务中的应用效果良好。

Nov, 2018

SymNMF-Net对称NMF问题

本文提出了一种神经网络SymNMF-Net，用于解决Symmetric NMF优化算法在真实世界数据集聚类任务中出现的不足，并通过实验结果验证了该算法的有效性。

May, 2022

对称矩阵分解的再思考：更一般且更优的聚类视角

本文提出了使用正则项优化的高效因式分解算法来提高聚类性能，同时进一步探索了使用不同约束条件解决对称矩阵分解问题的通用框架。

Sep, 2022

通过非负低秩半定规划实现统计最优 K-means 聚类

该论文提出了一种基于Burer-Monteiro分解的NMF-like算法，通过将SDP松弛的K-means问题约束为非负低秩矩阵，实现了和NNF算法一样简单、可扩展且具有强大的统计优化保证的聚类效果。该算法在实验中的误聚类错误率明显低于现有的最新技术。

May, 2023

基于图正则化的L20范数非负矩阵分解的无监督特征学习

基于GNMF和l2,0范数约束的非负矩阵分解方法，旨在提取具有稀疏特征、减轻噪音影响的数据低维结构，通过实验验证了算法的有效性和优越性。

Mar, 2024

从压缩数据中学习非负矩阵分解

本研究解决了从压缩测量中直接提取非负低秩分量的问题，填补了现有方法对原始数据的访问需求过高的空白。提出了一种灵活且有理论支持的框架，通过优化问题仅基于压缩数据，能够接近原始矩阵的非负分解，显示出在实际应用中的良好性能。

Sep, 2024