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

• URL: http://arxiv.org/abs/2608.08704v1
• Date: Sun, 09 Aug 2026 13:34:27 GMT
• Title: Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery
• Abstract summary: Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales.<n>We address this issue through a multi- kernel formulation that aggregates kernels with different bandwidths.<n>We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model.
• Score: 5.506184984859199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control [21.938486689664856]
  We propose a choice of scale to make the spectral complexity of the kernel consistent with the intrinsic complexity of the underlying manifold.<n>We evaluate SSL embeddings from six encoders on CIFAR-100, showing that adaptive bandwidth consistently improves leave-one-out (LOO) classification and label propagation (LP) accuracy.
  arXiv  Detail & Related papers  (2026-09-03T02:57:28Z)
• Diffusion Models for High-Dimensional Clustered Data: Intrinsic-Dimension Adaptivity via Bayesian Classification [1.9981375888949475]
  We study the adaptivity of multimodal diffusion models to structured geometry of high-dimensional data.<n>We employ $K$-mixture Gaussian distributions as a canonical framework to capture this geometry.<n>By separately analysing the denoising process in its mixing and cluster-commitment phases, we prove that the KL error bound depends linearly on the maximum intrinsic dimension of a cluster.
  arXiv  Detail & Related papers  (2026-08-19T16:09:31Z)
• Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization [48.25304391127552]
  Estimating the tangent spaces of a data manifold is a fundamental problem in data analysis.<n>We propose a method, Laplacian Eigenvector Gradient Orthogonalization (LEGO), that utilizes the global structure of the data to guide local tangent space estimation.
  arXiv  Detail & Related papers  (2025-10-02T17:59:45Z)
• Avoided-crossings, degeneracies and Berry phases in the spectrum of quantum noise through analytic Bloch-Messiah decomposition [49.1574468325115]
  "analytic Bloch-Messiah decomposition" provides approach for characterizing dynamics of quantum optical systems.<n>We show that avoided crossings arise naturally when a single parameter is varied, leading to hypersensitivity of the singular vectors.<n>We highlight the possibility of programming the spectral response of photonic systems through the deliberate design of avoided crossings.
  arXiv  Detail & Related papers  (2025-04-29T13:14:15Z)
• Datacube segmentation via Deep Spectral Clustering [76.48544221010424]
  Extended Vision techniques often pose a challenge in their interpretation. The huge dimensionality of data cube spectra poses a complex task in its statistical interpretation. In this paper, we explore the possibility of applying unsupervised clustering methods in encoded space. A statistical dimensional reduction is performed by an ad hoc trained (Variational) AutoEncoder, while the clustering process is performed by a (learnable) iterative K-Means clustering algorithm.
  arXiv  Detail & Related papers  (2024-01-31T09:31:28Z)
• Variational Quantum Approximated Spectral Clustering [0.6718184400443239]
  We propose Variational Quantum Approximated Spectral Clustering (VQASC), which extends quantum distance-based classifier models to the clustering framework.<n>Our approach uses efficient quantum circuit designs whose depth scales sub-quadratically with dataset size, enabling the computation of weighted sums over various matrix representations of an undirected graph.
  arXiv  Detail & Related papers  (2023-09-08T17:54:42Z)
• Adaptively-weighted Integral Space for Fast Multiview Clustering [54.177846260063966]
  We propose an Adaptively-weighted Integral Space for Fast Multiview Clustering (AIMC) with nearly linear complexity. Specifically, view generation models are designed to reconstruct the view observations from the latent integral space. Experiments conducted on several realworld datasets confirm the superiority of the proposed AIMC method.
  arXiv  Detail & Related papers  (2022-08-25T05:47:39Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• Spectral learning of multivariate extremes [0.0]
  We propose a spectral clustering algorithm for analyzing the dependence structure of multivariate extremes. Our work studies the theoretical performance of spectral clustering based on a random $k-nearest neighbor graph constructed from an extremal sample. We propose a simple consistent estimation strategy for learning the angular measure.
  arXiv  Detail & Related papers  (2021-11-15T14:33:06Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• Kernel Interpolation of High Dimensional Scattered Data [22.857190042428922]
  Data sites selected from modeling high-dimensional problems often appear scattered in non-paternalistic ways. We propose and study in the current article a new framework to analyze kernel of high dimensional data, which features bounding approximation error by the spectrum of the underlying kernel matrix.
  arXiv  Detail & Related papers  (2020-09-03T08:34:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.