Spectral State Compression of Markov Processes

Anru Zhang, Mengdi Wang

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Article number8918022
Pages (from-to)3202-3231
Number of pages30
JournalIEEE Transactions on Information Theory
Volume66
Issue number5
DOIs
StatePublished - May 2020

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Computational complexity
  • maximum likelihood estimation
  • minimax techniques
  • signal denoising
  • tensor SVD

Fingerprint Dive into the research topics of 'Spectral State Compression of Markov Processes'. Together they form a unique fingerprint.

  • Cite this