[ 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.