Abstract
As networks proliferate in diverse fields of modern endeavor, so grows the need to control them on a large scale (e.g. in wireless or sensor networks), and interpret the high-dimensional data they generate (e.g. in social or biological networks). In this talk I present a broad-based approach to both challenges, based on a popular, but currently unrelated, formalism for multivariate statistical inference: Markov random fields (MRFs).
The popularity of MRFs derives from the empirical success of graph-based heuristics, like Belief Propagation (BP), in performing basic statistical tasks. A principled understanding of BP, however, is a long-standing open problem. The first part of my talk shows how BP can effectively solve core resource allocation problems in wireless and sensor networks. The structure of our problems enables us to develop the first formal connection between BP and linear programming; this also facilitates its application in decentralized settings.
In the second part of my talk I present a fundamental new uncertainty principle we develop, between the rank of a matrix and its sparsity pattern. This enables us to exactly resolve a composite matrix into its a-priori unknown sparse and low-rank components, via convex programming; splitting has implications for spectral data analysis, system identification etc. For networks, using this technique on Gaussian MRFs allows us to exactly ascertain hidden (i.e. unobservable) causes of network phenomena, with very few a-priori assumptions on the nature of these causes; this represents a global alternative to local heursitics like the EM algorithm.
Together, these examples show the ability of our approach to focus techniques from optimization, statistics and combinatorics, for the solution of network problems.
Biography Sujay Sanghavi has a B. Tech in EE from IIT Bombay, two MS degrees in ECE and Mathematics from UIUC. He obtained his PhD in ECE from UIUC in 2006; his thesis research focused on decentralized algorithms for communication networks. In UIUC, Sujay received the Perry Fellowship in 2001, and the Mavis Fellowship in 2005; he also started the annual CSL student conference. From 2006-08 he was a postdoc in LIDS at MIT, where he worked on large-scale statistical problems. Since Aug 2008, Sujay is an Assistant Professor in ECE at Purdue, where he works with students and colleages on both the above fields, and their many intersections