A special instance of this theory yields a novel sampling theorem:Suppose that a finite N dimensional signal f has only B nonzeroFourier coefficients at unknown frequencies. Then we can recover fperfectly from a small number of samples (on the order of B log N)in the time domain.
The recovery procedure is nonlinear, and consists of solving atractable convex program. Despite its nonlinearity, the recoveryprocedure is exceptionally stable against measurement error.
The theory (and the recovery algorithm) can be extended to signalsand images that are sparse in a known representation, and "sampled"using a specified set of measurement signals. We will show how ourability to recover a sparse signal depends on the representation andthe measurements system obeying an uncertainty principle.We will close by showing how these ideas can be applied to problemsin tomographic imaging and data compression.