论文标题
马尔可夫链过渡矩阵的光谱聚类与复杂特征值
Spectral clustering of Markov chain transition matrices with complex eigenvalues
论文作者
论文摘要
强大的Perron聚类分析（PCCA+）已成为一种流行的光谱群集算法，用于具有过渡状态的几乎可分解的马尔可夫链的粗粒过渡矩阵。该算法最初是为可逆的马尔可夫链开发的，仅用于具有真实特征值的过渡矩阵。因此，在本文中，我们将PCCA+的理论框架扩展到具有复杂特征分类的马尔可夫链。我们表明，通过通过其真实和虚构的组件替换复杂的共轭特征向量，可以获得相同子空间的实际表示，这适用于群集分析。我们表明，我们的方法与广义PCCA+（genPCCA）相同，该结果通过概念上更困难的实际Schur分解代替了复杂的特征分解。我们将该方法应用于非可逆的马尔可夫链（包括圆形链）上，并与GenPCCA相比证明了其效率。实验以MATLAB编程语言进行，并提供代码。
The Robust Perron Cluster Analysis (PCCA+) has become a popular spectral clustering algorithm for coarse-graining transition matrices of nearly decomposable Markov chains with transition states. Originally developed for reversible Markov chains, the algorithm only worked for transition matrices with real eigenvalues. In this paper, we therefore extend the theoretical framework of PCCA+ to Markov chains with a complex eigen-decomposition. We show that by replacing a complex conjugate pair of eigenvectors by their real and imaginary components, a real representation of the same subspace is obtained, which is suitable for the cluster analysis. We show that our approach leads to the same results as the generalized PCCA+ (GenPCCA), which replaces the complex eigen-decomposition by a conceptually more difficult real Schur decomposition. We apply the method on non-reversible Markov chains, including circular chains,and demonstrate its efficiency compared to GenPCCA. The experiments are performed in the Matlab programming language and codes are provided.
