Spectral Clustering for Non-reversible Markov Chains

Please always quote using this URN: urn:nbn:de:0297-zib-70218
  • Spectral clustering methods are based on solving eigenvalue problems for the identification of clusters, e.g. the identification of metastable subsets of a Markov chain. Usually, real-valued eigenvectors are mandatory for this type of algorithms. The Perron Cluster Analysis (PCCA+) is a well-known spectral clustering method of Markov chains. It is applicable for reversible Markov chains, because reversibility implies a real-valued spectrum. We also extend this spectral clustering method to non-reversible Markov chains and give some illustrative examples. The main idea is to replace the eigenvalue problem by a real-valued Schur decomposition. By this extension non-reversible Markov chains can be analyzed. Furthermore, the chains do not need to have a positive stationary distribution. In addition to metastabilities, dominant cycles and sinks can also be identified. This novel method is called GenPCCA (i.e. Generalized PCCA), since it includes the case of non reversible processes. We also apply the method to real world eye tracking data.

Download full text files

Export metadata

Metadaten
Author:Konstantin Fackeldey, Alexander Sikorski, Marcus Weber
Document Type:ZIB-Report
Tag:Markov chain; Schur decomposition; non-reversible; spectral clustering
MSC-Classification:15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY / 15Axx Basic linear algebra / 15A21 Canonical forms, reductions, classification
62-XX STATISTICS / 62Hxx Multivariate analysis [See also 60Exx] / 62H30 Classification and discrimination; cluster analysis [See also 68T10]
CCS-Classification:G. Mathematics of Computing / G.1 NUMERICAL ANALYSIS / G.1.3 Numerical Linear Algebra
PACS-Classification:00.00.00 GENERAL / 05.00.00 Statistical physics, thermodynamics, and nonlinear dynamical systems (see also 02.50.-r Probability theory, stochastic processes, and statistics)
Date of first Publication:2018/08/24
Series (Serial Number):ZIB-Report (18-48)
ISSN:1438-0064
Published in:Comp. Appl. Math., pp 1-16, https://doi.org/10.1007/s40314-018-0697-0