Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization
This work addresses the challenge of dimensionality reduction in multivariate Markov chains for researchers in information theory and machine learning, but it is incremental as it builds on existing submodular optimization methods.
The paper tackles the problem of projecting or partitioning the state space of multivariate Markov chains to minimize information loss under cardinality constraints, using information-theoretic criteria like entropy rate and factorizability distance, and develops efficient greedy algorithms with theoretical guarantees, demonstrating them on Bernoulli–Laplace and Curie–Weiss models with publicly available code.
We study the problem of optimally projecting the transition matrix of a finite ergodic multivariate Markov chain onto a lower-dimensional state space, as well as the problem of finding an optimal partition of coordinates such that the factorized Markov chain gives minimal information loss compared to the original multivariate chain. Specifically, we seek to construct a Markov chain that optimizes various information-theoretic criteria under cardinality constraints. These criteria include entropy rate, information-theoretic distance to factorizability, independence, and stationarity. We formulate these tasks as best subset or partition selection problems over multivariate Markov chains and leverage the (k-)submodular (or (k-)supermodular) structures of the objective functions to develop efficient greedy-based algorithms with theoretical guarantees. Along the way, we introduce a generalized version of the distorted greedy algorithm, which may be of independent interest. Finally, we illustrate the theory and algorithms through extensive numerical experiments with publicly available code on multivariate Markov chains associated with the Bernoulli--Laplace and Curie--Weiss models.