Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

1.1. Clustering and the Gaussian mixture model.

• The minimum separation between Gaussian-mixture cluster centers governs recovery difficulty, while spectral methods project data onto a subspace before clustering.The section also situates direct k-means minimization and mixture-likelihood fitting as other methodological families.Source: §1.1 · pp. 2–3

1.2. Segmenting data with imbalanced clusters.

• Average misclustering error can be small even when a minority cluster is entirely lost, motivating worst-case error assessment across clusters.Much existing theoretical work focuses on balanced clusters, where the largest-to-smallest size ratio stays bounded as problem size grows.Source: §1.2 · p. 3

1.3.1. Clustering and Gaussian Determinantal Processes.

• The truncated covariance approach focuses on pairs that straddle clusters, because within-cluster pairs carry no center information and dominate when one cluster is large.Earlier work by Ghosh and Rigollet [41] studied truncated covariance-type statistics in the context of Gaussian Determinantal Processes.Source: §1.3.1 · pp. 3–4

1.3.2. The Widom-Rowlinson Model as a mechanism for cluster formation.

• The Widom–Rowlinson model offers a physical picture of cluster formation, but the paper’s analysis is entirely under a Gaussian mixture model.The statistical-mechanical discussion is motivational; the Widom–Rowlinson model’s properties are not amenable to simple closed-form analysis.Source: §1.3.2 · p. 4

1.3.3. Kernelised and truncated covariance matrices.

• Kernelised covariance matrices generalize the truncated statistic, but the far-neighbour indicator kernel is more appropriate than alternatives such as the Gaussian kernel for imbalanced clustering.The general form uses an interaction kernel between data points, modulated by a parameter.Source: §1.3.3 · p. 5

2.1. Notation.

• The notation specifies vector and matrix norms, indicator vectors, identity and all-ones matrices, positive semidefinite square roots, and orthogonal projections.It also defines log+ and central and noncentral chi-square notation.Source: §2.1 · p. 5

2.2. Gaussian Mixture Model.

• In the isotropic Gaussian mixture model, the goal is to estimate cluster labels, and weak separation occurs when center gaps are smaller than typical noise length.In that regime, pairwise distances still contain aggregate information; the algorithm uses a lower bound on minimum separation rather than requiring its exact value.Source: §2.2 · pp. 6–7

2.3. Classical PCA based dimension reduction and clustering.

• Centered PCA projects observations onto the leading left singular subspace of the centered data matrix, then applies k-means to the reduced-dimensional observations.Centering makes the data translation invariant.Source: §2.3 · pp. 7–8

3. Key ingredients and approach

• The method keeps pairwise terms carrying information about differences between cluster centers and removes within-cluster terms from the covariance construction.The resulting kernelised covariance is formed through the data Laplacian.Source: §3 · p. 8, §3.2 · pp. 10–11

3.1.1. Data truncation matrices.

• Data truncation matrices use a threshold function to form a kernel matrix and its degree and Laplacian matrices; ideal truncation selects cross-cluster pairs and excludes same-cluster pairs.The ideal selection matrix equals one on cross-cluster pairs and zero on same-cluster pairs.Source: §3.1 · p. 9, §3.1.1 · p. 9, §3.1.2 · p. 10

3.2. The transformed data and noise reduction.

• The ideal transform preserves the full centered signal while reducing noise from O(σ√p + n) to O(σ√p + m).Here m is the number of observations outside the largest cluster.Source: §3.2 · p. 11

3.3. Dimension reduction after truncation.

• The truncated covariance’s leading singular directions estimate the signal subspace and can also be obtained from its eigendecomposition.The dimension-reduction error is measured against the true signal subspace.Source: §3.3 · p. 11

3.4. Clustering post dimension reduction.

• After projecting to dimension r, the clustering procedure applies global k-means to the projected data points.The text gives typical choices r = min{p, k} or r = min{p, k−1}.Source: §3.4 · p. 12

3.5. Metrics for clustering error.

• Maximum clustering error complements average error because a dominant cluster can make average loss hide mistakes on smaller clusters.Source: §3.5 · p. 12

3.6. On the choice of the kernel function.

