Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees

Understand

In this paper, we study the problem of inferring time-varying Markov random fields (MRF), where the underlying graphical model is both sparse and changes sparsely over time.

• Most of the existing methods for the inference of time-varying MRFs rely on the regularized maximum likelihood estimation (MLE), that typically suffer from weak statistical guarantees and high computational time.
• Instead, we introduce a new class of constrained optimization problems for the inference of sparsely-changing MRFs.
• The proposed optimization problem is formulated based on the exact $\ell_0$ regularization, and can be solved in near-linear time and memory.