arXiv:2608.08704stat.MLcs.LG2026-08

多核谱聚类提升高维数据聚类精度,自动捕捉不同尺度距离。

Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery

  • 用多个带宽的核函数聚合,自动选择距离尺度。
  • 在高维多尺度模型下,聚类结果可实现高概率精确恢复。
  • 适用于中心和协方差结构异质的复杂数据,适合科研与工程应用。

单带宽核谱聚类在具有多种特征成对距离尺度的数据中表现不足,尤其在高维情形下更为明显。本文提出一种多核方法,通过聚合不同带宽的核函数来解决此问题。带宽基于成对平方距离的经验分位数确定,无需先验总体信息即可捕捉相关距离尺度。在一般高维、多尺度混合模型下,该方法允许异质簇中心与协方差几何结构。我们构建了经验多核矩阵的块状常数低秩近似,并建立了其主谱成分及对应归一化拉普拉斯矩阵的行级ℓ₂,∞扰动界。这些界实现了对谱嵌入的逐样本控制,优于传统全局谱空间扰动估计。在适当的特征值间隙与簇分离条件下,对多核谱嵌入进行近似K-均值聚类可实现高概率精确恢复。

原文摘要 · Abstract (English)

Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales, a problem particularly prevalent in the high-dimensional regime. We address this issue through a multi-kernel formulation that aggregates kernels with different bandwidths. The bandwidths are selected as prescribed empirical quantiles of the pairwise squared distances, thereby capturing the relevant distance scales without requiring prior population-scale information. We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model with heterogeneous cluster centers and covariance geometries. We construct a blockwise constant, low-rank informative approximation to the empirical multi-kernel matrix and establish row-wise $\ell_{2,\infty}$ perturbation bounds for its leading spectral components, as well as for the associated normalized Laplacian matrix. These bounds yield observation-level control of the spectral embedding, which is more informative than conventional global eigenspace perturbation estimates. Under suitable eigen-gap and cluster-separation conditions, we show that approximate $K$-means applied to the multi-kernel spectral embedding achieves exact recovery with high probability.

谱聚类多核方法高维数据精确恢复

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。