Terence Tao

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