Almost separable matrices

An (mtimes 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.