Spectral partitioning for $k$-block averaging kernels of finite Markov chains

Michael C. H. Choi; Youjia Wang

stat.MLAug 21, 2026

Spectral partitioning for $k$ -block averaging kernels of finite Markov chains

Authors: Michael C. H. Choi, Youjia Wang

Organizations: Department of Statistics and Data Science, National University of Singapore, Level 7, 6 Science Drive 2, 117546, Singapore

Abstract

We develop spectral algorithms for selecting state-space partitions that define averaging kernels for finite, ergodic and reversible Markov chains. For a partition $\mathcal O$ , the Gibbs kernel $G_{\mathcal O}$ resamples within the current block from the stationary conditional distribution; when this update is tractable, composing or mixing it with a baseline kernel $P$ can accelerate convergence. We select $\mathcal O$ by rounding the bottom nonconstant eigenfunctions of $P^2$ , or the algebraically smallest eigenfunctions of $P$ for additive mixtures, using weighted $k$ -means. For $F(\mathcal O)=\|G_{\mathcal O}P-Π\|_{F,π}^2$ , we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $χ^2$ -mutual information between the initial block label and the state after one transition, giving this matrix objective a natural probabilistic interpretation. In the two-block case, a threshold sweep exactly solves the associated one-dimensional weighted two-means rounding problem. For general $k \geq 2$ , weighted $k$ -means rounds the bottom $(k-1)$ -dimensional embedding, after which candidates are rescored by $F$ ; the rounding distortion is a distance between subspaces that yields spectral approximation bounds. We extend the framework to additive mixtures, finite-horizon objectives, and discounted infinite-horizon objectives. In contrast to classical normalized spectral clustering, which uses top nonconstant modes to find low-flow persistent clusters, our method uses bottom modes to favor large normalized cross-block flow and rapid loss of block-label information. Experiments on a controlled-spectrum graph, a mean-field Ising model, and Bayesian variable selection show notable per-iteration improvements in convergence and statistical estimation.

Figures & tables

P^{2}\phi=\eta_{1}\phi,\qquad\|\phi\|_{\pi}=1.

Algorithm 1 Two-block spectral sweep

\widehat{\mathcal{O}}_{F}\in\operatorname*{argmin}_{s\in\mathopen{[\mkern-2.7mu[}\ell\mathclose{]\mkern-2.7mu]}}F(\mathcal{O}^{(s)}).

Algorithm 2 Multiway spectral sweep for

F

\widehat{\mathcal{O}}_{H}\in\operatorname*{argmin}_{s\in\mathopen{[\mkern-2.7mu[}\ell\mathclose{]\mkern-2.7mu]}}H(\mathcal{O}^{(s)}).

Algorithm 3 Additive-mixture multiway spectral sweep

\widehat{\mathcal{O}}_{\star}\in\operatorname*{argmin}_{s\in\mathopen{[\mkern-2.7mu[}\ell\mathclose{]\mkern-2.7mu]}}F_{\star}(\mathcal{O}^{(s)}).

Algorithm 4 Multi-horizon spectral sweep

Spectral sweep and embedding	Weighted $k$ -means surrogate	Exact candidate-selection objective	Selected output
One-step Frobenius sweep, Algorithm 2 . Bottom spectral subspace of $P^{2}$ and embedding $\Phi$ .	$\delta(\mathcal{O})$ , whose weighted $k$ -means representation is given in Proposition 4.1 .	$F(\mathcal{O})=\\|G_{\mathcal{O}}P-\Pi\\|_{F,\pi}^{2}$ (see ( 5 )).	$\widehat{\mathcal{O}}_{F}$
Additive-mixture sweep, Algorithm 3 . Bottom spectral subspace of $P$ and embedding $\Psi$ .	$\delta_{P}(\mathcal{O})$ , whose weighted $k$ -means representation is given in ( 34 ).	$H(\mathcal{O})=\\|A_{\mathcal{O}}-\Pi\\|_{F,\pi}^{2}$ (see ( 26 )).	$\widehat{\mathcal{O}}_{H}$
Multi-horizon sweep, Algorithm 4 . Bottom spectral subspace of $P^{2}$ and the same embedding $\Phi$ as in the one-step sweep.	The same rounding surrogate $\delta(\mathcal{O})$ as in Proposition 4.1 .	$F_{\star}(\mathcal{O})\in\bigl\{F_{w}^{T}(\mathcal{O}),F_{\gamma}^{\infty}(\mathcal{O})\bigr\}$ (see ( 41 ) and ( 42 )).	$\widehat{\mathcal{O}}_{\star}$ ( $\widehat{\mathcal{O}}_{\gamma}$ when $F_{\star}=F_{\gamma}^{\infty}$ )

Table 1: Comparison of the three multiway spectral sweep procedures. The second column gives the spectral rounding surrogate approximately minimized by weighted

k

-means, the third gives the original candidate-selection objective, and the rightmost column records the notation for the selected output.

Figure 1: Outputs of the four procedures for the controlled-spectrum chain with

\alpha=0.08

and

\varepsilon=0.03

. Algorithm 1 uses two blocks; Algorithms 2 – 4 use

