PaperlayerView exact revision on arXiv

Source-linked AI summary

Boolean Compressed Sensing and Noisy Group Testing

George Kamal Atia, Venkatesh Saligrama

arXiv:0907.1061v6cs.IT

TL;DR

The paper addresses how to recover a small defective subset from many items with few tests, particularly when group-testing observations are noisy. It formulates testing as channel coding and detection, derives a single-letter mutual-information characterization, and obtains order-wise tight scaling results for several noisy models while extending the framework toward compressed sensing.

  • Problem

    Noisy group testing, especially in the non-adaptive setting, had been largely unexplored despite established analyses for noiseless group testing.

  • Method

    The paper maps group testing to a corresponding channel model and uses random coding, Maximum Likelihood detection, mutual information, and Fano's inequality.

  • Results

    The framework provides a single-letter characterization of test requirements, with order-wise tight scaling across noise-free, additive, dilution, and approximate-reconstruction settings.

  • Takeaways & Limitations

    The mutual-information expressions provide a general way to obtain tradeoffs among the number of tests, items, defectives, and noise, including applications beyond Boolean group testing.

Abstract

from arXiv · show

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. The single letter characterization is shown to be order-wise tight for many interesting noisy group testing scenarios. Specifically, we consider an additive Bernoulli($q$) noise model where we show that, for $N$ items and $K$ defectives, the number of tests $T$ is $O(\frac{K\log N}{1-q})$ for arbitrarily small average error probability and $O(\frac{K^2\log N}{1-q})$ for a worst case error criterion. We also consider dilution effects whereby a defective item in a positive pool might get diluted with probability $u$ and potentially missed. In this case, it is shown that $T$ is $O(\frac{K\log N}{(1-u)^2})$ and $O(\frac{K^2\log N}{(1-u)^2})$ for the average and the worst case error criteria, respectively. Furthermore, our bounds allow us to verify existing known bounds for noiseless group testing including the deterministic noise-free case and approximate reconstruction with bounded distortion. Our proof of achievability is based on random coding and the analysis of a Maximum Likelihood Detector, and our information theoretic lower bound is based on Fano's inequality.

I. INTRODUCTION

The paper reframes non-adaptive group testing as a channel coding and detection problem, yielding mutual-information bounds that cover noisy and high-dimensional settings. Its framework recovers known noiseless scalings while extending analysis to additive and dilution noise and broader compressed sensing models.

  • Research gap: The noisy group testing problem was largely unexplored, especially for non-adaptive testing where the measurement matrix is fixed before testing.Prior work mainly characterized noiseless combinatorial matrix properties.
  • Information-theoretic framework: The paper maps group testing to a channel coding and detection problem, deriving a single-letter mutual-information characterization of necessary and sufficient test-count conditions.The achievability analysis uses random coding and connects required tests to mutual-information expressions.
  • Information-theoretic framework: The characterization explicitly handles the fully high-dimensional regime in which both N and K approach infinity.Unlike analyses holding K fixed, the resulting bounds depend explicitly on both the number of items and defectives.
  • Scope and models: The framework verifies known noiseless and approximate-reconstruction bounds while analyzing additive false alarms and dilution effects in noisy group testing.The paper also states that its methods extend beyond Boolean arithmetic to support recovery with arbitrary discrete alphabets.
  • Problem setup: Group testing seeks to recover at most K defectives among N items using a binary measurement matrix and as few tests as possible.Tests pool items, producing positive outcomes when a pool contains a defective item.

D. Performance criteria

