Mathematics – Functional Analysis
Scientific paper
2005-02-15
Mathematics
Functional Analysis
17 pages, 3 figures
Scientific paper
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.
Rudelson Mark
Vershynin Roman
No associations
LandOfFree
Geometric approach to error correcting codes and reconstruction of signals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Geometric approach to error correcting codes and reconstruction of signals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometric approach to error correcting codes and reconstruction of signals will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-242790