• Hard truncation distinguishes pair types once ∆≫σp^1/4, whereas smooth Gaussian kernels cannot make their expected within- and cross-cluster entries simultaneously approximate the ideal selection in the regime ∆=o(σ√p).The paper therefore uses a hard threshold for later dimension reduction and clustering.Source: §3.6 · pp. 13–14

4.1. Dimension Reduction.

• When h=o(p), dimension reduction permits Δ=o(σ√p), with transformed perturbation controlled by a reduced noise scale plus truncation error at high probability.Source: §4.1 · p. 15
• The approach has a separation barrier around Δ≈σp^1/4: below it, within- and cross-cluster distance means cannot compete reliably with random fluctuations.When Δ=o(σp^1/4), the kernel matrix carries almost no useful information about whether a pair is within or across clusters.Source: §4.1 · p. 15
• When √p(p+m)≪n, the transformed perturbation bound replaces n in PCA’s σ√p+n term with m, plus a truncation-error term.The authors identify this as an improved guarantee, including under weak separation.Source: §4.1 · p. 16

4.2. Clustering Accuracy.

• When H=o(p), the clustering separation condition permits Δ/σ of order (pH)^1/4=o(√p), guaranteeing performance in the weak-separation regime.Source: §4.2 · p. 17
• For k=2 with n_min=m≈p≈n^1/2, truncation requires Δ/σ≈n^1/8, versus ≈n^1/4 for classical PCA spectral clustering.Source: §4.2 · p. 19

5. Simulation experiments

• The simulations fix n = 4096, p = 128, and σ = 1; for k = 2, cluster sizes are (4096 − m, m), with m = 2048, 512, 128, or 32.For k = 5, imbalanced allocations use m = 512, 128, or 64, where m is the total size outside the largest cluster.Source: §5 · p. 19
• Truncated uses Algorithm 1 with r = k − 1 and a hard threshold, while centered PCA and Zhang–Zhou PCA use different centered or uncentered leading singular directions.Each method applies k-means to its projected data; Lloyd’s algorithm is used for the k-means step.Source: §5 · pp. 19–20
• Average and worst-cluster errors are reported across eight Gaussian-noise replicates, with descriptive approximate 95% pointwise intervals.The worst-cluster error is the maximum loss across clusters.Source: §5 · p. 20, Figure 1 · p. 20
• In imbalanced two- and five-cluster settings, truncation becomes effective at weaker separations than PCA, with larger advantages as imbalance grows and minority clusters become uneven.For the two-cluster simulations, balanced performance is comparable; the five-cluster experiments include varying minority allocations.Source: §5 · pp. 20–21, Figure 1 · p. 20, Figure 2 · p. 21

6. Proof overview

• The proof first bounds the operator-norm difference between transformed data and the centered signal, then extends the ideal-truncation analysis to the data-dependent transform.The resulting perturbation bound underpins both dimension-reduction and clustering results.Source: §6 · p. 21

6.1. Ideal truncation and noise reduction.

• The ideal Laplacian decomposition expresses its square root through weighted low-dimensional projections, preserving the centered signal while reducing transformed Gaussian noise.The argument uses the decomposition with Gaussian rotational invariance; when p + m ≤ n, the transformed noise has a smaller scale than the untransformed error.Source: §6.1 · pp. 21, 24

6.2. Error decomposition.

• The data-dependent transformation error splits into a signal-perturbation term and a transformed-noise term.The decomposition is X bS − Pc = P(bS − S0) + E bS.Source: §6.2 · p. 24

6.3. Bounding the signal perturbation.

• To bound signal perturbation, the proof linearizes the matrix square root and uses cancellation of same-cluster terms, then bounds cross-cluster errors by partitioning pairs into blocks.Within each block, distinct pairs have disjoint indices and the block size is at most m.Source: §6.3 · p. 25

6.4. Bounding the transformed noise.

• Because the data-dependent transform and Gaussian noise are dependent, the proof partitions pairs into blocks of disjoint-index terms, bounds each block, and combines the bounds with a union bound and net.This avoids conditioning on the transform when controlling transformed noise.Source: §6.4 · pp. 25–26

