LDPC Codes for Compressed Sensing

DOI10.1109/TIT.2011.2181819MaRDI QIDQ5271971zbMATH OpenFDO

Authors Alexandros G. Dimakis, Roxana Smarandache, Pascal O. Vontobel

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.0602

Mathematics Subject Classification ID

Applications of graph theory (05C90) Linear programming (90C05) Linear codes (general theory) (94B05) Sampling theory in information and communication theory (94A20)

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.

Cited in

(9)

• Computing the spark: mixed-integer programming for the (vector) matroid girth problem
• Polynomial data structure lower bounds in the group model
• Peeling decoding of LDPC codes with applications in compressed sensing
• Deterministic construction of sparse binary matrices via incremental integer optimization
• Analysis of Termatiko sets in measurement matrices
• Flexible construction of measurement matrices in compressed sensing based on extensions of incidence matrices of combinatorial designs
• Deterministic construction of compressed sensing matrices from codes
• When can an expander code correct (n) errors in O(n) time?
• An effective algorithm for the spark of sparse binary measurement matrices

This page was built for publication: LDPC Codes for Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5271971)