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

Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery
Aug 9, 2026Zeqin Lin, Guangming Pan, Zhixiang Zhang +1Clustering Unsupervised Clustering
1Nanyang Technological University · University of Macau · 3Dalian University of Technology
Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering
Oct 23, 2026Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee +1Clustering Spectral Clustering
National University of Singapore, Singapore · Indian Statistical Institute, Kolkata, India
Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering
Sep 24, 2026Yordan P. Raykov, Max A. LittleClustering Dynamic Programming
School of Mathematical Sciences, University of Nottingham · School of Computer Science, University of Birmingham

Aug 9, 2026J/K move · Enter open · S save

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

Zeqin Lin, Guangming Pan, Zhixiang Zhang, Yinbing Zhou

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

Clustering Unsupervised Clustering Spectral Clustering Kernel Methods Spectral Methods

Open paper AskPDF arXiv

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.

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