随机块模型中 SVD 的能力
本文提出一种基于随机投影与有限阶多项式拓展计算奇异值分解嵌入的压缩光谱嵌入算法,其降维效果与计算复杂度不受特征向量数量影响。此算法对聚类和分类等下游推断任务的对比相似度度量具有较好效果。
Sep, 2015
本文研究了 $k$-means 聚类的降维问题,提出了第一个能够保证准确的特征选择方法,并针对特征提取提出了两种方法,分别基于随机投影和快速近似 SVD 分解。所提出的算法是随机的,并对最优 $k$-means 目标值提供一定的近似保证。
Oct, 2011
本文研究了 VR-PCA 算法的收敛特性和优化问题的凸性和非凸性,证明了一些新的结果,包括该算法的块版本的形式分析和从随机初始化到收敛,还提出一些具有独立兴趣的观察,例如如何通过单一的准确幂迭代来预初始化可以显著提高随机方法的运行时间。
Jul, 2015
本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题,进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响,并在模型的一些扩展,包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。
Mar, 2018
本研究提出了一种名为 VR-PCA 的简单算法,使用计算成本低的随机迭代,能够指数级快速收敛至最优解,相较于现有算法,其收敛速度更快,而迭代时间随数据量的变化不大,适用于解决非凸问题。
Sep, 2014
本文考虑一种流式数据模型,通过计算奇异值分解和草图矩阵,获得与原始数据矩阵非常接近的奇异值和奇异向量。同时,将其应用于流图算法来近似计算具有低秩的计算机网络图 Laplacian 的特征值和特征向量。
Nov, 2012
本研究提出了一种高效的算法,叫做球形归一化奇异值分解 (SVD),用于稳健的奇异值分解近似,对异常值不敏感、可扩展的计算,提供准确的奇异向量估计。该算法通过仅使用标准降秩奇异值分解算法对适当缩放的数据进行两次计算,实现了显著的计算速度,并在计算时间上明显优于竞争算法。为评估估计奇异向量及其子空间的稳健性,我们引入了矩阵型输入的新的破坏点概念,包括按行、按列和按块的破坏点。理论和实证分析表明,与标准 SVD 及其修改相比,我们的算法具有更高的破坏点。我们在高维微阵列数据集的鲁棒低秩逼近和鲁棒主成分分析等应用中,经验地验证了我们方法的有效性。总体而言,本研究提供了一种高效且稳健的 SVD 近似解决方案,克服了现有算法在异常值存在时的局限性。
Feb, 2024