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

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.