Geodesic
An SVD approach to identifying metastable states of Markov chains
Electronic transactions on numerical analysis, Tome 29 (2008)
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.
Classification : 15A18, 15A51, 60J10, 60J20, 65F15
Keywords: Markov chain, stochastic matrix, conformation dynamics, metastable, eigenvalue cluster, singular value decomposition, block diagonal dominance 
@article{ETNA_2008__29__a10,
     author = {Fritzsche,  David and Mehrmann,  Volker and Szyld,  Daniel B. and Virnik,  Elena},
     title = {An {SVD} approach to identifying metastable states of {Markov} chains},
     journal = {Electronic transactions on numerical analysis},
     year = {2008},
     volume = {29},
     zbl = {1171.15008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2008__29__a10/}
}
TY  - JOUR
AU  - Fritzsche,  David
AU  - Mehrmann,  Volker
AU  - Szyld,  Daniel B.
AU  - Virnik,  Elena
TI  - An SVD approach to identifying metastable states of Markov chains
JO  - Electronic transactions on numerical analysis
PY  - 2008
VL  - 29
UR  - http://geodesic.mathdoc.fr/item/ETNA_2008__29__a10/
LA  - en
ID  - ETNA_2008__29__a10
ER  - 
%0 Journal Article
%A Fritzsche,  David
%A Mehrmann,  Volker
%A Szyld,  Daniel B.
%A Virnik,  Elena
%T An SVD approach to identifying metastable states of Markov chains
%J Electronic transactions on numerical analysis
%D 2008
%V 29
%U http://geodesic.mathdoc.fr/item/ETNA_2008__29__a10/
%G en
%F ETNA_2008__29__a10
Fritzsche,  David; Mehrmann,  Volker; Szyld,  Daniel B.; Virnik,  Elena. An SVD approach to identifying metastable states of Markov chains. Electronic transactions on numerical analysis, Tome 29 (2008). http://geodesic.mathdoc.fr/item/ETNA_2008__29__a10/