Pith. sign in

REVIEW 2 major objections 4 minor 55 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Multi-kernel spectral clustering with quantile-chosen bandwidths recovers every cluster exactly with probability at least $1-n^{-C}$ in high-dimensional multi-scale mixtures.

desk verdict Strong perturbation theory, but exact recovery is overproven: Lemma D.3's 'WLOG r=m' invalidates Theorem 3.3 for r<m. read the letter →

arxiv 2608.08704 v1 pith:A7C3M6MO submitted 2026-08-09 stat.ML cs.LGmath.STstat.TH

Zeqin Lin , Guangming Pan , Zhixiang Zhang , Yinbing Zhou This is my paper · ORCID
classification stat.MLcs.LGmath.STstat.TH MSC 62H3060B20
keywords multi-kernelspectralclusteringmulti-scalemixturemodelsquantilebandwidthselectionentrywiseeigenvectorperturbationrow-wiseboundsexactrecoverynormalizedLaplacianhigh-dimensionalkernelmatrices
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that kernel spectral clustering stops being hostage to one bandwidth: by summing several RBF kernels whose bandwidths are taken from empirical quantiles of the pairwise squared distances, the method captures every characteristic distance scale at once, with no prior knowledge of those scales. The central theorem states that under a high-dimensional multi-scale mixture model with separated cluster centers, balanced clusters, and a growing eigengap, approximate $k$-means applied to the multi-kernel spectral embedding recovers the true clustering exactly, with failure probability below $n^{-C}$ for any fixed $C$. The proof works by showing that the empirical multi-kernel matrix is a small row-wise perturbation of a blockwise-constant, low-rank 'informative' matrix whose eigenvectors are piecewise constant on the clusters, so the embedding of every point tracks its cluster's population center. If the claim is right, a common practical heuristic - quantile-based bandwidth choice - is placed on a rigorous foundation, and spectral clustering gains exact-recovery guarantees for datasets whose clusters live at very different distance scales, the regime in which single-bandwidth kernels visibly fail.

What carries the argument

The load-bearing object is the informative matrix $\bar{K}$, defined blockwise by $\bar{K}_{ij}=\sum_{t\in S_{k\ell}(0)}\alpha_t\exp(-\theta_{k\ell}/\hbar_t)$ for $i\in C_k$, $j\in C_\ell$, where $\theta_{k\ell}=\|\boldsymbol\mu_k-\boldsymbol\mu_\ell\|^2+\mathrm{Tr}\,\boldsymbol\Sigma_k+\mathrm{Tr}\,\boldsymbol\Sigma_\ell$ is the expected squared distance between clusters $k$ and $\ell$, and $S_{k\ell}(0)$ keeps only the kernel components whose bandwidths are comparable to that scale (components with much smaller bandwidths contribute exponentially little and are discarded). Since $\bar{K}=\boldsymbol\Phi\mathfrak{K}\boldsymbol\Phi^\top$ with $\boldsymbol\Phi$ the normalized cluster-indicator matrix, its rank is at most the number of clusters and its eigenvectors are piecewise constant on clusters: the population embedding is constant within each cluster, the structure $k$-means is designed to find. The argument is carried by a two-stage decomposition $K\approx\hat{K}\approx\bar{K}$, where the intermediate matrix $\hat{K}$ keeps the first-order random fluctuations, and by the scale-matched noise parameter $\rho$, which is what lets the bounds stay small when distance scales are heterogeneous. The bandwidths used by the algorithm are the empirical quantiles $h_t=G^{-1}(\omega_t)$ of the pairwise squared distances, and Lemma 3.1 shows that these fall within a multiplicative factor $1+O(n^\varepsilon\rho)$ of admissible deterministic bandwidths, so the perturbation theory applies to the actual data-driven procedure.

What would settle it

Run the paper's own two-scale six-cluster Gaussian model at growing $n$, but choose quantile levels $\{\omega_t\}$ that all fall inside the small scale's slice $(N_{<s}/N,(N_{<s}+N_s)/N)$, leaving the large scale's slice empty - a violation of Assumption 5 that the algorithm cannot detect. The theory's engine, Lemma 3.1, predicts that the large-scale clusters become under-connected in the multi-kernel graph. If multi-KSC still returns zero misclassification with probability tending to one under such quantile choices, the guarantee is stronger than its stated assumptions; if instead the large-scale clusters are systematically merged and the misclassification rate fails to decay at any polynomial rate in $n$, Assumption 5 is confirmed as the load-bearing premise.

Watch

Extended reading notes

Core claim

