Optimal Kullback–Leibler approximation of Markov chains via nuclear norm regularisation

Abstract

This paper is concerned with model reduction for Markov chain models. The goal is to obtain a low-rank approximation to the original Markov chain. The Kullback–Leibler divergence rate is used to measure the similarity between two Markov chains; the nuclear norm is used to approximate the rank function. A nuclear-norm regularised optimisation problem is formulated to approximately find the optimal low-rank approximation. The proposed regularised problem is analysed and performance bounds are obtained through the convex analysis. An iterative fixed point algorithm is developed based on the proximal splitting technique to compute the optimal solutions. The effectiveness of this approach is illustrated via numerical examples.

Keywords:

• Markov chain
• low-rank approximation
• Kullback–Leibler divergence rate
• nuclear norm regularisation
• proximal splitting algorithm

Acknowledgements

The authors gratefully acknowledge Prof. Sean P. Meyn in initially proposing the idea of low-rank approximation of Markov chains, and thank Prof. Prashant G. Mehta for helpful discussions. The authors also want to thank Dr. Yu Sun and Prof. Wei Dai for fruitful comments and suggestions.

Additional information

Notes on contributors

Kun Deng

Kun Deng received the BE degree in Automatic Control in 2005 and the MS degree in Mechanical Engineering in 2007, both from Tsinghua University, Beijing, China. He received the MS degree in Mathematics in 2010 and the PhD degree in Mechanical Engineering in 2012, both from University of Illinois at Urbana-Champaign, Urbana, IL, United States. His current research interests include stochastic processes, control and optimisation, and machine learning.

Dayu Huang

Dayu Huang received the BE degree in Information Electronics and Engineering in 2006 from Tsinghua University, Beijing, China. He received the MS degree in Electrical and Computer Engineering in 2009, the MS degree in Mathematics in 2010, and the PhD degree in Electrical and Computer Engineering in 2012, all from University of Illinois at Urbana-Champaign, Urbana, IL, United States. His current research interests include detection and estimation, information theory, and stochastic processes