Volume 29, pp. 46-69, 2007-2008.

An SVD approach to identifying metastable states of Markov chains

David Fritzsche, Volker Mehrmann, Daniel B. Szyld, and Elena Virnik

Abstract

Being one of the key tools in conformation dynamics, the identification of metastable states of Markov chains has been subject to extensive research in recent years, especially when the Markov chains represent energy states of biomolecules. Some previous work on this topic involved the computation of the eigenvalue cluster close to one, as well as the corresponding eigenvectors and the stationary probability distribution of the associated stochastic matrix. More recently, since the eigenvalue cluster algorithm may be nonrobust, an optimization approach was developed. As a possible less costly alternative, we present an SVD approach of identifying metastable states of a stochastic matrix, where we only need the singular vector associated with the second largest singular value. We also introduce a concept of block diagonal dominance on which our algorithm is based. We outline some theoretical background and discuss the advantages of this strategy. Some simulated and real numerical examples illustrate the effectiveness of the proposed algorithm.

Full Text (PDF) [2 MB], BibTeX

Key words

Markov chain, stochastic matrix, conformation dynamics, metastable, eigenvalue cluster, singular value decomposition, block diagonal dominance

AMS subject classifications

15A18, 15A51, 60J10, 60J20, 65F15

ETNA articles which cite this article

Vol. 37 (2010), pp. 296-306 Martin Nilsson Jacobi: A robust spectral method for finding lumpings and meta stable states of non-reversible Markov chains

Vol. 38 (2011), pp. 17-33 Ryan M. Tifenbach: On an SVD-based algorithm for identifying meta-stable states of Markov chains

Vol. 40 (2013), pp. 120-147 Ryan M. Tifenbach: A combinatorial approach to nearly uncoupled Markov chains I: Reversible Markov chains

< Back