Sparse Representation in Redundant Systems

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Reconstruction of Signals: An Approach through Geometric Functional Analysis

Dr. Roman Vershynin

University of California, Davis

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₁ 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ⁿ 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₁ norm. An equivalent problem in combinatorial geometry is the existence of a polytope with fixed number of facets and maximal number of lower-dimensional 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]