dc.contributor.author
Bittracher, Andreas
dc.contributor.author
Schütte, Christof
dc.date.accessioned
2021-02-26T10:38:13Z
dc.date.available
2021-02-26T10:38:13Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/29755
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-29497
dc.description.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 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 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.
en
dc.format.extent
19 Seiten
dc.rights.uri
https://creativecommons.org/licenses/by/4.0/
dc.subject
Markov chain
en
dc.subject
Sparse sampling
en
dc.subject
Metastability
en
dc.subject
Randomized algorithm
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
dc.title
A probabilistic algorithm for aggregating vastly undersampled large Markov chains
dc.type
Wissenschaftlicher Artikel
dcterms.bibliographicCitation.articlenumber
132799
dcterms.bibliographicCitation.doi
10.1016/j.physd.2020.132799
dcterms.bibliographicCitation.journaltitle
Physica D: Nonlinear Phenomena
dcterms.bibliographicCitation.volume
416
dcterms.bibliographicCitation.url
https://doi.org/10.1016/j.physd.2020.132799
refubium.affiliation
Mathematik und Informatik
refubium.affiliation.other
Institut für Mathematik

refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.issn
0167-2789
refubium.resourceType.provider
WoS-Alert