A Note on Projection-Based Recovery of Clusters in Markov Chains

Abstract

Let $T_0$ be the transition matrix of a purely clustered Markov chain, i.e. a direct sum of $k\ge 2$ irreducible stochastic matrices. Given a perturbation $T(x)=T_0+xE$ of $T_0$ such that $T(x)$ is also stochastic, how small must $x$ be in order for us to recover the indices of the direct summands of $T_0$? We give a simple algorithm based on the orthogonal projection matrix onto the left or right singular subspace corresponding to the $k$ smallest singular values of $I-T(x)$ which allows for exact recovery all clusters when $x=O\left(\frac{{\sigma }_{n-k}}{||E|{|}_2\sqrt{n_1}}\right)$ and approximate recovery of a single cluster when $x=O\left(\frac{{\sigma }_{n-k}}{||E|{|}_2}\right)$, where $n_1$ is the size of the largest cluster and ${\sigma }_{n-k}$ the $(k+1)$st smallest singular value of $T_0$.

References in corpus (1)

• Clusters in Markov Chains via Singular Vectors of Laplacian Matrices