The paper models defective-set recovery as channel decoding and evaluates error through average and partial-reconstruction criteria. Random coding with maximum-likelihood decoding supports sufficient test conditions expressed through mutual information.

  • Performance criteria: The decoder maps test outcomes Y^T to an index identifying one of the possible defective sets.The conditional channel law gives the probability of each outcome sequence given a candidate defective set.
  • Performance criteria: Partial reconstruction counts the number of missed defectives and declares an error only when misses exceed αK.The distance between decoded and true sets is defined by the number of misses.
  • Random matrix generation and encoding: Randomly and independently generated item codewords define the measurement matrix used in the channel-coding formulation.The matrix distribution assumes independence across tests and items.
  • Decoding: Maximum-likelihood decoding selects the defective set most likely to have produced the observed test outcomes.The decoder considers all possible size-K sets and minimizes error under a uniform prior.
  • Performance criteria: Average error probability is averaged over defective sets and randomly generated codebooks, with an arbitrarily small target criterion.A good codebook exists when the ensemble-averaged error probability becomes arbitrarily small.
  • Main result: A sufficient condition for arbitrarily small average error probability is expressed using mutual information I(X_S1; X_S2, Y).The theorem states the condition for i = 1, 2, …, K and allows an arbitrarily small error probability asymptotically.
  • Probability of error analysis: For errors differing in exactly i items, P(E_i) measures whether the decoder selects a competing set at that distance, and the analysis sums these events.The error events are analyzed through their probabilities over codebooks and test outcomes.

D. Proof of Theorem III.1

The proof controls each error event through an error exponent and uses a Taylor expansion around zero. This yields a mutual-information condition sufficient to make the total average error probability vanish asymptotically.

  • Error exponent: The proof seeks a positive error exponent for each P(E_i), which drives the corresponding error probability to zero as N approaches infinity.The argument derives a sufficient condition for the exponent to be positive.
  • Taylor expansion: The exponent is expanded near ρ = 0 using differentiability and Taylor’s theorem.The expansion uses a remainder term evaluated at some ψ in the interval [0, ρ].
  • Sufficient condition: Choosing T relative to I(X_S1; X_S2, Y) makes the exponent grow with N and ensures an arbitrarily small P(E_i).The proof connects the test count to the mutual-information expression through the exponent condition.
  • Conclusion of proof: Summing the error-event probabilities over i gives a total error probability that approaches zero.The argument first establishes the result for fixed K and then takes the stated asymptotic limits.

E. Proof of Lemma III.1

The proof analyzes defective-set decoding by separating error events according to the number of misclassified items and relating each event to an equivalent channel. It then combines mutual-information bounds with Fano’s inequality to obtain achievable and converse test requirements.

  • Achievability and converse: The achievability analysis uses codebook and channel-output symmetries to derive explicit bounds, while the converse applies Fano’s inequality to lower-bound the required tests.The lower bound is stated for i.i.d. measurement-matrix components and must hold for every i.
  • Error-event decomposition: The analysis partitions candidate defective sets by i, the number of items differing from the true set, while K −i items overlap.The candidate family A contains K-item sets differing from the true defective set in exactly i items.
  • Scaling regime: For simultaneous growth with K = o(N), the achievable condition remains valid up to an extra polylog(K) factor, and it is order-wise tight with the converse up to that factor.The achievable and lower bounds share the same mutual-information denominator and have similarly scaling combinatorial numerators.
  • Information characterization: The mutual-information expression captures the information available per test when K −i defective items are known, while the numerator counts candidate sets with i substitutions.This yields tradeoffs among K, N, T, and noise for different models and error criteria.
  • Equivalent channel model: Each error channel represents recovery of K −i defectives and recognition of i remaining items; overall decoding error is bounded through the separate channel errors.The proof studies each error channel independently and then upper-bounds the total error probability.
  • Noise effects: The noisy-model scaling increases by 1/(1−u)^2 under dilution and by 1/(1−q) under additive noise.These factors are summarized as the test-count penalties for the two noise models.

V. NOISE FREE CASE-DETERMINISTIC OUTPUT

