# Spectral State Compression of Markov Processes

arXiv: https://arxiv.org/abs/1802.02920 · HTML: https://mlsanity.com/paper/1802.02920/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2018.

## Built on by (most cited first, 18 of 18)

- [Spectral Decomposition Representation for Reinforcement Learning](https://mlsanity.com/paper/2208.09515/) (2022)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2209.06620/) (2022)
- [A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning](https://mlsanity.com/paper/2111.11485/) (2021)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Certainty Equivalent Quadratic Control for Markov Jump Systems](https://mlsanity.com/paper/2105.12358/) (2021)
- [The Normalized Cross Density Functional: A Framework to Quantify Statistical Dependence for Random Processes](https://mlsanity.com/paper/2212.04631/) (2022)
- [Improved Algorithm and Bounds for Successive Projection](https://mlsanity.com/paper/2403.11013/) (2024)
- [Low-Rank Tensors for Multi-Dimensional Markov Models](https://mlsanity.com/paper/2411.02098/) (2024)
- [Tucker Diffusion Model for High-dimensional Tensor Generation](https://mlsanity.com/paper/2604.00481/) (2026)
- [Detection and Evaluation of Clusters within Sequential Data](https://mlsanity.com/paper/2210.01679/) (2022)
- [Accuracy vs Memory Advantage in the Quantum Simulation of Stochastic Processes](https://mlsanity.com/paper/2312.13473/) (2023)
- [Estimating the number of clusters of a Block Markov Chain](https://mlsanity.com/paper/2407.18287/) (2024)
- [Synwalk -- Community Detection via Random Walk Modelling](https://mlsanity.com/paper/2101.08623/) (2021)
- [Mode Reduction for Markov Jump Systems](https://mlsanity.com/paper/2205.02697/) (2022)
- [Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes](https://mlsanity.com/paper/2510.09965/) (2025)
- [Transfer Denoising of Low-Rank Plus Sparse Matrices under Ambient and Rank Growth](https://mlsanity.com/paper/2601.21873/) (2026)

## Abstract (arXiv)

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.