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

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.

本文针对大型高斯图模型（Gaussian graphical models）的最大似然估计计算任务，提出了基于团（cliques）划分策略的迭代比例缩放法（iterative proportional scaling, IPS）本地化实现方案。我们首先将全体团的集合划分为若干互不重叠且非空的块，随后在每个块内对团边缘分布开展局部调整，此举可规避高阶矩阵运算，进而加速IPS流程。我们对斯温森-王算法（Swendsen–Wang Algorithm）进行改进，并结合模拟退火算法（simulated annealing algorithm）求解最优划分的近似解，以实现最低的计算复杂度。该团划分策略同样可加速现有的IIPS与IHT流程。本文通过数值实验验证了所提新型实现方案与策略所具备的竞争性性能。