An approximation theory for Markov chain compression
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915470616035328 |
|---|---|
| author | Fornace, Mark Lindsey, Michael |
| author_facet | Fornace, Mark Lindsey, Michael |
| contents | We develop a framework for the compression of reversible Markov chains with rigorous error control. Given a subset of selected states, we construct reduced dynamics that can be lifted to an approximation of the full dynamics, and we prove simple spectral and nuclear norm bounds on the recovery error in terms of a suitably interpreted Nyström approximation error. We introduce two compression schemes: a projective compression based on committor functions and a structure-preserving compression defined in terms of an induced Markov chain over the selected states. The Nyström error appearing in our bounds can be controlled using recent results on column subset selection by nuclear maximization. Numerical experiments validate our theory and demonstrate the scalability of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22918 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An approximation theory for Markov chain compression Fornace, Mark Lindsey, Michael Numerical Analysis Probability We develop a framework for the compression of reversible Markov chains with rigorous error control. Given a subset of selected states, we construct reduced dynamics that can be lifted to an approximation of the full dynamics, and we prove simple spectral and nuclear norm bounds on the recovery error in terms of a suitably interpreted Nyström approximation error. We introduce two compression schemes: a projective compression based on committor functions and a structure-preserving compression defined in terms of an induced Markov chain over the selected states. The Nyström error appearing in our bounds can be controlled using recent results on column subset selection by nuclear maximization. Numerical experiments validate our theory and demonstrate the scalability of our approach. |
| title | An approximation theory for Markov chain compression |
| topic | Numerical Analysis Probability |
| url | https://arxiv.org/abs/2506.22918 |