Short Description

Recently, two papers treated state-space aggregation of Markov chains from an information-theoretic point-of-view: The work of Deng, Mehta and Meyn [1] minimizes a specific Kullback-Leibler divergence rate and connects the aggregation to graph-based methods, where the optimal bipartition turns out to coincide with the solution from spectral graph theory. Our work [2] minimizes a different Kullback-Leibler divergence rate and connects the aggregation with the phenomenon of lumpability and with the information bottleneck method. There are two projects/theses associated with this topic:

1. It would be interesting to find out if also our proposed method in some way has a connection with spectral graph theory, at least in case of the bipartition problem. This topic will be a bit heavy on the theoretical side.
2. It can be shown that the information bottleneck method is sub-optimal for the problem at hand. We have an idea to adapt the method to perform better; after implementation and testing of this method, a theoretical analysis shall investigate the possible improvements.

Your Requirements

This work will be both theoretical and involves MATLAB simulations. A good background in probabilities would be good.

Additional Information

The work should be completed by August 2014.

References

[1]: Deng, Mehta & Meyn: “Optimal Kullback-Leibler Aggregation via Spectral Theory of Markov Chains”, IEEE Trans. on Automatic Control, Link.
[2]: Geiger, Petrov, Kubin & Koeppl: “Optimal Kullback-Leibler Aggregation via Information Bottleneck”, submitted, arXiv.