Near optimal efficient decoding from pooled data
share
The objective of the pooled data problem is to design a measurement matrix A that allows to recover a signal ∈0, 1, 2, …, d^n from the observation of the vector = A of joint linear measurements of its components as well as from A itself, using as few measurements as possible. It is both a generalisation of the compelling quantitative group testing problem as well as a special case of the extensively studied compressed sensing problem. If the signal vector is sparse, that is, its number k of non-zero components is much smaller than n, it is known that exponential-time constructions to recover from the pair (A, ) with no more than O(k) measurements exist. However, so far, all known efficient constructions required at least Ω(kln n) measurements, and it was an open question whether this gap is artificial or of a fundamental nature. In this article we show that indeed, the previous gap between the information-theoretic and computational bounds is not inherent to the problem by providing an efficient recovery algorithm that succeeds with high probability and employs no more than O(k) measurements.
READ FULL TEXT