The noiseless case yields test-count guarantees for both average and worst-case reconstruction. Average-error recovery requires O(K log N) tests, whereas exact worst-case recovery requires O(K^2 log N) tests, with an additional polylogarithmic factor in one simultaneous-scaling regime.

  • Model: In the deterministic noiseless model, each test outcome is one exactly when at least one defective item is pooled, and zero otherwise.The output is determined with certainty by the pooled defective-set codeword.
  • Average error: O(K log N) tests achieve arbitrarily small average error probability for N items and K defectives.A constant C independent of N and K suffices when T ≥ C · K log N.
  • Average error: When N and K grow simultaneously with K = o(N), the noiseless sufficient condition includes an extra log^2 K factor.The paper attributes this polylogarithmic factor to conservatism in the error-exponent bounding technique.
  • Worst-case error: Exact reconstruction under the worst-case error criterion is achievable with T = O(K^2 log N) tests.Worst-case error requires controlling the maximum error over defective sets rather than only the average error.
  • Worst-case error: The worst-case guarantee is obtained by converting sufficiently small average error into the existence of a measurement codebook with zero worst-case error in the noiseless setting.Because the noiseless error indicator is binary, the selected codebook can have λ(X) = 0.

C. Achievability with Distortion

The paper studies approximate reconstruction, allowing up to αK defective-item misses, and establishes test-count guarantees for noisy group testing. For additive noise, average-error recovery uses O(K log N) scaling for fixed K, while worst-case criteria require replacing K with K^2.

  • Approximate reconstruction: Approximate reconstruction permits up to αK misses when K defective items are declared.The goal is recovering a large fraction rather than the entire defective set.
  • Approximate reconstruction: T = O(K log N) tests achieve approximate reconstruction with up to αK misses.This theorem concerns recovery with bounded distortion rather than exact recovery.
  • Additive noise: T = O(K log N) tests suffice for average-error recovery in the additive noise model when K is fixed.The average error probability goes to zero as N approaches infinity, with q parameterizing Bernoulli noise.
  • Additive noise: Larger q requires more tests because additive noise makes pooling-test outcomes less reliable through false alarms.The additive noise model captures false alarms in applications such as blood testing.
  • Additive noise: For worst-case error, the same additive-noise scaling holds after replacing K with K^2.In noisy settings, this criterion guarantees vanishing worst-case error probability rather than exact reconstruction as in the noise-free case.
  • Additive noise: If T = o of the theorem’s necessary additive-noise threshold, the error probability approaches 1.The cited theorem provides a converse condition on the number of tests.

B. Dilution

The dilution model treats defective items as probabilistically absent in tests, producing false negatives. The paper derives average- and worst-case test-count scalings, including an additional log^2 K factor in the simultaneous N,K asymptotic regime.

  • Dilution model: In the dilution model, positive items can behave as absent, causing erroneously negative test outcomes.This models dilution in pooled blood testing and related probabilistic transmission effects.
  • Average-error recovery: Larger u requires more tests because dilution makes test outcomes less reliable.The paper explicitly links the increased flip probability to increased testing requirements.
  • Simultaneous asymptotics: When N and K grow simultaneously with K = o(N), a positive constant C gives vanishing misidentification probability under the stated dilution condition.The theorem applies to the more general simultaneous-growth regime.
  • Simultaneous asymptotics: An extra log^2 K factor appears in the simultaneous N,K asymptotic result.The paper calls this polylogarithmic factor conservative and difficult to avoid with its error-exponent bounds.
  • Worst-case recovery: For worst-case error, the dilution scaling holds after replacing K with K^2.This is stated for the same dilution model and asymptotic scaling.

VII. CONCLUSIONS

The paper reframes group testing as an equivalent channel model and uses capacity-style information analysis to derive general achievable test-count tradeoffs. This framework covers a wide range of group testing problems.

  • Conclusions: The information-theoretic framework replaces random disjunct or separable matrix generation with equivalent channel modeling and capacity computation.The resulting achievable bound relates tests to the numbers of items and defectives.
  • Conclusions: The framework yields tradeoffs among the number of tests, items, and defectives across a wide range of group testing problems.The paper presents these tradeoffs as the main consequence of the general achievable bound.

