LDPC Codes for Compressed Sensing

Abstract

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, \emph{channel coding linear programming decoding (CC-LPD)}, which is a well-known relaxation o maximum-likelihood channel decoding for binary linear codes, and, on the other hand, \emph{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 under-determined system of linear equations. More specifically, we establis 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 (LDPC) codes constructed by Gallager.

To appear, IEEE Transactions on Information Theory, 2012

References in corpus (13)

• Near-ideal model selection by ${\ell }_1$ minimization
• Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes
• Compressed sensing performance bounds under Poisson noise
• Probabilistic Analysis of Linear Programming Decoding
• Why Gabor Frames? Two Fundamental Measures of Coherence and Their Role in Model Selection
• A Decomposition Theory for Binary Linear Codes
• Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
• On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing
• On the Block Error Probability of LP Decoding of LDPC Codes
• Absdet-Pseudo-Codewords and Perm-Pseudo-Codewords: Definitions and Properties
• The Benefit of Thresholding in LP Decoding of LDPC Codes

Cited by in corpus (10)

• Unknown sparsity in compressed sensing: Denoising and inference
• Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes
• Near-optimal Binary Compressed Sensing Matrix
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• Boolean Matrix Factorization and Noisy Completion via Message Passing
• A signal recovery algorithm for sparse matrix based compressed sensing
• Sparsification of Matrices and Compressed Sensing
• Compressed Sensing with Incremental Sparse Measurements
• Verification-Based Interval-Passing Algorithm for Compressed Sensing
• Contact Tracing Information Improves the Performance of Group Testing Algorithms