本文提出了一种基于图信号处理的快速谱聚类算法,通过使用图滤波器对随机信号进行谱聚类距离矩阵的估计,利用这些随机向量的随机性来估计聚类数目 k,相较于传统谱聚类方法,我们的方法在大规模数据集上表现相当且速度至少快二倍。
Sep, 2015
本文提出了一种基于图信号处理的方法,采用图滤波和随机采样技术加速生成 Laplacian 矩阵特征向量和 k-means 聚类算法步骤,该方法在控制误差的同时计算时间效率可达到数个数量级的提升,并在人工合成数据和真实网络数据集上进行测试。
Feb, 2016
本文通过理论分析证明,在光谱聚类时,使用小量的幂迭代即可通过近似特征向量来达到接近最优的 K-means 聚类结果。
Nov, 2013
该论文通过 Lanczos 方法,提出了一种精确、鲁棒、可扩展和高效的算法,用于大规模图的信号处理和滤波,相较于基于 Chebyshev 多项式的现有方法,其在不增加整体复杂度的情况下实现了更高的准确性,并且特别适用于具有大谱间隙的图。
该研究探讨了一种可并行化的方法,通过对大型图的频谱进行扩展,以加速奇异值分解求解器和谱聚类,并利用多项式逼近来实现此目的。
Jul, 2022
本文提出一种基于特征图的方法来学习图信号的复原,通过最小化图拉普拉斯正则项以优化马氏距离矩阵的带权图,在 3D 点云去噪问题上的实验证明,相较于已有的方案,该算法具有最先进的性能。
Jul, 2019
采用自适应随机梯度优化的实用方法可以学习拉普拉斯矩阵的完整光谱,且每个迭代的成本与样本数量成线性关系,实验证明其具备比近似方法更好的计算可扩展性。
Jul, 2016
本研究提出了一种基于顶点嵌入的简单谱聚类算法,通过幂法计算的向量,在接近线性时间内计算顶点嵌入,并在输入图形的自然假设下,算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现,该算法与其他聚类算法相比,具有显著更快的速度,并且产生的聚类准确度基本相同。
Oct, 2023
该论文提出了一种基于扩散的谱聚类和降维算法的概率解释,利用规范化图拉普拉斯算子的特征向量。通过定义数据点之间的扩散距离,并证明了对应马尔科夫矩阵的前几个特征向量的低维表示在一定均方误差标准下是最佳的。此外,假设数据点是从密度 $p (x)=e^{-U (x)}$ 中随机抽取的,作者将这些特征向量视为具有反射边界条件下潜在 $2U (x)$ 力学势中福克 - 普朗克算子的离散近似的本征函数。最后,应用已知结果,对连续福克 - 普朗克算子的本征值和本征函数进行解析,从而为基于前几个特征向量的谱聚类和降维算法的成功提供了数学论证。这项分析阐明了许多经验发现关于谱聚类算法的特征和扩散进程。
Jun, 2005
研究正交群同步和置换群同步的谱方法的性能保证,通过研究计算出的特征向量如何逐个逼近每个群元素来建立理论,并且在正交群同步和置换群同步下,我们得出了性能界限和性能界限的结果,进行了数值实验来验证我们的理论。
Aug, 2020