Uncertainty principles, high-dimensional geometry, and sparse recovery


Terence Tao

University of California, Los Angeles


Thursday, October 13, 2005

Talk at 4:30 p.m. in Room 2-190

Tea from 4:00 - 4:30 p.m. in Room 2-290
Refreshments afterwards, in Room 2-290


Abstract:   Can one recover (or at least approximate) an n-dimensional vector of data from m linear measurements if m is much smaller than n? Without any further assumptions on the data, the answer is of course no. But a surprising discovery in recent years is that if the data is sparse (or compressible), and the measurements are suitably "generic", then approximate and even exact recovery can be possible, and in fact fairly straightforward. In particular, one can achieve good results by randomly sampling the Fourier coefficients. The reason that this works is because of a certain "uncertainty principle" between the data basis and the measurement basis, and also some key facts from high-dimensional geometry (most notably the fact that the unit ball in l^1 is extremely "pointy").


Home Web page:  Alexandru I. Suciu Comments to: 
Posted: September 22, 2005    URL: