概率单纯形上的投影:一种高效算法及简明证明与应用
本文提出一个快速和简单的算法来计算在标准单纯形三角形上的投影,利用 Moreau 恒等式,我们展示了该问题本质上是一元最小化问题,目标函数是严格凸的,且连续可微。此外,研究表明,最多有 n 个候选者可以明确计算,而最小化程序是唯一一个落入正确区间的程序。
Jan, 2011
本文提出一种新的迭代算法,Cauchy-Simplex,用于概率单纯形上的凸优化问题。该算法具有简单易用、收敛速度快等优点,并应用于在线学习问题,证明了平均遗憾的收敛性。
May, 2023
非监督学习中的聚类是一个基础问题,本研究介绍了一种简单的随机聚类算法,它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn),并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法,通过实验证明与现有方法相比,我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。
Oct, 2023
通过研究高斯向量、比例渐近性、经验分布、随机子空间和随机最优控制问题,我们证明了一类分布可以通过迭代算法实现,并获得了关于这个问题的对偶表述和拓展帕里西公式的变分原理。
Jun, 2024
该研究提出了基于稀疏单纯形投影的 Wasserstein k-means 算法,通过减少 Wasserstein 距离计算和利用稀疏单纯形投影来缩小数据样本、质心和成本矩阵的规模,从而显著减少用于求解最优运输问题的计算量,提高了聚类效果
Nov, 2020
分析了一种用于邻接矩阵的随机投影方法,研究其在表示稀疏图中的实用性,展示了这些随机投影保留了其底层邻接矩阵的功能,同时具有额外的特性,使它们作为动态图表示具有吸引力。特别地,它们可以在相同的空间中表示不同大小和顶点集的图,从而实现对图的聚合和操作的统一方式。同时提供关于投影大小需要如何扩展以保留准确的图操作的结果,表明投影的大小可以与顶点数线性扩展,同时准确地保留一阶图信息。最后,将这种随机投影描述为保持距离的邻接矩阵映射,类似于通常的 Johnson-Lindenstrauss 映射。
Sep, 2023
该论文证明了一个简单的聚类算法可以在不假设任何生成模型的情况下运作,只需要假定一种叫做 “接近条件” 的规律。该算法依赖于著名的 k-means 算法,能够产生大多数现有生成模型的结果,同时提出了一种新的技术来提高间距与标准差之比。
Apr, 2010