k=4

blocks. Raw objective values should therefore not be used to rank procedures having different numbers of blocks.

Figure 2: Diagnostics for the controlled-spectrum chain with

\alpha=0.08

and

\varepsilon=0.03

. Left: all non-unit eigenvalues

\lambda_{j}(P)

P

(grey). Blue circles mark the

k-1=3

eigenvalues selected by the bottom spectrum of

P^{2}

, while red squares mark the

k-1=3

algebraically smallest eigenvalues of

P

. Center: the lagged Frobenius objective

F(P^{t},\mathcal{O})

. Right: the worst-case total-variation distance

d_{\mathrm{TV}}^{\mathrm{wc}}(K,t)

from ( 56 ) for each displayed kernel

K

Figure 3: Empirical controlled-spectrum phase diagram. Weighted disagreement is defined in ( 57 ). For each grid point, let $\widehat{\mathcal{O}}_{F}$ and $\widehat{\mathcal{O}}_{\gamma}$ denote the candidates selected from the same bottom- $P^{2}$ candidate pool by minimizing $F$ and $F_{\gamma}^{\infty}$ , respectively. The lower-left panel displays $1-\frac{F_{\gamma}^{\infty}(\widehat{\mathcal{O}}_{\gamma})}{F_{\gamma}^{\infty}(\widehat{\mathcal{O}}_{F})},$ the relative reduction in the discounted multi-horizon objective.

Figure 4: The most horizon-sensitive point

(\alpha,\varepsilon)=(0.16,0.006)

on the tested grid. The lower-left panel evaluates the lagged Frobenius profile

F(P^{t},\mathcal{O})

; the lower-right panel reports the distinct diagnostic

d_{\mathrm{TV}}^{\mathrm{wc}}(K,t)

from ( 56 ) for each displayed kernel

K

Baseline	Construction	Evaluation
Magnetization bins	Order the magnetization levels $M(x)$ and group whole levels into four nonempty contiguous bins. No magnetization level is split.	One deterministic partition.
Coordinate blocks	The four blocks are determined by the four possible values of $(x_{1},x_{2})\in\{-1,+1\}^{2}$ .	One deterministic partition.
Random nonempty assignments	Randomly permute the states, assign one state to each of the four labeled blocks, and assign every remaining state independently and uniformly to a block.	Mean and one empirical standard deviation over $80$ draws in Figure 5 . This is not uniform over unlabeled set partitions.

Table 2: Baselines used in the Ising experiment with

k=4

Figure 5: Exact Ising objective values for

d=8

and

k=4

. The shaded band is one empirical standard deviation across

80

random nonempty label assignments. Each blue curve evaluates the objective used to select that spectral-sweep output. Within each panel, lower values indicate better performance under the displayed criterion.

Figure 6: Conditional block allocation by magnetization for the exact Curie–Weiss chain at

(\beta,h)=(1.5,0)

. Each bar gives the stationary conditional distribution of block labels within one magnetization level.

Figure 7: Diagnostics for the exact Curie–Weiss chain at

(\beta,h)=(1.5,0)

. Left: the lagged Frobenius profile

F(P^{t},\mathcal{O})

. Right: exact worst-case total variation for repeated application of each displayed kernel.

Figure 8: Exact Bayesian variable-selection benchmark with $k=4$ . Left: block masses in decreasing order; unconstrained rounding places almost all posterior mass in one block, whereas the constrained outputs obey ( 58 ). Right: mean values of the four errors in ( 59 ) at $T=1000$ , divided by the corresponding mean error for the $0.1$ -lazy single-toggle Metropolis kernel $P$ . The dotted horizontal line at one represents $P$ , while the purple bars represent the separate add/delete/swap Metropolis benchmark. Values below one indicate improvement over $P$ . For each kernel, results are averaged over $160$ independent length- $1000$ trajectories, all initialized at the maximum-a-posteriori model $m_{\mathrm{MAP}}\in\operatorname*{argmax}_{m\in\mathcal{X}}\pi(m).$

Markov Models

Markov models describe systems that evolve probabilistically, with future behavior determined by the current state and transition rules.

See all 93 papers

Aug 9, 2026

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

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.

Zeqin Lin, Guangming Pan, Zhixiang Zhang +1

1Nanyang Technological University · University of Macau · 3Dalian University of Technology

Clustering Unsupervised Clustering Spectral Clustering Kernel Methods Spectral Methods

Ask PDF

Oct 23, 2026

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.

Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee +1

National University of Singapore, Singapore · Indian Statistical Institute, Kolkata, India

Clustering Spectral Clustering Dimensionality Reduction Kernel Methods

Ask PDF

Sep 24, 2026

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

Exact Euclidean

K

-means partitions

n

observations into

K

unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-

K

or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed

K

and dimension, under compact ball support and density bounds, retaining

q=O(\log n)

nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an

O(\log n/n)

fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.

Yordan P. Raykov, Max A. Little

School of Mathematical Sciences, University of Nottingham · School of Computer Science, University of Birmingham

Clustering Dynamic Programming Graph Sparsification

Ask PDF

Abstract

Markov Models

Explore similar work

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

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering