Spectral State Compression of Markov Processes
This work addresses state compression in Markov processes for applications in modeling state-transition systems, representing an incremental advancement with specific theoretical and empirical contributions.
The paper tackles the problem of model reduction for Markov processes by developing spectral methods to estimate low-rank transition matrices and recover latent structures like state aggregation from empirical trajectories, achieving statistical upper bounds with nearly matching minimax lower bounds in numerical studies on synthetic data and NYC taxi trips.
Model reduction of Markov processes is a basic problem in modeling state-transition systems. Motivated by the state aggregation approach rooted in control theory, we study the statistical state compression of a discrete-state Markov chain from empirical trajectories. Through the lens of spectral decomposition, we study the rank and features of Markov processes, as well as properties like representability, aggregability, and lumpability. We develop spectral methods for estimating the transition matrix of a low-rank Markov model, estimating the leading subspace spanned by Markov features, and recovering latent structures like state aggregation and lumpable partition of the state space. We prove statistical upper bounds for the estimation errors and nearly matching minimax lower bounds. Numerical studies are performed on synthetic data and a dataset of New York City taxi trips.