Almost disjunct matrices from codes and designs

Alexander Barg, Arya MazumdararXiv 2015 · arXiv · OpenReview

Abstract

In group testing, binary-output tests are designed to identify a small number $t$ of defective items within a large population $N$. Traditionally, this requires $(t)$-disjunct matrices that guarantee recovery for any possible set of defectives. This paper explores a relaxation of this combinatorial problem: $(t, \epsilon)$-disjunct matrices. These matrices identify a uniformly random $t$-set of defective items with a false positive probability of at most $\epsilon$. By establishing a new connection between these matrices and the dual distance of error-correcting codes, we derive improved parameter estimates for non-adaptive group testing schemes. Our approach utilizes the moments of the distance distribution of codes and combinatorial design theory to provide more efficient testing regimes than traditional deterministic methods.

Introduction

Group testing is a fundamental problem in information theory and combinatorics, focusing on identifying a small subset of "defective" items ($t$) from a large population ($N$) using a minimal number of tests ($M$). In non-adaptive group testing, all tests are determined beforehand and can be represented as a binary matrix where rows are tests and columns are items.

Historically, the focus has been on $t$-disjunct matrices, which ensure the identification of defectives regardless of which $t$ items are chosen. However, this worst-case guarantee is often expensive, typically requiring $M \approx t^2 \log N$ tests. This paper investigates the "almost disjunct" problem: if we only require the identification of a randomly chosen set of defectives with high probability, can we significantly reduce $M$? This relaxation is highly relevant for practical applications like genetic screening or network fault detection, where worst-case scenarios are statistically improbable.

The Dual Distance Connection

The core innovation of this research is the shift from a code's minimum distance to its dual distance ($d'$). While minimum distance measures the separation between the closest codewords, dual distance indicates how closely the code's distribution resembles a truly random distribution.

Methodology

The authors employ several sophisticated mathematical tools to establish this link:

  1. Kautz-Singleton Construction: This method is used to transform non-binary codes (such as Reed-Solomon codes) into binary matrices suitable for group testing.
  2. Moment Analysis: By utilizing Pless power moment identities, the researchers relate the dual distance of a code to the moments of its distance distribution. High dual distance implies that the codewords behave like independent random variables for low-order statistics.
  3. Probabilistic Bounds: To bound the probability of a "false positive"—where a non-defective item's signature is covered by the union of the actual defectives—the authors apply Hoeffding, Marcinkiewicz-Zygmund, and Rosenthal inequalities.

Bridging to Combinatorial Designs

The paper further establishes a bridge between group testing and combinatorial $t$-designs. It demonstrates that binary constant-weight codes with high dual distance are essentially equivalent to these designs. This connection allows the researchers to leverage decades of work in algebraic combinatorics to create efficient group testing schemes. The "strength" of a combinatorial design is shown to be directly proportional to the dual distance, providing a clear metric for evaluating potential test matrices.

Key Results and Efficiency

The proposed methods successfully break the traditional $t^2$ barrier in many scenarios:

  • Reed-Solomon (RS) Schemes: For RS codes, the authors achieve a test complexity of $M = O(\max\{t^2, t(\frac{\log N}{\log t})^3\})$.
  • Information-Theoretic Gains: The paper proves the existence of schemes using $M = O(t \log^2 N / \log^2 t)$ tests that identify a random defective set with an error probability of at most $\exp(-\log N / \log t)$. This represents a $\log t$ factor improvement over previous "almost disjunct" constructions.
  • Algebraic Curve Codes: Specific parameters are provided for Hermitian and Suzuki codes, demonstrating their ability to handle very large populations ($N$) with relatively few tests ($M$). For example, Hermitian codes can handle $N \approx q^{2q^2}$ with $M=q^5$.

Discussion and Future Outlook

While the paper provides explicit results for Reed-Solomon and Algebraic-Geometric codes, some of the most efficient results remain existence claims based on known $t$-designs. The authors note that their theoretical bounds are likely conservative. Preliminary experimental simulations with BCH codes suggest that the actual false-positive rates are significantly lower than the current theory predicts.

Future work will focus on optimizing the constants in the Khinchine-type inequalities used in the proofs and moving from existence claims to explicit, easily generated matrices for the most efficient regimes. By relaxing the requirement from worst-case to average-case success, this research opens a path toward group testing schemes that approach the information-theoretic lower bound of $O(t \log N)$.

Summary updated

Abstract

In group testing, simple binary-output tests are designed to identify a small number $t$ of defective items that are present in a large population of $N$ items. Each test takes as input a group of items and produces a binary output indicating whether the group is free of the defective items or contains one or more of them. In this paper we study a relaxation of the combinatorial group testing problem. A matrix is called $(t,\epsilon)$-disjunct if it gives rise to a nonadaptive group testing scheme with the property of identifying a uniformly random $t$-set of defective subjects out of a population of size $N$ with false positive probability of an item at most $\epsilon$. We establish a new connection between $(t,\epsilon)$-disjunct matrices and error correcting codes based on the dual distance of the codes and derive estimates of the parameters of codes that give rise to such schemes. Our methods rely on the moments of the distance distribution of codes and inequalities for moments of sums of independent random variables. We also provide a new connection between group testing schemes and combinatorial designs.
BibTeX
@misc{barg2015almost,
  author = {Alexander Barg and Arya Mazumdar},
  title = {{Almost disjunct matrices from codes and designs}},
  year = {2015},
  eprint = {1510.02873},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.02873},
}

Loading related content...

Figure