Fast Computation of Branching Process Transition Probabilities via ADMM

Branching processes are a class of continuous-time Markov chains (CTMCs) prevalent for stochastic population models in ecology, biology, epidemiology, and many other fields. There transient or finite-time behavior is fully characterized by their transition probabilities. However, computing them requires marginalizing over all paths between endpoint-conditioned values, which often poses a computational bottleneck. Leveraging recent results that connect generating function methods to a compressed sensing framework, we recast this task from the lens of sparse optimization. We propose a new solution method using variable splitting; in particular, we derive closed form updates in a highly efficient ADMM algorithm. Remarkably, no matrix products---let alone inversions---are required at any step. Not only does this reduce computational cost by orders of magnitude over existing methods, but the algorithm is easily parallelizable and fairly insensitive to tuning parameters. A comparison to prior work is carried out in two applications to models of blood cell production and transposon evolution, showing that the proposed method is orders of magnitudes more scalable than existing work.