Spectral State Compression of Markov Processes
arXiv:1802.02920
Abstract
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.
arXiv commentto appear in IEEE Transactions on Information Theory
References in corpus (11)
- A Simpler Approach to Matrix Completion
- Matrix estimation by Universal Singular Value Thresholding
- Spectral methods for network community detection and graph partitioning
- Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
- Minimax risk of matrix denoising by singular value thresholding
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Learning low-dimensional state embeddings and metastable clusters from time series data
- Estimation of Markov Chain via Rank-Constrained Likelihood
- Recovering Structured Probability Matrices