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

arXiv: https://arxiv.org/abs/2608.21466 · HTML: https://mlsanity.com/paper/2608.21466/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 23 references that are in the map.
- First posted on arXiv 21 Aug 2026.

## Builds on (most cited first, 4 of 4)

- [Optimal interval clustering: Application to Bregman clustering and statistical mixture learning](https://mlsanity.com/paper/1403.2485/) (2014)
- [Parallel Markov Chain Monte Carlo via Spectral Clustering](https://mlsanity.com/paper/1605.09454/) (2016)
- [Optimising two-block averaging kernels to speed up Markov chains](https://mlsanity.com/paper/2603.10318/) (2026)
- [On additive averaging kernels for finite Markov chains](https://mlsanity.com/paper/2604.12334/) (2026)

## Abstract (arXiv)

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 Gmathcal 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 P2, or the algebraically smallest eigenfunctions of P for additive mixtures, using weighted k-means. For F(mathcal O)=|Gmathcal OP-Pi|F,π2, we derive exact trace and normalized-cut representations and show that F equals the Pearson chi2-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 ≥ 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.