Paper Info
Title
Efficient Transition Probability Computation for Continuous-Time Branching Processes via Compressed Sensing
Abstract
Branching processes are a class of continuous-time Markov chains (CTMCs) with ubiquitous applications. A general difficulty in statistical inference under partially observed CTMC models arises in computing transition probabilities when the discrete state space is large or uncountable. Classical methods such as matrix exponentiation are infeasible for large or count-ably infinite state spaces, and sampling-based alternatives are computationally intensive, requiring integration over all possible hidden events. Recent work has successfully applied generating function techniques to computing transition probabilities for linear multi-type branching processes. While these techniques often require significantly fewer computations than matrix exponentiation, they also become prohibitive in applications with large populations. We propose a compressed sensing framework that significantly accelerates the generating function method, decreasing computational cost up to a logarithmic factor by only assuming the probability mass of transitions is sparse. We demonstrate accurate and efficient transition probability computations in branching process models for blood cell formation and evolution of self-replicating transposable elements in bacterial genomes.
Year
Venue
Field
2015
UAI'15 Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence
Probability mass function,Generating function,Mathematical optimization,Computer science,Markov chain,Algorithm,Theoretical computer science,Statistical inference,Logarithm,Matrix exponential,State space,Branching process
DocType
Volume
ISSN
Conference
2015
1525-3384
ISBN
Citations 
PageRank 
978-0-9966431-0-8
1
0.35
References 
Authors
3
2
Name
Order
Citations
PageRank
jason xu111.36
Vladimir N Minin2287.58