Statistical mechanics aims at understanding the collective behavior of large systems made of simple interacting components. The space of possible configurations of such systems is high-dimensional and combinatorial and, as a consequence, it is extremely challenging to understand their behavior. Despite this, statistical mechanics techniques often provide strong quantitative predictions.

A number of modern information technologies share the same complex features, in that they are based on large decentralized networks of simple units. Examples include sensor networks, ad hoc wireless networks, social communities, modern coding systems. Over the last 20 years, spectacular progress has been made in probability theory towards a rigorization of the methods of statistical mechanics. These achievements can have far-reaching consequences in the analysis and design of computer and communication systems.

The present proposal has two goals: (I) Clarify and rigorize the statistical physics techniques and their applications to engineering and computer science. (II) Use this approach in three new application domains: learning graphical models; detection and measurement through sparse graphs; statistical inference for high-dimensional combinatorial distributions.

Project Report

The challenge of extracting information from noisy data is central to many engineering and scientific problems. For instance, in imaging an object is probed by some physical device (radar, nuclear magnetic resonance, electron microscope) and its structure must be inferred from such measurements. At a completely different scale, web commerce companies collect data about the behavior of their users (ad clicks, purchasing behavior, andso on). In order to provide a better service, they use this information to extract a profile (an `image') of their user. This profile is then used to provide recommendations. Despite these problems might appear extremely different, at a fundamental mathematical level they are in fact closely related. Many similar examples are indeed characterized by the large amount of available data, and the fact that the underlyingobject to be reconstructed is very complex (for instance an image or a user profile). Also, these reconstruction problemsare often characterized by a 'phase transition,' an abrupt change in their behavior as the amount of data increases.Namely, when the amount of data is below a certain threshold, the problem is virtually unsolvable. When this threshold is passed, the problem becomes suddenly easy to solve. This has deep analogies with physical phase transitions,whereby matter changes state (e.g. from solid to liquid) as its temperature is changed. This project focused on the study of such inference problems, tackling in particular two challenges: (1) Characterize the phase transition phenomenon, e.g. the minimum amount of data necessary to reconstruct a certain object. (2) Develop efficient reconstruction algorithms that attain the optimum performances. Namely, they can reconstruct the unknown image as close as possible to the underlying phase transition.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
0743978
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2008-08-01
Budget End
2014-07-31
Support Year
Fiscal Year
2007
Total Cost
$400,000
Indirect Cost
Name
Stanford University
Department
Type
DUNS #
City
Palo Alto
State
CA
Country
United States
Zip Code
94304