A. Proof of Equation (25)

The proof decomposes competing codeword sets according to their shared and differing rows, then uses independence to factor their probabilities. This supports the comparison underlying Equation (25).

  • Proof of Equation (25): The proof partitions two candidate defective sets by the i codewords in which they differ and the K − i codewords they share.The shared and differing submatrices are named explicitly for the probability comparison.
  • Proof of Equation (25): Independence factors each candidate codeword probability into shared and nonshared components.Conditioning on one candidate fixes the shared submatrix in the summation.

B. Proof of Lemma III.1

The proof exploits symmetry by grouping competing defective sets according to their common and missed codeword values. It then bounds the ML error probability by conditioning on these values and the observed tests.

  • Symmetry reduction: Channel and codebook symmetries make the relevant error probability independent of the particular competing-set permutation.This permits taking unions and summations over competing sets without changing the associated probability expression.
  • Symmetry reduction: W1 and W2 represent the realized codewords on the common and missed parts of a competing set, respectively.The common part contains K−i rows and the missed part contains i rows, with component-wise equality defining each realization.
  • Probability representation: The joint probability of W1 and W2 is expressed through the original random submatrices, while the output distribution is written as the corresponding channel probability.These substitutions connect the auxiliary notation to the random codebook and group testing channel.
  • Error-set construction: The proof groups competing sets by overlap with the true defective set and defines the corresponding error sets through likelihood comparisons.For each competing set, the error event consists of codebooks whose likelihood under that set is at least the likelihood under the true set.
  • Conditional error bound: Conditioning on W1, W2, and Y^T enables the proof to compute the conditional error probability before summing over realizations.The subsequent simplification uses Bayes’ rule, conditional independence, and independence of codewords.

Appendix B: Proof of Theorem VI.3

The appendix derives a necessary test-count condition for the additive noise model by upper-bounding the relevant mutual information and applying the Fano-based lower bound. Substitution into the theorem yields the stated result.

  • Mutual-information bound: The proof targets a necessary condition on T for additive noise by bounding I(X_S1; X_S2, Y) under the channel model.The mutual-information bound is obtained through a sequence of inequalities and simplifications.
  • Theorem specialization: The lower bound must hold for every overlap index i, so the proof specializes to i = K to obtain the final constraint.This specialization is then substituted into the preceding inequality to recover Theorem VI.3.

Appendix C

Appendix C extends the analysis to the regime K = o(N) and proves channel-specific bounds by controlling derivatives of the error exponent. The arguments cover noiseless, additive-noise, and dilution channels.

  • Extension: The appendix extends Theorem III.1 to simultaneous growth of N and K with K = o(N), proving Theorems V.2, VI.2, and VI.5.This establishes the asymptotic regime used for the subsequent channel-specific analyses.
  • Error-exponent analysis: The proof lower-bounds the error exponent using Taylor expansion and worst-case second-derivative control.The mutual information at zero and bounds on the second derivative provide the ingredients for the resulting sufficient conditions.
  • Auxiliary quantities: The auxiliary quantities b_ρ and f_ρ are bounded random variables, while g_ρ is analyzed through monotonicity and derivative properties.These properties support the derivative bounds used throughout the appendix.
  • Noiseless channel: For the noiseless channel, the worst-case second derivative is characterized and evaluated by separating cases according to Y and X_S2.The resulting bound leads to the noiseless sufficient condition and associated test-count inequality.
  • Additive-noise channel: For additive noise, monotonicity and positivity of E[u_ρ log u_ρ] establish the second-derivative bound used in Theorem VI.2.The appendix states that this reproduces the sufficient condition obtained for the additive-noise channel.
  • Dilution channel: For dilution, bounded auxiliary terms and decreasing g_ρ reduce the analysis to evaluating its maximum at ρ = 0.Case analysis over Y, X_S2, and the number of ones in X_S1 yields Lemma VII.5 and Theorem VI.5.
Loading 0907.1061v6…