Home Organization Outline Talks Logistics Participants Sponsors
ITA: Workshop '09 Keynote presentation
Keynote presentation

Precise Optimality in Compressed Sensing: Rigorous Theory and Ultra Fast Algorithms(Watch )

David Donoho, Stanford University

Joint work with Andrea Montanari, Arian Maleki and Iain Johnstone.

While Compressed Sensing has generated a great deal of published work, quite a lot of it is merely qualitative -- talking about loose performance bounds -- or else empirical -- describing computer experiments. In my talk I will describe some large-system optimality problems we have recently solved precisely, and fast algorithms which have a theoretical motivation, provably achieve the optimal performance level, and are dramatically faster in certain precise senses than the most popular iterative algorithms. Our approach unites minimax decision theory from statistics with ideas from statistical physics and belief propagation.  

Biography: David Donoho received his AB in Statistics from Princeton and his PhD in Statistics from Harvard. After a Postdoc at MSRI, he was a faculty member in Statistics at UC Berkeley before joining Stanford. He has held visiting positions at Universities of Paris, Leiden, Tel Aviv and Cambridge, UC San Diego, and at the National University of Singapore. He is a member of the US National Academy of Sciences and a Foreign Associate of the French Académie des Sciences. He has also worked in Oil Exploration (Western Geophysical), Quantitative Investing (Renaissance Technologies) and was co-founder of network management company BigFix (acquired by IBM).