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

arXiv:2608.21466v1 Announce Type: cross 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-Pi|_{F,pi}^2, we derive exact trace and normalized-cut representations and show that F equals the Pearson hi^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.

Source: arXiv cs.LG | 2026-08-25