Collaborative Research: Message-Passing Algorithms - from Practice to Theory and back to Practice

这笔赠款支持的研究的目标是彻底和有效地了解消息传递算法，这些算法构成了一大类非常有效的估计和检测技术。事实上，虽然消息传递(迭代)处理在实践中非常成功，但理解它的局限性及其非最佳行为的来源一直难以捉摸。尽管消息传递算法具有巨大的影响，特别是在通信场景中，但实际系统目前几乎完全依赖于基于模拟的评估。在这种情况下，了解消息传递的行为和几何结构不仅可以减少模拟的必要性，还可以为系统优化提供强大的工具。该建议借鉴了最近令人兴奋的发展，将消息传递算法与成熟的凸优化理论相联系。事实证明，消息传递算法与手头推理任务的线性规划公式密切相关。事实上，信任传播算法可以被解释为一种有效的基于对偶的方法来逼近线性规划的解。一旦建立了这样的联系，调查人员将努力从一个全新的和富有成效的角度来理解消息传递算法。此外，研究人员已经证明，与凸优化的联系植根于消息传递算法的基本属性，即它们仅在给定的图形模型中局部操作。因此，从这里研究的方法得到的结果将适用于任何合理的局部操作算法。

The research supported under this grant targets the thorough and effective understanding of message-passing algorithms which constitute a large and very potent class of estimation and detection techniques. Indeed, while message-passing (iterative) processing is very successful in practice, understanding its limitations and its sources of non-optimal behavior has been elusive. Despite the enormous impact that message-passing algorithms have, in particular in a communication scenario, practical systems currently rely almost exclusively on a simulation-based evaluation. In this situation, understanding the behavior and geometry of message-passing will not only reduce the necessity of simulations but provide powerful tools for system optimization.This proposal draws on recent exciting developments that connect message-passing algorithms to the well established theory of convex optimization. As it turns out, message-passing algorithms are intimately related to a linear programming formulation of the inference task at hand. In fact, belief propagation algorithms may be interpreted as an efficient duality-based method to closely approximate the solution to a linear program. Once such connections are established the investigators will strive to understand message-passing algorithms from an entirely new and fruitful point of view. Also, the investigators have already shown that the connection to convex optimization is rooted in the basic property of message-passing algorithms, namely that they operate only locally in a given graphical model. Thus the findings resulting from the approach investigated here will apply to any reasonable locally-operating algorithm.