Almost separable matrices

An $$m\times n$$ m × n matrix $$\mathsf {A}$$ A with column supports $$\{S_i\}$$ { S i } is k-separable if the disjunctions $$\bigcup _{i \in \mathcal {K}} S_i$$ ⋃ i ∈ K S i are all distinct over all sets $$\mathcal {K}$$ K of cardinality k. While a simple counting bound shows that $$m > k \log _2 n/k$$ 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)$$ m = O ( k log n ) rows, which is optimal for $$k = O(n^{1-\beta })$$ 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.