[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Sparse Representation in Redundant Systems > Martin Vetterli


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 L1 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 Rn into Rm) form efficient and robust robust error correcting codes. The decoder is the metric projection onto the range of Q in the L1 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]