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

In this paper, 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 non-overlapping and non-empty 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.