Optimal kullback-leibler aggregation via spectral theory of markov chains

Kun Deng, Prashant G. Mehta, Sean P. Meyn

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number5746509
Pages (from-to)2793-2808
Number of pages16
JournalIEEE Transactions on Automatic Control
Issue number12
StatePublished - Dec 2011


  • Kullback-Leibler (K-L) divergence rate
  • Markov chain
  • Model reduction
  • Spectral theory

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal kullback-leibler aggregation via spectral theory of markov chains'. Together they form a unique fingerprint.

Cite this