Collaborative Effort: 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.