Abstract of a paper by Mark Rudelson and Roman Vershynin
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.
participants (1)
-
Dale Alspach