Research Activities > Programs >
Sparse Representation in Redundant Systems
>
Martin Vetterli
|
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]
|
|
|