×

zbMATH — the first resource for mathematics

An SVD approach to identifying metastable states of Markov chains. (English) Zbl 1171.15008
Summary: 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 a singular value decomposition (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.

MSC:
15A18 Eigenvalues, singular values, and eigenvectors
15B51 Stochastic matrices
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Software:
ARPACK; JDQR; JDQZ; TMG
PDF BibTeX XML Cite
Full Text: EMIS EuDML