An SVD approach to identifying metastable states of Markov chains. (English) Zbl 1171.15008

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

ETNA, Electron. Trans. Numer. Anal. 29(2007-2008), 46-69 (2008).

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

Keywords:

Markov chain; stochastic matrix; conformation dynamics; metastable; eigenvalue cluster; singular value decomposition; block diagonal dominance; eigenvectors; algorithm; numerical examples

Software:

ARPACK; JDQR; JDQZ; TMG