PaperlayerView exact revision on arXiv

Source-linked AI summary

LDPC Codes for Compressed Sensing

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

arXiv:1012.0602v2cs.ITmath.NA

TL;DR

The paper asks whether CS-LPD and CC-LPD, which arise from real-valued sparse recovery and finite-field channel decoding, have a connection beyond superficial similarity. It constructs a bridge for zero-one matrices, transfers decoding guarantees to basis pursuit, and obtains deterministic order-optimal measurement matrices from high-girth Gallager LDPC codes.

  • Problem

    The paper asks whether CS-LPD and CC-LPD have a connection beyond their superficial similarity despite operating over real-valued and finite-field formulations.

  • Method

    The paper maps nonzero real-nullspace vectors of a zero-one measurement matrix to nonzero vectors in the fundamental cone of the same matrix used as a binary parity-check matrix.

  • Results

    High-girth Gallager LDPC matrices yield deterministic basis-pursuit measurement matrices with an order-optimal number of rows; for m/n = 1/2 and a (3, 6)-regular graph, recovery holds with high probability for α ≤ 0.05.

  • Takeaways & Limitations

    Performance guarantees for good binary channel-code parity-check matrices can be translated into compressed-sensing recovery guarantees for the same matrices over the reals.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper establishes a connection between channel-coding and compressed-sensing linear-programming decoders, showing that channel-code performance guarantees can transfer to basis pursuit for zero-one matrices. This connection yields deterministic, order-optimal compressed-sensing matrices from high-girth LDPC constructions.

  • I. INTRODUCTION: CS-LPD and CC-LPD, although defined over real and finite-field settings respectively, are connected through zero-one measurement matrices viewed as binary parity-check matrices.The bridge maps problematic real-nullspace vectors to problematic vectors in the fundamental cone of the corresponding code.
  • I. INTRODUCTION: If a parity-check matrix corrects any k bit-flipping errors under CC-LPD, the same matrix recovers all k-sparse error signals under CS-LPD.The guarantee is point-wise over the error support, not merely an average-case correspondence.
  • I. INTRODUCTION: CC-LPD guarantees for suitable channels translate into robust CS-LPD guarantees in ℓ1/ℓ1, ℓ2/ℓ1, and ℓ∞/ℓ1 senses.The ℓ1/ℓ1 result applies to binary-input output-symmetric channels with bounded log-likelihood ratios, while the ℓ2/ℓ1 result applies to the AWGNC.
  • I. INTRODUCTION: The established implication is one-way: good CC-LPD parity-check matrices yield good CS-LPD measurement matrices, but the converse is not proved.The reverse direction remains an open problem.
  • I. INTRODUCTION: The paper also develops graph-cover reformulations and a zero-infinity-operator relaxation to expose further similarities between the two decoding frameworks.These additional formulations complement the main bridge between CS-LPD and CC-LPD.

B. Conditions for the Equivalence of CS-LPD and CS-OPT

This section characterizes when basis pursuit recovers the sparsest solution and when it provides approximation guarantees. The nullspace property supplies the necessary and sufficient matrix condition used later to connect compressed sensing with channel decoding.

  • B. Conditions for the Equivalence of CS-LPD and CS-OPT: The central question is when CS-LPD equals the NP-hard CS-OPT solution while using relatively few measurements, especially in the linear sparsity regime.The paper focuses typically on k = Θ(n) and m = Θ(n), where linear measurement scaling is optimal.
  • B. Conditions for the Equivalence of CS-LPD and CS-OPT: The paper uses nullspace characterization rather than RIP because the nullspace condition directly characterizes when the LP relaxation is good.RIP can certify recovery and robustness, but it is not a complete characterization of good LP measurement matrices.
  • B. Conditions for the Equivalence of CS-LPD and CS-OPT: The nullspace property is a necessary and sufficient condition for a measurement matrix to recover all k-sparse signals exactly under CS-LPD.Under this condition, the CS-LPD estimate equals the CS-OPT estimate for signals with at most k nonzero components.
  • B. Conditions for the Equivalence of CS-LPD and CS-OPT: For approximately sparse signals, ℓp/ℓq guarantees bound CS-LPD error relative to the best k-sparse approximation, with exact recovery as a special case.When e is k-sparse, the approximation residual vanishes, so the guarantee implies exact recovery.

IV. CHANNEL CODING

