  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.