The paper's central claim is that the multi-kernel spectral embedding is faithful to the cluster structure row by row, not just globally. For the empirical multi-kernel matrix $K$ with entries $\sum_{t=1}^T \alpha_t \exp(-\|x_i-x_j\|^2/h_t)$, the paper constructs a blockwise-constant informative matrix $\bar{K}$ of rank at most $m$, whose eigenvectors are constant on each cluster, and proves that the leading eigenspace of $K$ deviates from that of $\bar{K}$ by at most $\rho/\sqrt{n}+1/n^{3/2}$ in the $\ell_{2,\infty}$ norm (maximum row norm) in the optimal eigengap regime, where $\rho=\max_{k,\ell}\psi_{k\ell}/\theta_{k\ell}$ compares each pairwise-distance fluctuation to its own characteristic scale. The eigenvalue-weighted embedding obeys the analogous bound $\rho+1/n$, and the same rates hold for the normalized Laplacian $L=nD^{-1/2}KD^{-1/2}$. Because these are per-row bounds, every embedded point stays close to its cluster's population center, which is exactly what a $k$-means oracle can exploit. The endpoint is Theorem 3.3: the label map produced by Algorithm 1 satisfies $\mathrm{P}\{M(\hat\pi,\bar\pi)=0\}\ge 1-n^{-C}$ for every $C>0$.

Load-bearing premise

Assumption 5 requires that for every characteristic distance scale of the data, at least one chosen quantile level falls inside that scale's slice of the empirical distance distribution, but the slice boundaries are defined through the true, unobserved cluster partition and scale composition, so the exact-recovery guarantee for the data-driven bandwidth rule is conditional on information the algorithm is never given; if a scale's slice contains no quantile level, Lemma 3.1 does not establish admissibility of the empirical bandwidths, and the perturbation bounds for $K(\boldsymbol h)$ do not go through.

Editorial extensions

If this is right

  • The quantile rule (3.2) needs no labels and no population-scale information, and the theory covers any prescribed non-degenerate kernel weights, uniform weights included; the implied risk bound is $\mathbb{E}M(\hat\pi,\bar\pi)\le n^{-C}$ for every fixed $C$ and all large $n$.
  • Because the perturbation bounds are row-wise, the empirical embedding of every point stays in a small $\ell_{2,\infty}$ neighborhood of its cluster's population center, which is precisely the condition that lets an approximate $k$-means oracle convert embedding fidelity into exact labels.
  • The normalized-Laplacian variant of Algorithm 1 carries the same rates, so the same guarantees hold when the embedding is built from $L=nD^{-1/2}KD^{-1/2}$.
  • The scale-matched analysis beats the standard single-kernel Lipschitz concentration bound in exactly the multi-scale regime: in the paper's four-cluster example the competing bound stays of constant order relative to its reference matrix, while the multi-kernel bound is $o(1)$ whenever $n^\varepsilon\ll\sqrt{p}$.
  • The theorems are stated for RBF kernels but the proof uses only bounded first and second derivatives and a tail-decay condition on the kernel profile, so the same bounds cover general distance-based kernels of the form $f_t(\|x-y\|^2/\hbar_t)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Assumption 5 is the one condition the algorithm cannot check: the quantile levels must hit each scale's slice of the distance distribution, but the slice boundaries are defined through the true, unobserved cluster partition. A workaround the authors do not state is to oversample the quantile levels (take $T$ growing slowly with $n$): the admissibility argument needs only one hit per scale, so an o
  • The proof separates the polynomial-tail concentration assumption from the combinatorial exact-recovery step, which suggests the failure probability is limited by Assumption 2 rather than by the $k$-means stage; under sub-Gaussian latent vectors the same mechanism should sharpen the $n^{-C}$ tail to an exponential one, matching the rate that SVD-based spectral clustering achieves for isotropic Gaus
  • The blockwise informative-matrix construction is the same device used in community detection, where the population adjacency matrix is blockwise constant; the multi-scale treatment developed here suggests an analogous entrywise theory for weighted stochastic block models whose communities have heterogeneous connection scales, a setting where a single resolution parameter is known to fail.
  • The simulations use quadratically spaced quantile levels and find that covering the two relevant scales, not the number of kernels, drives performance; if that diagnosis is right, simpler uniformly spaced levels should perform comparably once the number of kernels is moderate, a prediction that can be tested directly in the paper's own six-cluster benchmark.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies multi-kernel spectral clustering with RBF kernels and bandwidths selected as empirical quantiles of pairwise squared distances. It considers a high-dimensional mixture model with heterogeneous cluster centers and covariance geometries, and approximates the empirical multi-kernel matrix by a blockwise-constant low-rank informative matrix. The main theoretical results are: (i) high-probability eigenvalue and row-wise ℓ2,∞ eigenvector perturbation bounds for the multi-kernel matrix and its normalized Laplacian; (ii) an analysis of the quantile-based bandwidth selection rule showing that the selected bandwidths are close to admissible deterministic bandwidths under Assumption 5; and (iii) an exact-recovery guarantee (Theorem 3.3) for approximate K-means on the spectral embedding under Assumptions 1, 2, 4–7. The proof uses a two-stage perturbation argument and standard entrywise eigenspace perturbation techniques.

