학술논문

Optimal Kullback-Leibler Aggregation via Spectral Theory of Markov Chains
Document Type
Periodical
Source
IEEE Transactions on Automatic Control IEEE Trans. Automat. Contr. Automatic Control, IEEE Transactions on. 56(12):2793-2808 Dec, 2011
Subject
Signal Processing and Analysis
Markov processes
Reduced order systems
Eigenvalues and eigenfunctions
Probability distribution
Optimization
Mutual information
Kullback–Leibler (K–L) divergence rate
Markov chain
model reduction
spectral theory
Language
ISSN
0018-9286
1558-2523
2334-3303
Abstract
This paper is concerned with model reduction for complex Markov chain models. The Kullback–Leibler divergence rate is employed as a metric to measure the difference between the Markov model and its approximation. For a certain relaxation of the bi-partition model reduction problem, the solution is shown to be characterized by an associated eigenvalue problem. The form of the eigenvalue problem is closely related to the Markov spectral theory for model reduction. This result is the basis of a heuristic proposed for the $m$-ary partition problem, resulting in a practical recursive algorithm. The results are illustrated with examples.