k-means 聚类的随机投影
非监督学习中的聚类是一个基础问题，本研究介绍了一种简单的随机聚类算法，它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn)，并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法，通过实验证明与现有方法相比，我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。
Oct, 2023
研究采用缩略图替代数据矩阵来加速 k - 均值聚类和约束 k - 秩近似问题的精确、近似或启发式算法，并提供降维和草图技术及近似算法来解决这些普遍问题。
Oct, 2014
该研究论文探讨随机投影作为贝叶斯回归分析的数据降维技术，证明了高维分布在数据点从 n 到 k 时仍可以得到保留，通过对投影数据进行高斯似然函数的评估获得的结果误差很小，结果表明该方法能够高效恢复回归模型。
Apr, 2015
通过投影到随机的 O (log (k/ ε) / ε²) 维子空间上，可以近似保持欧几里得 k-means 或 k-medians 聚类的最优解成本，并且适用于任何满足温和的子高斯尾条件的维度缩减映射，其维数几乎是最优的。此外，该结果适用于所有权重的欧几里得 k - 聚类。
Nov, 2018
给定一组点，聚类是找到一个点集合的分区，使分配给一个点的中心尽可能接近。对于中心为点的目标，我们显示了一个收敛速度为 O (sqrt (k/n)) 的收敛界限。对于中心为 j 维子空间的子空间聚类，我们显示了一个收敛速度为 O (sqrt ((kj^2)/n)) 的收敛界限。对于广义 $k$-means 的投影聚类特例，我们证明了一个收敛速度为 Omega (sqrt ((kj)/n)) 的必要界限。
Oct, 2023
本文研究将输入点集 $X$ 投影到随机 $d=O (d_X)$ 维子空间（其中 $d_X$ 是 $X$ 的双倍维数）的随机降维应用到聚类问题中，主要探讨了设施选址问题和单链接层次聚类问题。研究表明，这种方法在维度映射到一定程度时，可以达到在原始空间中找到的最优的设施选址近似值，同时这种方法还可以用于解决最小生成树等问题。
Jul, 2021
利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。
Jun, 2020
本文研究了 $k$-means 聚类的降维问题，提出了第一个能够保证准确的特征选择方法，并针对特征提取提出了两种方法，分别基于随机投影和快速近似 SVD 分解。所提出的算法是随机的，并对最优 $k$-means 目标值提供一定的近似保证。
Oct, 2011