The channel-coding setup defines maximum-likelihood decoding for binary linear codes and relaxes it through a fundamental polytope, yielding CC-LPD. Its performance depends on the parity-check matrix and channel-specific pseudo-codeword behavior.

  • A. The Setup: A binary linear code is specified by a generator matrix over F2, with codewords generated as x = G_CC · u (mod 2), while a parity-check matrix characterizes valid codewords by H_CC · x = 0 (mod 2).
  • A. The Setup: CC-LPD uses log-likelihood ratios and a channel-dependent linear objective rather than the binary syndrome vector for its main analysis.
  • A. The Setup: CC-MLD maximizes the channel likelihood over codewords, while CC-LPD minimizes a linear cost over the fundamental polytope containing the codeword convex hull.The exact convex-hull formulation is generally exponential, motivating the relaxed polytope formulation.
  • A. The Setup: The fundamental polytope contains the convex hull of codewords, and its vertices include all codeword vertices; different parity-check matrices can therefore induce different CC-LPDs.
  • A. The Setup: CC-LPD performance is evaluated relative to CC-MLD, although even maximum-likelihood decoding can fail beyond the channel code’s error-correction capability.
  • A. The Setup: The fundamental cone is the conic hull associated with the fundamental polytope, and both polytope and cone points are called pseudo-codewords in this framework.

B. Conditions for the Equivalence of CC-LPD and CC-MLD

A BSC success condition for CC-LPD is expressed through inequalities over fundamental-cone pseudo-codewords and connects directly to pseudo-weight measures. These channel-dependent weights quantify the effective distance relevant to fractional decoding errors.

  • B. Conditions for the Equivalence of CC-LPD and CC-MLD: If every nonzero fundamental-cone pseudo-codeword satisfies the BSC inequality for the flipped-coordinate set, CC-LPD returns the transmitted codeword.The condition is also necessary, although that fact is not used subsequently.
  • B. Conditions for the Equivalence of CC-LPD and CC-MLD: Pseudo-weights depend on the channel, whereas the fundamental polytope and cone depend only on the parity-check matrix.Thus, each channel supplies its own measure of pseudo-codeword distance for CC-LPD analysis.
  • B. Conditions for the Equivalence of CC-LPD and CC-MLD: The BSC pseudo-weight is defined from the sorted pseudo-codeword components and is used to express the relevant BSC decoding condition.
  • B. Conditions for the Equivalence of CC-LPD and CC-MLD: The max-fractional weight is efficiently computable but yields weaker performance guarantees than the other pseudo-weight quantities.

V. ESTABLISHING A BRIDGE BETWEEN CS-LPD AND CC-LPD

For zero-one measurement matrices, absolute values map real nullspace vectors into the associated binary code’s fundamental cone, creating a bridge from CC-LPD guarantees to CS-LPD recovery guarantees. The translation covers exact, robust, and point-wise recovery statements.

  • V. ESTABLISHING A BRIDGE BETWEEN CS-LPD AND CC-LPD: For a zero-one measurement matrix, every real nullspace vector ν maps to the fundamental-cone point |ν| with the same support.This is a one-way mapping: fundamental-cone points need not correspond to real nullspace vectors.
  • V. ESTABLISHING A BRIDGE BETWEEN CS-LPD AND CC-LPD: Absence of low pseudo-weight points with a given support in the fundamental cone implies absence of problematic real-nullspace points with that support, enabling point-wise CS-LPD guarantees.
  • V. ESTABLISHING A BRIDGE BETWEEN CS-LPD AND CC-LPD: The bridge assumes zero-one measurement matrices in its main use, while extensions to less restricted matrices are discussed but generally not used.
  • V. ESTABLISHING A BRIDGE BETWEEN CS-LPD AND CC-LPD: If the parity-check matrix corrects any k BSC bit-flipping errors under CC-LPD, the same matrix recovers all k-sparse error signals under CS-LPD.

B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD

The paper translates CC-LPD guarantees beyond the BSC into compressed-sensing recovery results, including strong and weak bounds for sparse matrices. Its central explicit result uses high-girth Gallager LDPC constructions to obtain deterministic, order-optimal measurement matrices, while retaining scope limitations.

  • B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD: The bridge lemma translates three positive LDPC CC-LPD threshold results into corresponding CS-LPD/basis-pursuit guarantees.The translated results include strong, weak, and high-girth-based recovery statements.
  • B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD: For m/n = 1/2 and d_v = 32, sparse expander-based zero-one matrices recover all k = αn sparse vectors for α ≤ 0.000175.This is a strong bound because it covers every k-sparse vector.
  • B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD: For m/n = 1/2 and d_v = 8, random sparse matrices recover randomly supported k = αn vectors with high probability when α ≤ 0.002.This weak bound applies with high probability over the vector support rather than uniformly over all supports.
  • B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD: For m/n = 1/2, Gallager’s (3, 6)-regular logarithmic-girth matrices recover k = αn sparse vectors with high probability when α ≤ 0.05.The construction is deterministic and has an order-optimal number of measurements.
  • B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD: Girth provides a polynomial-time-certifiable route to good sparse measurement matrices, avoiding the harder task of constructing or checking high expansion.Gallager’s logarithmic-girth LDPC matrices therefore yield deterministic zero-one matrices with order-optimal measurement counts.
  • B. The Role of Binary-Input Channels Beyond the BSC for CS-LPD: Corollary 18 guarantees recovery of almost all k-sparse signals, not every one, and known expansion-based deterministic constructions may provide stronger uniform guarantees.The paper also notes that logarithmic girth gives exponentially decaying failure probability, while smaller logarithmic-logarithmic girth gives inverse-polynomial decay.

G. Comments on Dense Measurement Matrices

The paper finds that translating CC-LPD guarantees to CS-LPD becomes weaker for dense measurement matrices. It contrasts this with graph-cover reformulations and a dense signed-matrix example whose compressed-sensing behavior exceeds the translated channel-coding prediction.

  • G. Comments on Dense Measurement Matrices: The authors conclude that translated CS-LPD guarantees weaken as measurement matrices become denser.This conclusion summarizes the paper’s stated understanding of the CC-LPD-to-CS-LPD translation for dense matrices.
  • G. Comments on Dense Measurement Matrices: For dense matrices, CS-LPD can substantially outperform what the CC-LPD translation predicts, so the bridge is not tight in this regime.The paper explicitly identifies this mismatch for dense measurement matrices.
  • G. Comments on Dense Measurement Matrices: Graph-cover reformulations express CC-LPD and CS-LPD through lifted Tanner-graph constructions, clarifying their formal similarities and differences.The measurement matrices in the CS-LPD cover formulation are induced by possible M-covers of the Tanner graph.
  • G. Comments on Dense Measurement Matrices: Figure 1 organizes graph-cover examples by cover size: the base graph G, possible 2-covers, a possible 3-cover, and a possible M-cover.The covers are formed using arbitrary edge permutations σ_e1 through σ_e5.
  • G. Comments on Dense Measurement Matrices: Figure 2 shows the analogous progression from a Tanner graph T(H) to possible 3-covers and M-covers using arbitrary edge permutations.These lifted Tanner graphs support graph-cover formulations of channel-coding and compressed-sensing decoders.

C. Reformulations of CS-OPT

The paper reformulates CS-OPT, CS-LPD, and related channel-decoding problems to expose their formal relationships, including a graph-cover reformulation of CS-LPD. It also introduces CS-OPT0,∞ and argues that CS-LPD is more closely aligned with this objective than with sparsity alone.

  • D. Reformulations of CS-LPD: CS-LPD has a graph-cover reformulation, CS-LPD1, that is formally close to the graph-cover formulation of CC-LPD3 (BSC).The reformulation minimizes over positive cover sizes and measurement matrices induced by Tanner-graph covers.
  • D. Reformulations of CS-LPD: CS-LPD changes the objective function while retaining the feasible domain, unlike CC-LPD, which retains its cost function while relaxing the domain.These differences are reflected in the corresponding graph-cover formulations.
  • C. Reformulations of CS-OPT: CS-OPT0,∞ minimizes the product of sparsity and maximum component magnitude, thereby penalizing imbalance among nonzero entries.The paper defines this objective as a trade-off between support size and the largest component magnitude.
  • C. Reformulations of CS-OPT: Over F2, the zero-infinity operator equals Hamming weight, establishing a close formal relationship between CC-MLD (BSC), CS-OPT, and CS-OPT0,∞.This relationship motivates viewing CS-LPD as a relaxation associated with more than one underlying optimization problem.

B. Geometrical Aspects of CS-OPT0,∞

The paper interprets CS-OPT, CS-LPD, and CS-OPT0,∞ geometrically through their unit balls and connects CS-LPD to a relaxation of the zero-infinity objective. It concludes that CS-LPD is at least as good an approximation for CS-OPT0,∞ as for CS-OPT, under the stated reformulation results.

  • B. Geometrical Aspects of CS-OPT0,∞: The zero-infinity unit ball is closer in shape to the ℓ1 unit ball than the ℓ0 unit ball is, motivating closer CS-LPD and CS-OPT0,∞ solutions.CS-OPT and CS-LPD correspond to finding the smallest respective norm balls intersecting the feasible set.
  • B. Geometrical Aspects of CS-OPT0,∞: CS-REL0,∞ is introduced as a relaxation of CS-OPT0,∞ and is shown equivalent to CS-LPD for rational syndrome vectors and measurement matrices with entries in {0,1,−1}.The equivalence preserves optimal solutions through the mapping ϕM.
  • IX. CONCLUSIONS AND OUTLOOK: The paper identifies extending the nullspace connection to noisy compressed sensing as an open research direction.Noisy measurements can still be addressed with ℓ1 minimization, but the corresponding coding-theory connection remains to be investigated.

APPENDIX A PROOF OF THEOREM 5

The appendix proves Theorem 5 and extends the bridge between compressed sensing nullspaces and coding-theoretic structures beyond the basic zero-one real setting. It develops complex-valued and cover-based generalizations while preserving mappings between nullspaces and related constructions.

  • APPENDIX A PROOF OF THEOREM 5: Theorem 5’s proof derives the CS-LPD error guarantee by placing the reconstruction error in the measurement matrix’s nullspace and applying the assumed nullspace property.The argument uses ℓ1 optimality, triangle inequalities, and norm relations before solving for the reconstruction error.
  • APPENDIX D EXTENSIONS OF THE BRIDGE LEMMA: For complex measurement matrices with entries of absolute value zero or one, a nullspace vector is mapped through componentwise magnitudes into the fundamental cone.The proof verifies the cone conditions using the measurement equations and triangle inequality.
  • APPENDIX D EXTENSIONS OF THE BRIDGE LEMMA: The cover construction extends to complex matrices with integer entry magnitudes by replacing each nonzero entry with signed sums of permutation matrices.The resulting cover matrix has entries whose absolute values are zero or one.
  • APPENDIX D EXTENSIONS OF THE BRIDGE LEMMA: For the constructed covers, nullspace membership transfers between the base matrix and cover matrix through lifting and the mapping ϕM.The appendix states both the lifting implication and its converse under the defined construction.

APPENDIX E PROOF OF THEOREM 13

The proof of Theorem 13 applies the nullspace property to the difference between the original sparse signal and the CS-LPD estimate. Norm inequalities then yield the stated reconstruction-error bound.

  • APPENDIX E PROOF OF THEOREM 13: The reconstruction error ν=e−ê lies in the nullspace because both the original signal and CS-LPD estimate satisfy the same measurement equation.The proof combines CS-LPD’s ℓ1 optimality with triangle inequalities and the assumed weighted nullspace bound.
  • APPENDIX E PROOF OF THEOREM 13: The proof concludes by subtracting the support contribution and solving for ∥ν∥2=∥e−ê∥2.The resulting inequality gives the promised reconstruction-error guarantee.

APPENDIX F PROOF OF THEOREM 14

The proof shows that the error ν=e−ê lies in the nullspace of HCS and derives an ℓ∞ recovery bound from a nullspace assumption and norm inequalities.

  • ν=e−ê belongs to NullspR(HCS) because both e and ê satisfy the same measurement equation HCS·e=s.
  • The proof applies the assumption ∥ν∥1≥C′·∥ν∥∞ to nullspace vectors, together with bounds relating ℓ1 and ℓ∞ norms.The argument also uses ∥a∥1≤k·∥a∥∞ and ∥aS∥∞≤∥a∥∞.
  • Subtracting the support-error term and solving for ∥ν∥∞ yields the claimed bound on ∥e−ê∥∞.

APPENDIX G PROOF OF THEOREM 21

The proof reformulates both the CS-LPD objective and constraints through error variables, then compares feasible solutions in graph covers with their base-graph projections.

  • Objective reformulation: For the objective, the binary modulo-2 expression is rewritten over the reals so minimizing over codeword variables becomes minimizing ∥λsupp(e′)∥1 over error variables.The first resulting sum depends only on y, while the remaining term is ⟨|λ|,e′⟩=∥λsupp(e′)∥1.
  • Constraint reformulation: For the constraint, the proof introduces e′=y−x′ (mod 2) and rewrites feasibility through the corresponding parity-check equation.
  • Graph-cover comparison: Every feasible vector in an M-cover projects to a feasible base-graph vector whose cost is no larger than the cover vector’s cost.This follows because the cover constraint implies HCS·ϕM(ẽ′)=s, while the projection preserves feasibility and does not increase cost.

APPENDIX I PROOF OF THEOREM 24

The proof establishes equality between the optimal values of CS-REL0,∞ and CS-LPD by proving both an optimization inequality and a graph-cover realization of every CS-LPD optimum.

  • The proof has two parts: CS-REL0,∞ cannot have a smaller minimum than CS-LPD, and every CS-LPD minimizer is realized by a suitable graph cover configuration.
  • Rational minimizer: A rational CS-LPD minimizer exists because the linear program has rational coefficients and rational vertices, including when the minimizer is not unique.
  • Cover construction: The redefined matrices contain only 0, 1, and −1 entries, and the resulting Tanner graph remains a valid M-fold cover of the base Tanner graph.
  • Optimal-value equality: The lifted configuration is arranged so its projection equals the chosen minimizer and satisfies the required zero-infinity objective relation, completing the reverse inequality.The proof uses the projection identity and the cost comparison established for arbitrary feasible lifted configurations.
  • Cover construction: The construction embeds a normalized rational minimizer into an M-fold Tanner-graph cover using integer-coordinate polytope vertices and rational convex-combination weights.The cover size is chosen as M=μ/μ′, and the lifted configuration projects back to the original minimizer.
Loading 1012.0602v2…