LDPC Codes for Compressed Sensing

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, c...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2012-05, Vol.58 (5), p.3093-3114
Main Authors: Dimakis, A. G., Smarandache, R., Vontobel, P. O.
Format: Article
Language:English
Subjects:
Applied sciences
Approximation guarantee
Approximation methods
basis pursuit
Channel coding
Channels
Coding theory
Coding, codes
Compressed
Compressed sensing
Data compression
Decoding
Detection
Exact sciences and technology
graph cover
Information theory
Information, signal and communications theory
Linear programming
linear programming decoding
Low density parity check codes
Mathematical analysis
Matrices
Matrix
Matrix methods
Maximum likelihood decoding
Maximum likelihood method
pseudocodeword
pseudoweight
Sampling, quantization
Signal and communications theory
sparse approximation
Sparse matrices
Telecommunications and information theory
Vectors
zero-infinity operator
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, compressed sensing linear programming decoding (CS-LPD), also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an underdetermined system of linear equations. More specifically, we establish a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of "good" channel codes can be used as provably "good" measurement matrices under basis pursuit. In particular, we provide the first deterministic construction of compressed sensing measurement matrices with an order-optimal number of rows using high-girth low-density parity-check codes constructed by Gallager.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2011.2181819