A probabilistic algorithm for aggregating vastly undersampled large Markov chains

Please always quote using this URN: urn:nbn:de:0297-zib-78688
  • 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 low-rank 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 mag- nitude 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Bittracher, Christof Schütte
Document Type:ZIB-Report
Date of first Publication:2020/06/26
Series (Serial Number):ZIB-Report (20-21)
ISSN:1438-0064
Published in:Appeard in: Physica D
URL:https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7587