Significance. If valid, the results would provide the first entrywise eigenvector perturbation bounds for high-dimensional empirical kernel matrices in a multi-scale setting, improving on the ℓ2 bounds available from [4]. The scale-matched relative-error structure is a genuine conceptual advance, and the exact-recovery guarantee for a concrete multi-kernel algorithm with data-adaptive bandwidths would be a valuable theoretical foundation for practice. The paper is careful in its use of stochastic domination and provides detailed proofs that appear non-circular; the two-stage perturbation bounds and the bandwidth admissibility lemma are substantial technical contributions. The numerical experiments illustrate the multi-scale failure of single-kernel methods and support the qualitative claims.

major comments (2)
  1. [D.2, Lemma D.3] The proof of Lemma D.3 asserts 'Without loss of generality, we take the embedding dimension in (3.11) to be r=m' and then derives the separation bound (D.18) for the m-dimensional centers. However, Theorem 3.3 is stated for Algorithm 1 with an arbitrary prespecified embedding dimension r, and Assumption 7 only controls the separation of the r-dimensional centers defined in (3.11). The m-dimensional separation bound does not imply the r-dimensional separation bound, since projection onto the first r coordinates can only decrease distances between the centers. Consequently, the proof of Theorem 3.3 does not cover the case r<m, which is explicitly within the theorem's scope. This is a load-bearing gap; the authors should either prove an r-dimensional analogue of Lemma D.3 using the r-dimensional perturbation bounds already established in Corollary 3.2, or restrict the statement of Theorem 3.3 to r=m.
  2. [3, Assumption 5 and Lemma 3.1] The guarantee for the data-driven bandwidth selection rule is conditional on Assumption 5, which requires that for each characteristic scale s there is a quantile level ω_t lying in the interval (N_{<s}/N, (N_{<s}+N_s)/N). The endpoints of these intervals depend on the true cluster partition and on the scale counts N_s, which are not computable from the observed data without knowing the labels or population scales. Thus the advertised claim that the bandwidths 'capture the relevant distance scales without requiring prior population-scale information' is not established as a theorem: the user must choose ω_t so that Assumption 5 happens to hold, and the paper provides no verifiable sufficient condition or practical selection rule ensuring this. The numerical example uses a specific choice of ω_t, but no proof is given that Assumption 5 is satisfied there or in general. The authors should either provide checkable conditions on the quantile levels under which Assumption 5 holds, or temper the claim about data-driven scale selection.
minor comments (4)
  1. [Appendix A] The intermediate matrix in the two-stage perturbation analysis is denoted by garbled placeholder symbols such as '∝⌈⌈≀⊔⊣⌋⌋K' throughout Appendix A; this notation should be fixed and consistently defined.
  2. [D.1, proof of Corollary 3.2] In equation (D.7), the displayed argument reads 'Δ_r(𝚲(ℏ*))=[λ_r(ℏ)−λ_{r+1}(ℏ)]∧λ_r(ℏ)', mixing ℏ and ℏ*; the left-hand side should be Δ_r(𝚲(ℏ)).
  3. [D.1, proof of Lemma D.1] The text says 'the r.h.s. of (D.11a) and (D.11a)' where the second reference should be (D.11b).
  4. [2.2] The matrix L in (2.26) is a rescaled normalized affinity matrix rather than the usual normalized Laplacian; the authors acknowledge this and refer to L as the normalized Laplacian by abuse of terminology, which is acceptable but should be flagged earlier for the reader.

Circularity Check

1 steps flagged · score 2.0 of 10

