CAREER: Novel Message-Passing Algorithms for Distributed Computation in Graphical Models: Theory and Applications in Signal Processing

许多现实世界的科学和工程系统由大量相互作用的子系统组成。示例包括无线传感器网络，其中使用低功耗设备监视和检测扩展空间区域上的事件；以及数据以分布式方式存储的网络设置中的数据压缩（例如，分布在多台计算机服务器上的大型数据库）。图形模型为这种性质的系统的建模、分析和设计提供了一套强大的工具。这些模型通过结合概率模型（即，在系统操作中存在不确定性或随机性的模型）和捕获系统之间依赖关系的图来获得它们的能力。这项研究包括开发新的算法，将这些图形模型应用于传感器网络和数据压缩等大规模系统。利用图形模型的全部功能需要有效的方法来解决一系列核心挑战。在这项研究中，研究者描述了现有算法的局限性，并进一步开发了替代的、最终更强大的消息传递算法来解决这些核心计算问题。以下四个项目涉及这一高级别目标的相关方面：(a)分析基于线性规划的可证明有效的算法；(b)新颖的消息传递算法，用于执行近乎最佳的有损数据压缩；(c)对消息传递中的稳定性和鲁棒性问题进行基础研究；(d)从数据中自动学习模型的新方法。这些研究重点与教育举措密切相关，包括招收本科生从事研究；广泛分发可公开获得的调查报告、教程幻灯片和图形模型软件；以及通过加州大学伯克利分校的通信、计算和统计指定重点，促进工程与统计学之间的互动。

Many real-world scientific and engineering systems consist of a large number of interacting subsystems. Examples include wireless sensor networks, in which low-power devices are used to monitor and detect events over an extended spatial region; and data compression in network settings where data is stored in a distributed manner (e.g., large databases distributed over multiple computer servers). Graphical models provide a powerful set of tools for modeling, analyzing, and designing systems of this nature. These models derive their power by combining a probabilistic model (i.e., one in which there is uncertainty or stochasticity in the system operation) with graphs that capture the dependencies among the systems. This research involves developing new algorithms for applying these graphical models to large-scale systems like sensor networks and data compression.Leveraging the full power of graphical models requires efficient methods for solving a core set of challenges. In this research, the investigator characterizes the limitations of existing algorithms, and moreover develops alternative and ultimately more powerful message-passing algorithms for solving these core computational problems. The following four projects address related aspects of this high-level goal: (a) analysis of provably effective algorithms based on linear programming; (b) novel message-passing algorithms for performing near-optimal lossy data compression; (c) fundamental research on issues of stability and robustness in message-passing; and (d) new methods for automated learning of models from data. These research thrusts are closely coupled with educational initiatives, including recruitment of undergraduates into research; broad dissemination of publicly-available survey papers, tutorial slides and software for graphical models; and the fostering of interaction between Engineering and Statistics via the Designated Emphasis in Communication, Computation and Statistics at UC Berkeley.