Repository: Freie Universität Berlin, Math Department

A probabilistic algorithm for aggregating vastly undersampled large Markov chains

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

[img] PDF

Official URL:


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