Bandwidth admissibility is assumed rather than derived; the perturbation bounds and exact-recovery argument are otherwise self-contained.

  1. self definitional [Section 3, Assumption 5 (page 18) and Lemma 3.1 (page 19)]
    "Intuitively, condition (3.6), though formulated in a different way, essentially plays the same role as the second constraint in (2.7): each characteristic scale θ_s is captured by at least one bandwidth h_t = G^{-1}(ω_t)."

    Assumption 5 posits that for every characteristic scale θ_s there is a quantile level ω_t inside the interval (N_<s/N, (N_<s+N_s)/N), where N_s counts true pairwise distances whose deterministic proxy lies at scale s. Lemma 3.1 then proves that the proxy bandwidths ℏ*_t are admissible by directly invoking this condition: its proof says 'By Assumption 5, there exists some t ... ℏ*_t = Gbar^{-1}(ω_t) ∈ {θ_kℓ : θ_kℓ ∈ [c1 θ_s, θ_s/c1]}'. That is exactly the second half of Definition 2.1, namely that every characteristic scale is represented by some bandwidth of the same order.

full rationale

The paper's perturbation theory is derived rather than fitted: the informative matrix Kbar is constructed from the true blockwise structure and the bounds are proven under concentration and eigengap assumptions. No fitted parameter is renamed as a prediction, and the exact-recovery theorem is a conditional statement built on those bounds. There are no load-bearing self-citations; Lemma D.2 is imported from the external reference [1] and reproduced, and the other cited tools are standard. The one notable circularity is the bandwidth-admissibility step: Assumption 5 essentially assumes that the quantile levels are already placed so that every scale is hit, and Lemma 3.1 uses that assumption verbatim to conclude admissibility. This makes the data-adaptive bandwidth claim partially tautological. Separately, the skeptical reader's point about Lemma D.3's 'Without loss of generality, we take the embedding dimension in (3.11) to be r=m' is a real proof gap for Theorem 3.3 when r<m, but it is a correctness concern rather than a circular reduction and therefore does not raise this circularity score. Overall, the central spectral perturbation results are self-contained, so a low score is appropriate.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The central claim is carried by the high-dimensional mixture model, the stochastic-domination concentration assumption, the n-power scale separation, and the eigengap and separation conditions. None of these is fitted; they are the modeling envelope. The method's own hyperparameters (kernel weights, quantile levels, embedding dimension, K-means approximation parameter) are user inputs and are therefore listed as free parameters even though they are not tuned in the paper.

free parameters (4)
  • kernel weights alpha_t
    Prescribed inputs in Algorithm 1; Assumption 4 only requires alpha_t >= c4. They are never learned or fit to data, but the exact recovery guarantee depends on them through the informative matrix.
  • quantile levels omega_t
    Prescribed inputs in Algorithm 1 step 1; Assumption 5 requires each omega_t to lie in intervals determined by true cluster-scale counts, so choosing them in practice requires unobservable scale information.
  • embedding dimension r
    Prespecified input; Assumptions 6 and 7 assume an eigengap and separation at this r, and the proof of Lemma D.3 operates with r=m.
  • K-means approximation parameter epsilon*
    Input to Algorithm 1; the near-optimality condition in Lemma D.2 uses B=1+epsilon*.
assumptions (7)
  • domain assumption Data model (2.2): x_i = mu_k + A_k z_i for i in cluster k, with E z_i=0 and Cov z_i=I; no independence of coordinates of z_i is required.
    Used throughout Section 2 and the theorems; the blockwise approximation and theta_kl are computed under it. It limits scope to affine latent-variable mixtures.
  • domain assumption Assumption 2 concentration: |<a,z_i>| is stochastically dominated by ||a|| and |<z_i,B z_i> - Tr B| by ||B||_F, uniformly in i.
    This is the engine for pairwise distance concentration and for the random matrix lemmas; the paper notes it is satisfied by bounded-moment or log-concave isotropic vectors when min d_k >= n^c.
  • domain assumption Assumption 1: pairwise mean squared distances theta_kl cluster into T1 scales separated by powers of n, with theta_kl in union of [c1 theta_s, theta_s/c1] and theta_{s+1}/theta_s >= n^{c1}.
    Defines the multi-scale structure and makes the index sets S_kl(0) and S_kl(1) partition all kernels; powers of n separate scales because all bounds use stochastic domination with n^epsilon.
  • domain assumption Assumptions 3, 3' and 6: effective eigengaps Delta_r of the informative kernel or Laplacian satisfy n^3 rho^2 / Delta^3 <= n^{-2c3} and Delta >= n^{c3}, or Delta >= c6 n in the data-adaptive case.
    Needed for Davis-Kahan-type inverse eigenvalue control and to keep perturbation terms subleading.
  • domain assumption Assumption 5: quantile levels omega_t lie in intervals defined by true cluster-scale pair counts N_s/N.
    Used in Lemma 3.1 to translate empirical quantiles into admissible bandwidths; unverifiable without labels.
  • domain assumption Assumption 7: population centers are separated by n^{c7}(rho + 1/n).
    Needed to convert entrywise embedding perturbations into zero misclassification via Lemma D.2.
  • standard math Standard results: Davis-Kahan sin Theta theorem, Rouche's theorem, resolvent and decoupling estimates, matrix square root perturbation bounds.
    Used as black boxes in Sections A through D.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery." pith.science (2026). https://pith.science/paper/A7C3M6MO

