Almost separable matrices

An m× n matrix A with column supports { S_i} is k-separable if the disjunctions ⋃ _{i ∈ K}S_i are all distinct over all sets K of cardinality k. While a simple counting bound shows that m> klog ₂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(klog n) rows, which is optimal for k= O(n^{1 - β}). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.