6.5. Dimension reduction and clustering error bounds.

• Combining signal and noise bounds gives the full transformed-data perturbation, which is used with spectral perturbation theory for dimension reduction and a k-means error bound for clustering.The combined perturbation is bounded by the sum of the signal-perturbation and transformed-noise norms.Source: §6.5 · p. 26

• The authors verified all steps and take responsibility for the final content.Source: §7.1 · p. 26
• The authors proposed the truncated estimator, related dimension-reduction and clustering methods, and the kernel-Laplacian analytical perspective.Source: §7.1 · p. 26
• Standard generative AI tools supported simulations, literature search, calculations, parts of proof development and simplification, and typesetting.Source: §7.1 · p. 26

Appendix A. Expectation of Data Truncation Matrices and Ideal Truncation

• The ideal Laplacian square root has a closed-form weighted-projection representation that preserves the centered signal and reduces effective noise dimension.The representation is identified as the key structural fact behind truncation.Source: Appendix A · p. 30
• When p + m ≤ n, the ideal transform improves the Gaussian-error scale from σ√p + n to σ√p + m with high probability.The probability bound is at least 1 − exp(−cA.3.1(p + m)).Source: Appendix A · pp. 30–31

Appendix B. Error Induced by Fluctuation of the Data Truncation Matrices

• For practical data truncation, the transform depends on the Gaussian error, so the analysis separately bounds signal perturbation and transformed noise.Source: Appendix B · p. 31

B.1. Signal perturbation.

• Square-root linearization converts signal error to a linear Laplacian difference; projection cancels same-cluster entries, and disjoint-pair blocks support matrix Bernstein control.The signal argument partitions dependent terms into blocks of disjoint index pairs.Source: §B.1 · pp. 31–32

B.2. Contribution from the noise.

• The noise bound controls the data-dependent transformed noise without assuming independence from the Gaussian noise matrix, using pairwise Laplacian blocks and a sphere net.Summands are independent within each disjoint-index block, so scalar Bernstein applies; independence between blocks is not required.Source: §B.2 · p. 32

B.3. Final perturbation bound.

• The final perturbation argument decomposes transformed-data error into signal and noise terms, then uses a triangle inequality to combine their bounds.The decomposition is X bS − Pc = P(bS − S0) + E bS.Source: §B.3 · pp. 33–34

Appendix C. Proof of Main Results on Dimension reduction

• Lemma C.1 is the singular-subspace perturbation tool, formulated for a rank-r matrix and the top-r left singular vectors of its perturbation.The proof later applies the lemma with the population matrix Pc and r = r0.Source: Appendix C · p. 34
• The proof identifies PS0 with Pc and uses the separation hypothesis to meet Proposition B.5's requirements for the transformed-data perturbation bound.The resulting operator bound holds with probability at least 1 − e^(-c1(p+m)).Source: Appendix C · p. 34
• Applying Lemma C.1 with M = Pc and r = r0 transfers the transformed-data perturbation bound to the claimed dimension-reduction result.The proof then substitutes the bound for ∥Y − Pc∥op.Source: Appendix C · p. 34

Appendix D. Proof of Main Results on Clustering Accuracy

• Theorem 4.6’s separation condition yields the deterministic clustering margin, and the perturbation bound holds outside an event of probability at most e^-c2(p+m).The proof uses an ideal cluster-constant target of rank at most min{k − 1, p} that preserves pairwise center separations, then derives two loss bounds.Source: Appendix D · pp. 34–36

Appendix E. Preliminaries

• The preliminaries provide bounds converting separation conditions, the unique PSD square root, the best rank-r approximation in operator norm, and a rank-one Laplacian expansion.These lemmas supply elementary matrix and approximation tools used in the proofs.Source: Appendix E · pp. 36–37

Appendix F. Partition into classes of disjoint pairs

• Pairs can be partitioned into classes of disjoint pairs; after restricting to cross-class pairs, each class contains at most m pairs.The construction uses N − 1 classes for even N and N for odd N.Source: Appendix F · pp. 38–39

Appendix G. Spectral k-means