@misc{pith2026260808704,
  author       = {Pith},
  title        = {Pith review of: Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A7C3M6MO}},
  note         = {Machine review of arXiv:2608.08704}
}
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.

Figures

Figures reproduced from arXiv: 2608.08704 by the authors.

Figure 1
Figure 1. Single-kernel matrix in the two-cluster example. [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Single-kernel matrix in the multi-scale four-cluster example. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Spectral embedding produced by the multi-kernel matrix in the multi-scale four-cluster example. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Misclassification rates over 500 replications for the oracle-tuned single-KSC benchmark and multi-KSC with 𝑇 = 3 and 𝑇 = 4. in [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: Comparison of spectral embeddings from the multi-kernel matrix ( [PITH_FULL_IMAGE:figures/full_fig_p023_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 29 canonical work pages

  1. [4]

    Concentration of kernel matrices with application to kernel spectral clustering

    A. A. Amini and Z. S. Razaee. “Concentration of kernel matrices with application to kernel spectral clustering”. The Annals of Statistics49(2021), pp. 531–556.doi:10.1214/20-AOS1967

    work page doi:10.1214/20-aos1967 2021

  2. [1]

    Anℓ𝑝 theory of PCA and spectral clustering

    E. Abbe, J. Fan, and K. Wang. “Anℓ𝑝 theory of PCA and spectral clustering”. The Annals of Statistics50(2022), pp. 2359–2385.doi:10.1214/22-AOS2196

    doi:10.1214/22-aos2196 2022

  3. [2]

    Entrywise eigenvector analysis of random matrices with low expected rank

    E. Abbe, J. Fan, K. Wang, and Y. Zhong. “Entrywise eigenvector analysis of random matrices with low expected rank”. The Annals of Statistics48(2020), pp. 1452–1474.doi:10.1214/19-AOS1854

    doi:10.1214/19-aos1854 2020

  4. [3]

    Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence

    J. Agterberg, Z. Lubberts, and C. E. Priebe. “Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence”. IEEE Transactions on Information Theory68(2022), pp. 4618–4650.doi:10. 1109/TIT.2022.3159085

    arXiv 2022

  5. [5]

    Multiple kernel learning, conic duality, and the SMO algorithm

    F. R. Bach, G. R. G. Lanckriet, and M. I. Jordan. “Multiple kernel learning, conic duality, and the SMO algorithm”. Proceedings of the twenty-first international conference on Machine learning. ICML ’04. New York, NY, USA: Association for Computing Machinery, 2004, p. 6.doi:10.1145/1015330.1015424

    arXiv 2004

  6. [6]

    Extreme eigenvalues of log-concave ensemble

    Z. Bao and X. Xu. “Extreme eigenvalues of log-concave ensemble”. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques61(2025), pp. 155–184.doi:10.1214/23-AIHP1439

    work page doi:10.1214/23-aihp1439 2025

  7. [7]

    Matrix Perturbation: Davis-Kahan in the Infinity Norm

    A. Bhardwaj and V. Vu. “Matrix Perturbation: Davis-Kahan in the Infinity Norm”.Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Proceedings. Society for Industrial and Applied Mathe- matics, 2024, pp. 880–934.doi:10.1137/1.9781611977912.34

    doi:10.1137/1.9781611977912.34 2024

  8. [8]

    Signal-plus-noisematrixmodels:eigenvectordeviationsandfluctuations

    J.Cape,M.Tang,andC.E.Priebe.“Signal-plus-noisematrixmodels:eigenvectordeviationsandfluctuations”.Biometrika 106(2019), pp. 243–250.doi:10.1093/biomet/asy070

    doi:10.1093/biomet/asy070 2019

Show all 55 references
  1. [9]

    The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics

    J. Cape, M. Tang, and C. E. Priebe. “The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics”. The Annals of Statistics47(2019), pp. 2405–2439.doi:10.1214/18-AOS1752

    2019 doi

  2. [10]

    On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence

    D. Chafaï and K. Tikhomirov. “On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence”. Probability Theory and Related Fields170(2018), pp. 847–889.doi:10.1007/s00440-017-0778-9

    2018 doi

  3. [11]

    An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture

    Y. Chen. “An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture”. Geometric and Functional Analysis31(2021), pp. 34–61.doi:10.1007/s00039-021-00558-4

    2021 doi

  4. [12]

    Spectral Methods for Data Science: A Statistical Perspective

    Y. Chen, Y. Chi, J. Fan, and C. Ma. “Spectral Methods for Data Science: A Statistical Perspective”. Foundations and Trends in Machine Learning14(2021), pp. 566–806.doi:10.1561/2200000079

    2021 doi

  5. [13]

    The spectrum of random inner-product kernel matrices

    X. Cheng and A. Singer. “The spectrum of random inner-product kernel matrices”. Random Matrices: Theory and Applications02(2013), p. 1350010.doi:10.1142/S201032631350010X

    2013 doi

  6. [14]

    Y. S. Chow and H. Teicher.Probability Theory: Independence, Interchangeability, Martingales. Springer Science & Business Media, 2012.isbn: 978-1-4612-1950-7

    2012

  7. [15]

    Algorithms for Learning Kernels Based on Centered Alignment

    C. Cortes, M. Mohri, and A. Rostamizadeh. “Algorithms for Learning Kernels Based on Centered Alignment”. Journal of Machine Learning Research13(2012), pp. 795–828.url:http://jmlr.org/papers/v13/cortes12a.html. 61 Multi-kernel spectral clustering References

    2012

  8. [16]

    Kernel spectral clustering of large dimensional data

    R. Couillet and F. Benaych-Georges. “Kernel spectral clustering of large dimensional data”. Electronic Journal of Statistics10(2016), pp. 1393–1454.doi:10.1214/16-EJS1144

    2016 doi

  9. [17]

    TheRotationofEigenvectorsbyaPerturbation.III

    C.DavisandW.M.Kahan.“TheRotationofEigenvectorsbyaPerturbation.III”.SIAMJournalonNumericalAnalysis 7(1970), pp. 1–46.doi:10.1137/0707001

    1970 doi

  10. [18]

    Learninglow-dimensionalnonlinearstructuresfromhigh-dimensionalnoisydata:anintegraloperator approach

    X.DingandR.Ma.“Learninglow-dimensionalnonlinearstructuresfromhigh-dimensionalnoisydata:anintegraloperator approach”. The Annals of Statistics51(2023), pp. 1744–1769.doi:10.1214/23-AOS2306

    2023 doi

  11. [19]

    Impactofsignal-to-noiseratioandbandwidthongraphLaplacianspectrumfromhigh-dimensional noisy point cloud

    X.DingandH.-T.Wu.“Impactofsignal-to-noiseratioandbandwidthongraphLaplacianspectrumfromhigh-dimensional noisy point cloud”. IEEE Transactions on Information Theory69(2023), pp. 1899–1931.doi:10.1109/TIT.2022. 3216561

    2023 doi

  12. [20]

    Onthespectralpropertyofkernel-basedsensorfusionalgorithmsofhighdimensionaldata

    X.DingandH.-T.Wu.“Onthespectralpropertyofkernel-basedsensorfusionalgorithmsofhighdimensionaldata”.IEEE Transactions on Information Theory67(2021), pp. 640–670.doi:10.1109/TIT.2020.3026255

    2021

  13. [21]

    The spectrum of random kernel matrices: universality results for rough and varying kernels

    Y. Do and V. Vu. “The spectrum of random kernel matrices: universality results for rough and varying kernels”. Random Matrices: Theory and Applications02(2013), p. 1350005.doi:10.1142/S2010326313500056

    2013 doi

  14. [22]

    Dubova, Y

    S. Dubova, Y. M. Lu, B. McKenna, and H.-T. Yau.Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime. 2023.url:http://arxiv.org/abs/2310.18280

    2023 arXiv

  15. [23]

    Unperturbed:spectralanalysisbeyondDavis-Kahan

    J.Eldridge,M.Belkin,andY.Wang.“Unperturbed:spectralanalysisbeyondDavis-Kahan”.ProceedingsofAlgorithmic Learning Theory. PMLR, 2018, pp. 321–358.url:https://proceedings.mlr.press/v83/eldridge18a.html

    2018

  16. [24]

    Erdős and H.-T

    L. Erdős and H.-T. Yau.A Dynamical Approach to Random Matrix Theory. American Mathematical Soc., 2017.isbn: 978-1-4704-3648-3

    2017

  17. [25]

    Anℓ∞ Eigenvector Perturbation Bound and Its Application

    J. Fan, W. Wang, and Y. Zhong. “Anℓ∞ Eigenvector Perturbation Bound and Its Application”. Journal of Machine Learning Research18(2018), pp. 1–42

    2018

  18. [26]

    Z. Fan, R. Ma, E. Paquette, and Z. Wang.Anisotropic local law for non-separable sample covariance matrices. 2026.doi: 10.48550/arXiv.2602.17960

    2026 doi

  19. [27]

    Thespectralnormofrandominner-productkernelmatrices

    Z.FanandA.Montanari.“Thespectralnormofrandominner-productkernelmatrices”.ProbabilityTheoryandRelated Fields173(2019), pp. 27–85.doi:http://dx.doi.org/10.1007/s00440-018-0830-4

    2019 doi

  20. [28]

    Garreau, W

    D. Garreau, W. Jitkrittum, and M. Kanagawa.Large Sample Analysis of the Median Heuristic. 2018.doi:10.48550/ arXiv.1707.07269

    2018 doi arXiv

  21. [29]

    MultipleKernelLearningAlgorithms

    M.GönenandE.Alpaydin.“MultipleKernelLearningAlgorithms”.JournalofMachineLearningResearch12(2011), pp. 2211–2268.url:http://jmlr.org/papers/v12/gonen11a.html

    2011

  22. [30]

    Metric andKernelLearning UsingaLinearTransformation

    P.Jain, B.Kulis,J. V.Davis,and I.S.Dhillon.“Metric andKernelLearning UsingaLinearTransformation”. Journalof Machine Learning Research13(2012), pp. 519–547.url:http://jmlr.org/papers/v13/jain12a.html

    2012

  23. [31]

    On information plus noise kernel random matrices

    N. E. Karoui. “On information plus noise kernel random matrices”. The Annals of Statistics38(2010), pp. 3191–3216. doi:10.1214/10-AOS801

    2010 doi

  24. [32]

    Thespectrumofkernelrandommatrices

    N.E.Karoui.“Thespectrumofkernelrandommatrices”.TheAnnalsofStatistics38(2010),pp.1–50.doi:10.1214/08- AOS648

    2010 doi

  25. [33]

    Bourgain’s slicing problem and KLS isoperimetry up to polylog

    B. Klartag and J. Lehec. “Bourgain’s slicing problem and KLS isoperimetry up to polylog”. Geometric and Functional Analysis32(2022), pp. 1134–1159.doi:10.1007/s00039-022-00612-9

    2022 doi

  26. [34]

    ℓ 𝑝-NormMultipleKernelLearning

    M.Kloft,U.Brefeld,S.Sonnenburg,andA.Zien.“ℓ 𝑝-NormMultipleKernelLearning”.JournalofMachineLearning Research12(2011), pp. 953–997

    2011

  27. [35]

    Kogan, S

    D. Kogan, S. Nandy, and J. Huang.Extremal eigenvalues of random kernel matrices with polynomial scaling. 2024.doi: 10.48550/arXiv.2410.17515

    2024 doi arXiv

  28. [36]

    Randommatrixapproximationofspectraofintegraloperators

    V.KoltchinskiiandE.Giné.“Randommatrixapproximationofspectraofintegraloperators”.Bernoulli6(2000),pp.113– 167.doi:10.2307/3318636. 62 Multi-kernel spectral clustering References

    2000 doi

  29. [37]

    Learning the Kernel Matrix with Semidefinite Programming

    G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan. “Learning the Kernel Matrix with Semidefinite Programming”. Journal of Machine Learning Research5(2004), pp. 27–72.url:https://www.jmlr. org/papers/v5/lanckriet04a.html

    2004

  30. [38]

    Lei.Unifiedℓ 2→∞ Eigenspace Perturbation Theory for Symmetric Random Matrices

    L. Lei.Unifiedℓ 2→∞ Eigenspace Perturbation Theory for Symmetric Random Matrices. 2020.doi:10.48550/arXiv. 1909.04798

    2020 doi arXiv

  31. [39]

    OptimalityofspectralclusteringintheGaussianmixturemodel

    M.Löffler,A.Y.Zhang,andH.H.Zhou.“OptimalityofspectralclusteringintheGaussianmixturemodel”.TheAnnals of Statistics49(2021), pp. 2506–2530.doi:10.1214/20-AOS2044

    2021 doi

  32. [40]

    Anequivalenceprincipleforthespectrumofrandominner-productkernelmatriceswithpolynomial scalings

    Y.M.LuandH.-T.Yau.“Anequivalenceprincipleforthespectrumofrandominner-productkernelmatriceswithpolynomial scalings”. The Annals of Applied Probability35(2025), pp. 2411–2470.doi:10.1214/25-AAP2176

    2025 doi

  33. [41]

    ConsistencyofSpectralClustering

    U.vonLuxburg,M.Belkin,andO.Bousquet.“ConsistencyofSpectralClustering”.TheAnnalsofStatistics36(2008), pp. 555–586.doi:10.1214/009053607000000640

    2008 doi

  34. [42]

    Estimating Mixed Memberships With Sharp Eigenvector Deviations

    X. Mao, P. Sarkar, and D. Chakrabarti. “Estimating Mixed Memberships With Sharp Eigenvector Deviations”. Journal of the American Statistical Association116(2021), pp. 1928–1940.doi:10.1080/01621459.2020.1751645

    2021

  35. [43]

    On spectral clustering: analysis and an algorithm

    A. Y. Ng, M. I. Jordan, and Y. Weiss. “On spectral clustering: analysis and an algorithm”. Proceedings of the 15th InternationalConferenceonNeuralInformationProcessingSystems:NaturalandSynthetic.NIPS’01.Cambridge, MA, USA: MIT Press, 2001, pp. 849–856.url:https://dl.acm.org/do...

    2001

  36. [44]

    SimpleMKL

    A. Rakotomamonjy, F. R. Bach, S. Canu, and Y. Grandvalet. “SimpleMKL”. Journal of Machine Learning Research 9(2008), pp. 2491–2521.url:http://jmlr.org/papers/v9/rakotomamonjy08a.html

    2008

  37. [45]

    TheGeometryofKernelizedSpectralClustering

    G.Schiebinger,M.J.Wainwright,andB.Yu.“TheGeometryofKernelizedSpectralClustering”.TheAnnalsofStatistics 43(2015), pp. 819–846.doi:10.1214/14-AOS1283

    2015 doi

  38. [46]

    Perturbationboundsformatrixsquarerootsandpythagoreansums

    B.A.Schmitt.“Perturbationboundsformatrixsquarerootsandpythagoreansums”.LinearAlgebraanditsApplications 174(1992), pp. 215–227.doi:10.1016/0024-3795(92)90052-C

    1992 doi

  39. [47]

    Schölkopf and A

    B. Schölkopf and A. J. Smola.Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2002.isbn: 978-0-262-19475-4

    2002

  40. [48]

    Normalized cuts and image segmentation

    J. Shi and J. Malik. “Normalized cuts and image segmentation”. IEEE Transactions on Pattern Analysis and Machine Intelligence22(2000), pp. 888–905.doi:10.1109/34.868688

    2000 doi

  41. [49]

    LargeScaleMultipleKernelLearning

    S.Sonnenburg,G.Rätsch,C.Schäfer,andB.Schölkopf.“LargeScaleMultipleKernelLearning”.JournalofMachine Learning Research7(2006), pp. 1531–1565.url:http://jmlr.org/papers/v7/sonnenburg06a.html

    2006

  42. [50]

    Covarianceestimationfordistributionswith2+𝜀moments

    N.SrivastavaandR.Vershynin.“Covarianceestimationfordistributionswith2+𝜀moments”.TheAnnalsofProbability 41(2013), pp. 3081–3111.doi:10.1214/12-AOP760

    2013 doi

  43. [51]

    G. W. Stewart and J.-g. Sun.Matrix Perturbation Theory. Computer Science and Scientific Computing. Boston: Academic Press, 1990

    1990

  44. [52]

    Vershynin.High-dimensional probability: an introduction with applications in data science

    R. Vershynin.High-dimensional probability: an introduction with applications in data science. Cambridge University Press, 2018.isbn: 978-1-108-41519-4

    2018

  45. [53]

    Analysis of Singular Subspaces under Random Perturbations

    K. Wang. “Analysis of Singular Subspaces under Random Perturbations”. The Annals of Statistics54(2026), pp. 667– 691.doi:10.1214/25-AOS2582

    2026 doi

  46. [54]

    Perturbation bounds in connection with singular value decomposition

    P.-Å. Wedin. “Perturbation bounds in connection with singular value decomposition”. BIT Numerical Mathematics12 (1972), pp. 99–111.doi:10.1007/BF01932678

    1972 doi

  47. [55]

    MetricLearningforKernelRegression

    K.Q.WeinbergerandG.Tesauro.“MetricLearningforKernelRegression”.ProceedingsoftheEleventhInternational Conference on Artificial Intelligence and Statistics. PMLR, 2007, pp. 612–619.url:https://proceedings.mlr. press/v2/weinberger07a.html. 63

    2007

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.