Title :
Error correction via linear programming
Author :
Candes, Emmanuel ; Rudelson, Mark ; Tao, Terence ; Vershynin, Roman
Author_Institution :
Applied and Computational Mathematics
Abstract :
Suppose we wish to transmit a vector f ϵ Rn reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?
Keywords :
Decoding; Encoding; Error correction; Error correction codes; Functional analysis; Linear code; Linear programming; Mathematics; Particle measurements; Vectors;
Conference_Titel :
Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Conference_Location :
Pittsburgh, PA
Print_ISBN :
0-7695-2468-0
DOI :
10.1109/SFCS.2005.5464411
