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.
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.
