Almost Separable Matrices

Abstract

An $m\times n$ matrix $\mathsf{A}$ with column supports $\{S_i\}$ is $k$-separable if the disjunctions ${\bigcup }_{i\in \mathcal{K}}{S}_i$ are all distinct over all sets $\mathcal{K}$ of cardinality $k$. While a simple counting bound shows that $m>k{\log }_{2}n/k$ rows are required for a separable matrix to exist, in fact it is necessary for $m$ to be about a factor of $k$ more than this. In this paper, we consider a weaker definition of `almost $k$-separability', which requires that the disjunctions are `mostly distinct'. We show using a random construction that these matrices exist with $m=O(k\log n)$ rows, which is optimal for $k=O(n^{1-\beta })$. Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.

References in corpus (1)

• Bounds on the rate of superimposed codes

Cited by in corpus (6)

• Performance of group testing algorithms with near-constant tests-per-item
• The capacity of Bernoulli nonadaptive group testing
• Improved group testing rates with constant column weight designs
• Strong converses for group testing in the finite blocklength regime
• On the optimality of some group testing algorithms
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach