PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic Construction of Binary, Bipolar and Ternary Compressed Sensing Matrices

Arash Amini, Farokh Marvasti

arXiv:0908.2676v2cs.IT

TL;DR

The paper addresses deterministic compressed-sensing matrix design for sparse recovery, emphasizing practical sensing and reconstruction. It connects optical codes to binary matrices, constructs BCH-based bipolar and combined ternary matrices, and reports successful OMP recovery with FFT-enabled reconstruction structure.

  • Problem

    The paper seeks deterministic sensing matrices that guarantee RIP-based sparse recovery while supporting practical sampling and reconstruction.

  • Method

    The authors connect OOC codes to binary matrices, replace zeros in binary BCH vectors with −1 for bipolar matrices, and combine binary and bipolar designs into ternary matrices.

  • Results

    OMP recovers k-sparse signals for k = 4 using all tested deterministic matrices, while noisy experiments at k = 15 show continuous performance curves as noise varies.

  • Takeaways & Limitations

    The resulting designs provide deterministic {0,1,−1} sensing options with simple measurements, coherence-based greedy recovery, and FFT-enabled reconstruction acceleration.

Abstract

from arXiv · show

In this paper we establish the connection between the Orthogonal Optical Codes (OOC) and binary compressed sensing matrices. We also introduce deterministic bipolar $m\times n$ RIP fulfilling $\pm 1$ matrices of order $k$ such that $m\leq\mathcal{O}\big(k (\log_2 n)^{\frac{\log_2 k}{\ln \log_2 k}}\big)$. The columns of these matrices are binary BCH code vectors where the zeros are replaced by -1. Since the RIP is established by means of coherence, the simple greedy algorithms such as Matching Pursuit are able to recover the sparse solution from the noiseless samples. Due to the cyclic property of the BCH codes, we show that the FFT algorithm can be employed in the reconstruction methods to considerably reduce the computational complexity. In addition, we combine the binary and bipolar matrices to form ternary sensing matrices ($\{0,1,-1\}$ elements) that satisfy the RIP condition.

I. INTRODUCTION

The paper targets deterministic compressed-sensing matrices that support sparse recovery while improving practical sampling and reconstruction properties. It connects optical codes and binary matrices, develops bipolar and ternary constructions, and uses coherence, cyclic structure, and FFT-based reconstruction.

  • Motivation: Compressed sensing seeks to reconstruct a k-sparse n-dimensional vector from m linear measurements with m much smaller than n.The paper identifies sampling-matrix selection and sparse-signal reconstruction as the two central concerns.
  • Motivation: Deterministic matrices offer a specific realization with guaranteed behavior and may improve computational complexity and compression ratio.This contrasts with random matrices, for which average performance does not guarantee that a particular realization works.
  • Motivation: RIP provides a stable-recovery condition, and coherence bounds can establish RIP when δ_k = λ(k −1) < 1.The paper notes that basis-pursuit and greedy methods can recover sparse vectors under suitable RIP conditions.
  • Prior deterministic designs: Existing deterministic constructions face limitations involving explicit construction, matrix dimensions, or restricted growth of n relative to m.The introduction discusses Spikes and Sines, Grassmannian frames, Vandermonde matrices, Devore designs, extractor-based matrices, and statistical RIP constructions.
  • Contributions: Cyclic structure enables FFT-based acceleration, while coherence supports simple greedy reconstruction methods such as Matching Pursuit.These design choices address both sensing simplicity and reconstruction complexity.
  • Contributions: The paper establishes an optical-code connection for binary sensing matrices and introduces bipolar and ternary deterministic matrices with RIP guarantees.The bipolar matrices use binary BCH-code vectors with zeros replaced by −1, while ternary matrices combine binary and bipolar designs.

II. BINARY SAMPLING MATRICES

This section constructs binary RIP matrices from low-coherence columns, including matrices derived from Orthogonal Optical Codes and finite-field polynomial designs. The constructions provide deterministic dimension and correlation guarantees, while binary schemes have a documented limitation relative to the random compressed-sensing bound.

  • RIP construction: A normalized matrix with pairwise column coherence λ satisfies RIP of order k when δ_k = λ(k −1) < 1.The argument uses the Gram matrix and the Gershgorin circle theorem to bound its eigenvalues.
  • OOC-based matrices: Orthogonal Optical Codes use fixed-weight binary signatures whose low correlations support binary sensing matrices after normalization.Circular autocorrelation and cross-correlation matter when all circular shifts are included as columns.
  • OOC-based matrices: For q = 16^a, the described OOC construction yields a matrix of size (16^a −1) × n with n ⪅ (16^a−1)(16^a−6)^5.The construction uses finite-field elements and circular shifts of the OOC vectors.
  • Finite-field matrices: Devore’s binary matrices have dimensions p^2 × p^(r+1), column weight p, and pairwise inner products bounded by r before normalization.The construction is based on polynomials over GF(p), with p a prime power.
  • Finite-field matrices: Devore’s structures are shown to be asymptotically optimal under the cited bound, despite not attaining the random compressed-sensing bound.The paper also notes that binary matrices generally cannot reach the predicted bound unless w = O(m).

III. BIPOLAR MATRICES VIA LINEAR CODES

The paper converts suitable symmetric binary linear codes into bipolar sensing matrices by replacing zeros with −1. Their minimum-distance and inner-product properties establish RIP through Gershgorin’s theorem, while common binary codes impose a practical distance limitation.

  • Code-to-matrix construction: Symmetric binary codes contain complement pairs, allowing one vector from each pair to form the sensing matrix.The construction uses 2^k̃−1 selected code vectors.
  • Code-to-matrix construction: Replacing zeros by −1 turns the selected binary code vectors into normalized bipolar columns with unit-magnitude entries.The resulting columns are normal because every entry has absolute value 1 before normalization.
  • RIP guarantee: A minimum-distance bound limits the absolute inner product between distinct columns, and Gershgorin’s theorem then proves the RIP condition.The proof derives the inner-product bound from the Hamming distance between codewords and their complements.
  • RIP guarantee: The theorem is useful only when d̃_min is close to ñ, but ordinary binary codes typically satisfy d̃_min ≤ ñ−k̃+1.Achieving the required distance can require parity bits of the same order as the data payload, which is impractical.

A. BCH codes with large ˜dmin

The paper designs BCH codes with large minimum distance by selecting roots through a structured subset of a finite field. A combinatorial characterization of that subset yields the code dimension, while BCH root spacing supplies a deterministic distance lower bound.

  • BCH code design: BCH codes are cyclic binary codes generated by polynomials dividing x^(2^m̃−1)+1, making them suitable for deterministic code design.Their cyclic structure also supports the surrounding matrix construction.
  • BCH code design: The construction includes the all-one codeword, so h(x) defines a symmetric code compatible with the bipolar-matrix theorem.The factor x+1 yields the all-one codeword through the polynomial construction.
  • Distance guarantee: The BCH minimum distance obeys d̃_min ≥ 2^(m̃−1)−2^l because the generating polynomial contains an arithmetic progression of roots.This follows from the standard BCH bound relating consecutive roots to minimum distance.
  • Distance guarantee: Theorem 2 maps the code parameter k̃ to binary sequences whose circularly arranged 1s are separated by at least m̃−l−1 zeros.This converts counting roots into a combinatorial sequence-counting problem.

B. Matrix Construction

The construction selects BCH parameters and codewords to produce a cyclic bipolar sensing matrix. Its columns are generated from even-parity code vectors, with the degree of h(x) controlling the resulting matrix size.

  • Cyclic matrix construction: Selecting codewords from complement pairs can preserve closure under circular shifts, producing a cyclic sensing matrix.BCH codes are cyclic, and parity distinguishes complement pairs from shifted versions.
  • Parameter selection: For target RIP order k, the construction chooses i=⌈log2(k)⌉, m̃≥i, and m=2^m̃−1 compressed samples.The sequence constraint requires circular spacing of at least i zeros between 1s.
  • Cyclic matrix construction: The matrix uses even-parity BCH code vectors as binary columns, then replaces zeros with −1 and normalizes every column.The additional x+1 factor enforces even parity.
  • Matrix size: The degree of h(x) grows linearly initially but becomes exponential after a transition as m̃ and i vary.Figure 1 reports this degree behavior for different parameter choices.

IV. MATRICES WITH {0, 1, −1} ELEMENTS

The paper combines binary and bipolar RIP matrices to construct larger ternary sensing matrices with entries in {0,1,−1}. The resulting matrix retains the RIP through bounds on column norms and pairwise inner products.

  • Ternary construction: Binary and bipolar RIP matrices are combined to create ternary matrices with larger dimensions.The construction targets entries from the set {0,1,−1}.
  • RIP preservation: Changing signs in replicated nonzero entries preserves column norms while modifying inner products, enabling larger constructions without changing the RIP order and constant.The preliminary replication expands p^2×p^(r+1) to p^2×p^(r+2), which is negligible in order.
  • Ternary construction: The operation M(s,x) embeds a vector x into the nonzero locations of a binary vector s and fills all other locations with zero.This embedding supplies the block structure used to combine the two component matrices.
  • RIP preservation: For Mersenne-prime dimensions, the combined matrix is constructed from a binary matrix S and the bipolar matrix X.The resulting matrix has p^2 rows and p^(r+1)·2^k̃ columns before the displayed combination details.
  • RIP preservation: The combined matrix satisfies RIP of order k because its columns are normal and distinct-column inner products remain bounded.The proof handles equal and unequal binary-column indices separately.

V. RECONSTRUCTION FROM THE MEASUREMENTS

The section proves that RIP-constrained matrices support exact sparse recovery with Matching Pursuit in the noiseless setting. It also shows that circular column structure enables FFT-based acceleration of the reconstruction computations.

  • Matching Pursuit selects support indices through maximum residual-column inner products and can exactly recover noiseless sparse signals with proper updating.The proof shows that each selected maximum belongs to the true support; with a suitable rule, all support elements are identified after k iterations.
  • RIP of order 2k is sufficient for unique reconstruction of a k-sparse signal from its measurements.
  • The residual is initialized as y and updated iteratively after estimating coefficients from selected support indices.
  • Circular columns convert the inner-product calculations across shifts into circular convolution, enabling DFT or FFT evaluation.
  • FFT reconstruction requires less computational complexity than directly calculating all inner products for matrices with circular column structure.The method uses one DFT, one IDFT, and m multiplications, with reduced transforms when only μ distinct shifts occur.

VI. NUMERICAL RESULTS

Numerical experiments compare binary, bipolar, ternary, and Gaussian sensing matrices using OMP. All deterministic matrices recover signals at the design sparsity, while the bipolar matrix performs best at larger sparsity levels and all methods show noise stability.

  • Binary, bipolar, and ternary deterministic matrices are evaluated at RIP order k = 4 alongside Gaussian random matrices.The binary matrix is 64 × 512, the bipolar matrix is 63 × 512, and the tested ternary matrix is 49 × 512.
  • The bipolar matrix designed for RIP order 4 also guarantees RIP orders up to and including 7.
  • At k = 4, all deterministic matrices recover the sparse signals in the simulations.The experiments use OMP for k iterations and average recovery results over 5000 input signals for each sparsity level.
  • At k = 20, bipolar recovery is almost 24% better on average than random-matrix recovery and 29% better than Devore’s matrix recovery.
  • For k = 15 with measurement noise, recovery performance varies continuously with noise level, indicating stability in the reported experiments.The noisy results are averaged over 10000 runs using the same matrices and OMP reconstruction.

VII. CONCLUSION

The paper connects OOC codes with binary RIP matrices, then constructs deterministic bipolar and ternary sensing matrices. Simulations examine recovery across sparsity and noise, while the bipolar design also supports FFT-accelerated reconstruction.

  • OOC codes yield binary sampling matrices that fulfill the RIP condition.
  • Recovery experiments evaluate perfect recovery across sparsity and continuous performance under noise for BCH, Devore, and ternary matrices.Figure 2 uses SNRrec. ≥100dB; Figure 3 studies 15-sparse signals with varying noise powers.
  • BCH-based bipolar matrices replace zeros in binary code vectors with −1, producing deterministic ±1 sensing matrices.
  • Combining binary and bipolar constructions produces ternary sensing matrices with elements {0, 1, −1} that satisfy RIP.
  • The cyclic structure of the bipolar matrices enables FFT-based reconstruction to reduce computational complexity.

APPENDIX A

Appendix A analyzes the number of binary sequences used in the construction through κ(a)_b. Its growth is governed by the largest root γ of f(z)=z^(a+1)−z^a−1, with figures comparing exact values across a and b.

  • κ(a)_b counts binary sequences satisfying a spacing property between 1s under a circular definition.
  • Valid shorter sequences can be padded with zeros while preserving the required property, supporting recursive bounds on κ(a)_b.
  • For large b, κ(a)_b grows on the order of γ^b, where γ is the largest root of f(z)=z^(a+1)−z^a−1.
  • The defining polynomial has a real root γ between 1 and 2 because f(1)f(2)<0.
  • Figure 4 reports exact κ(a)_b values for different a and b, including comparisons as b increases.

APPENDIX B

Appendix B proves a lower bound on the parameter δ used in the construction. The proof establishes δ>a^0.7 by analyzing an auxiliary function and its minimum.

  • The proof introduces f(x)=x^0.3−0.5x^−0.4−0.7 ln x and shows that it is positive for every x>0.
  • The auxiliary function has one positive critical point, at approximately x=1.277^10≈11.532, where its value is approximately 0.18>0.
  • Using the lemma in the subsequent inequality yields the claimed bound δ>a^0.7.
Loading 0908.2676v2…