Abstract: How to reconstruct a signal that belongs to a small class from few linear measurements? Using methods of geometric functional analysis, we prove that for most sets of Gaussian measurements, all signals of small support can be exactly reconstructed
by the L_{1} norm minimization. This is an improvement of earlier results of Donoho and of Candes
and Tao. This has implications in coding theory. We prove that most transform codes (linear orthogonal
transformations Q from R^{n} into R^{m}) form efficient and robust robust error correcting codes. The decoder
is the metric projection onto the range of Q in the L_{1} norm. An equivalent problem in combinatorial geometry
is the existence of a polytope with fixed number of facets and maximal number of lowerdimensional facets. We
prove that most sections of the cube form such polytopes. Our work thus belongs to a common ground of coding
theory, signal processing, combinatorial geometry and geometric functional analysis. This is a joint work with
Mark Rudelson.
[LECTURE SLIDES]
