STATISTICS COLLOQUIUM
Thursday, January 19th, 2012 at 4.10pm, MSB 1147 (Colloquium Room)
Refreshments: 3.30pm, MSB 4110 (Statistics Lounge)
Speaker: Andrea Montanari (Stanford University)
Title: Sharp Thresholds in Statistical Estimation
Abstract: Sharp thresholds are ubiquitous high-dimensional combinatorial structures. The oldest example is probably the sudden emergence of the giant component in random graphs, first discovered by Erdos and Renyi.
More recently, threshold phenomena have started to play an important role in
some statistical learning and statistical signal processing problems, in part
because of the interest in 'compressed sensing'.
The basic setting is one in which a large number of noisy observations of a
high-dimensional object are made. As the ratio of the number of observations to
the number of `hidden dimensions' crosses a threshold, our ability to
reconstruct the object increases dramatically.
I will discuss several examples of this phenomenon, and some algorithmic and
mathematical ideas that allow to characterize threshold phenomena.
[based on joint
work with Mohsen Bayati, David Donoho, Iain Johnstone, Arian Maleki]
