A Localized Implementation of the Iterative Proportional Scaling Procedure for Gaussian Graphical Models

Abstract

In this article, we propose localized implementations of the iterative proportional scaling (IPS) procedure by the strategy of partitioning cliques for computing maximum likelihood estimations in large Gaussian graphical models. We first divide the set of cliques into several nonoverlapping and nonempty blocks, and then adjust clique marginals in each block locally. Thus, high-order matrix operations can be avoided and the IPS procedure is accelerated. We modify the Swendsen–Wang Algorithm and apply the simulated annealing algorithm to find an approximation to the optimal partition which leads to the least complexity. This strategy of partitioning cliques can also speed up the existing IIPS and IHT procedures. Numerical experiments are presented to demonstrate the competitive performance of our new implementations and strategies.

Key Words:

• IPS procedure
• Junction tree
• Partitioning cliques
• Swendsen–Wang algorithm