• The spectral k-means lemma bounds clustering error through perturbation and shows that, after relabeling, all points outside the bad set are correctly classified.The proof establishes that every true cluster has a representative outside the bad set and that different clusters’ representatives receive distinct estimated labels.Source: Appendix G · pp. 39, 41

Appendix H. Measure concentration

• The measure-concentration preliminaries state a Bernstein inequality for sums of independent real-valued random variables under variance and boundedness assumptions.The lemma gives tail bounds for every t > 0.Source: Appendix H · p. 42
• Appendix H provides matrix Bernstein and chi-square concentration inequalities, alongside a distance-monotonicity lemma.These are presented as measure-concentration ingredients for the proofs.Source: Appendix H · pp. 42–43

Appendix I. Ingredients from high dimensional probability

• Appendix I supplies Gaussian vector and matrix norm bounds and a sphere-net size lemma for high-dimensional probability arguments.The appendix identifies these as Gaussian specializations and net consequences needed below.Source: Appendix I · pp. 44–45

Appendix J. Proofs for classical PCA results

• For Theorem 4.4, the proof bounds the noise operator norm and applies singular-subspace perturbation to centered data to control eigenspaces.The stated noise bound is ∥E∥op ≤ c1σ√p + n with probability at least 1 − e^(-c2n).Source: Appendix J · p. 45
• For Theorem 4.8, the centered population matrix is cluster-wise constant and has rank at most min{p, k − 1}, setting the target rank r*.The proof applies Lemma G.1 to the centered population and observed matrices.Source: Appendix J · p. 45
• Theorem 4.8's proof bounds centered noise and invokes the separation condition before applying Theorem G.1.The centered-noise operator bound is stated with probability at least 1 − e^(-c2n).Source: Appendix J · pp. 45–46

Data truncation matrices

• For every data realization, the data truncation Laplacian is symmetric positive semidefinite and annihilates the all-ones vector.The proof uses nonnegative adjacency weights and the quadratic form in pairwise coordinate differences.Source: Appendix K · p. 46

Expectation of data truncation matrices

• Lemma K.2 organizes expected truncation-matrix entries by same-cluster and cross-cluster pairs, then derives expected degrees and Laplacian entries.The displayed fragments identify a same-cluster expectation and use the diagonal degree matrix to obtain the Laplacian entries.Source: Appendix K · pp. 47–48

Monotonicity

• The truncation probability γ(d) is nondecreasing in cluster-mean separation d, with a further bound stated for separations at least Δ.The proof relates γ(d) to a noncentral chi-square probability and applies a tail estimate for the complementary event.Source: Appendix K · pp. 48–49

Orthogonal decomposition of the space

• The cluster partition yields an orthogonal decomposition of R^n into the constant-vector span, the centered cluster-constant subspace, and within-cluster zero-sum subspaces.The cluster-indicator matrix Q maps cluster coordinates to cluster-constant vectors, while each Π_a projects onto the zero-sum vectors supported on cluster a.Source: Appendix K · pp. 49–50

Factorization of the signal matrix

• The signal matrix factors through the cluster-indicator matrix Q, and its columns equal the corresponding cluster means.The factorization also implies that the signal matrix annihilates each within-cluster zero-sum projector Π_a.Source: Appendix K · pp. 50–51

Ideal truncation

• The ideal truncation Laplacian admits a cluster-subspace spectral decomposition, and its positive-semidefinite square root annihilates the all-ones vector.The decomposition is also used to identify the action on the population signal.Source: Appendix K · pp. 51–52

Perturbation identity

• The signal-side perturbation satisfies P(bL − L) = −PL(M), since the same-cluster contribution vanishes.This identity isolates the matrix M on cross-cluster pairs.Source: Appendix L · pp. 54–55

Concentration bounds

• A partition of unordered pairs into disjoint-index blocks gives independent summands for the concentration bounds.The proof uses these blocks to control the matrix contributions and obtains bounds simultaneously across blocks with high probability.Source: Appendix L · pp. 55–57

Perturbation bounds

• The perturbation argument requires no upper bound on pairwise distances d_ij once its moment condition is verified.The proof also derives the stated operator-norm controls with probability at least 1 − e^−(p+m).Source: Appendix L · pp. 54, 57, 59