Fast interior-point inference in high-dimensional sparse, penalized state-space models

We present an algorithm for fast posterior inference in penalized high-dimensional state-space models, suitable in the case where a few measurements are taken in each time step. We assume that the state prior and observation likelihoods are log-concave and have a special structure that allows fast matrix-vector operations. We derive a second-order algorithm for computing the maximum a posteriori state path estimate, where the cost per iteration scales linearly both in time and memory. This is done by computing an approximate Newton direction using an efficient forward-backward scheme based on a sequence of low rank updates. We formalize the conditions under which our algorithm is applicable and prove its stability and convergence. We show that the state vector can be drawn from a large class of prior distributions without affecting the linear complexity of our algorithm. This class includes both Gaussian and nonsmooth sparse and group sparse priors for which we employ an interior point modification of our algorithm. We discuss applications in text modeling and neuroscience.