Bittracher, Andreas and Schütte, Christof
(2021)
*A probabilistic algorithm for aggregating vastly undersampled large Markov chains.*
Physica D, 416
.
pp. 1-19.

PDF
2MB |

Official URL: http://doi.org/10.1016/j.physd.2020.132799

## Abstract

Model reduction of large Markov chains is an essential step in a wide array of techniques for understanding complex systems and for efficiently learning structures from high-dimensional data. We present a novel aggregation algorithm for compressing such chains that exploits a specific lowrank structure in the transition matrix which, e.g., is present in metastable systems, among others. It enables the recovery of the aggregates from a vastly undersampled transition matrix which in practical applications may gain a speedup of several orders of magnitude over methods that require the full transition matrix. Moreover, we show that the new technique is robust under perturbation of the transition matrix. The practical applicability of the new method is demonstrated by identifying a reduced model for the large-scale traffic flow patterns from real-world taxi trip data.

Item Type: | Article |
---|---|

Subjects: | Mathematical and Computer Sciences > Mathematics > Applied Mathematics |

Divisions: | Department of Mathematics and Computer Science > Institute of Mathematics |

ID Code: | 2614 |

Deposited By: | Monika Drueck |

Deposited On: | 24 Sep 2021 11:27 |

Last Modified: | 15 Feb 2022 16:01 |

Repository Staff Only: item control page