This is an announcement for the paper "Geometric approach to error correcting codes and reconstruction of signals" by Mark Rudelson and Roman Vershynin.
Abstract: We develop an approach through geometric functional analysis to error correcting codes and to reconstruction of signals from few linear measurements. An error correcting code encodes an n-letter word x into an m-letter word y in such a way that x can be decoded correctly when any r letters of y are corrupted. We prove that most linear orthogonal transformations Q from R^n into R^m form efficient and robust robust error correcting codes over reals. The decoder (which corrects the corrupted components of y) is the metric projection onto the range of Q in the L_1 norm. An equivalent problem arises in signal processing: how to reconstruct a signal that belongs to a small class from few linear measurements? 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 a substantial improvement of recent results of Donoho and of Candes and Tao. 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.
Archive classification: Functional Analysis; Combinatorics
Mathematics Subject Classification: 46B07; 94B75, 68P30, 52B05
Remarks: 17 pages, 3 figures
The source file(s), ecc.tex: 50560 bytes, ecc1.eps: 4526 bytes, ecc2.eps: 17097 bytes, ecc3.eps: 4645 bytes, is(are) stored in gzipped form as 0502299.tar.gz with size 23kb. The corresponding postcript file has gzipped size 84kb.
Submitted from: vershynin@math.ucdavis.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/math.FA/0502299
or
http://arXiv.org/abs/math.FA/0502299
or by email in unzipped form by transmitting an empty message with subject line
uget 0502299
or in gzipped form by using subject line
get 0502299
to: math@arXiv.org.