  In the pooled data problem, the goal is to identify the categories associated
with a large collection of items via a sequence of pooled tests. Each pooled
test reveals the number of items in the pool belonging to each category. A
prominent special case is quantitative group testing (QGT), which is the case
of pooled data with two categories. We consider these problems in the
non-adaptive and linear regime, where the fraction of items in each category is
of constant order. We propose a scheme with a spatially coupled Bernoulli test
matrix and an efficient approximate message passing (AMP) algorithm for
recovery. We rigorously characterize its asymptotic performance in both the
noiseless and noisy settings, and prove that in the noiseless case, the AMP
algorithm achieves almost-exact recovery with a number of tests sublinear in
the number of items. For both QGT and pooled data, this is the first efficient
scheme that provably achieves recovery in the linear regime with a sublinear
number of tests, with performance degrading gracefully in the presence of
noise. Numerical simulations illustrate the benefits of the spatially coupled
scheme at finite dimensions, showing that it outperforms i.i.d. test designs as
well as other recovery algorithms based on convex programming.
