Title :
LP decoding meets LP decoding: A connection between channel coding and compressed sensing
Author :
Dimakis, Alexandros G. ; Vontobel, Pascal O.
Author_Institution :
Dept. of Electr. Eng.-Syst., Univ. of Southern California, Los Angeles, CA, USA
fDate :
Sept. 30 2009-Oct. 2 2009
Abstract :
This is a tale of two linear programming decoders, namely channel coding linear programming decoding (CC-LPD) and compressed sensing linear programming decoding (CS-LPD). So far, they have evolved quite independently. The aim of the present paper is to show that there is a tight connection between, on the one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on the other hand, CC-LPD of the binary linear code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows one to translate performance guarantees from one setup to the other.
Keywords :
channel coding; decoding; linear programming; binary linear code; binary parity-check matrix; channel coding; compressed sensing; linear programming decoders; linear programming decoding; zero-one measurement matrix; Channel coding; Compressed sensing; Decoding; Error correction; Linear code; Linear programming; Noise robustness; Parity check codes; Sparse matrices; Symmetric matrices;
Conference_Titel :
Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4244-5870-7
DOI :
10.1109/ALLERTON.2009.5394826
