Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a “small” number of “pooled” tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when D = O(N1-δ) for some δ > 0. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of the literature demonstrates that θ(D log(N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexities that are sub-linear in N have started being investigated. In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity (O (D log(N)) in both the performance metrics). The total number of stages of our adaptive algorithm is “small” (O (log(D))). Similarly, in the scenario with nonadaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires O (D log(D) log(N)) tests and has a decoding complexity of O(D(log N +log2D)). Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as O(D(log N +log2D)). For all three settings, the probability of error of our algorithms scales as O (1/(poly(D)). For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed “small” universal factors in our theorem statements.

Suppose x is any exactly k-sparse vector in Rn. We present a class of sparse matrices A, and a corresponding algorithm that we call short and fast1 (SHO-FA) that, with high probability over A, can reconstruct x from Ax. The SHO-FA algorithm is related to the invertible bloom lookup tables recently introduced by Goodrich et al., with two important distinctions- SHO-FA relies on linear measurements, and is robust to noise. The SHO-FA algorithm is the first to simultaneously have the following properties: 1) it requires only O(k) measurements; 2) the bit precision of each measurement and each arithmetic operation is O (log(n) + P) (here, 2-Pcorresponds to the desired relative error in the reconstruction of x); 3) the computational complexity of decoding is O(k) arithmetic operations and that of encoding is O(n) arithmetic operations; and 4) if the reconstruction goal is simply to recover a single component of x instead of all of x, with significant probability over A, this can be done in constant time. All the above constants are independent of all problem parameters other than the desired probability of success. For a wide range of parameters, these properties are informationtheoretically order-optimal. In addition, our SHO-FA algorithm works over fairly general ensembles of sparse random matrices, and is robust to random noise and (random) approximate sparsity for a large range of k. In particular, suppose the measured vector equals A(x + z) + e, where z and e correspond to the source tail and measurement noise, respectively. Under reasonable statistical assumptions on z and e, our decoding algorithm reconstructs x with an estimation error of O(||z||2 + ||e||2). The SHO-FA algorithm works with high probability over A, z, and e, and still requires only O(k) steps and O(k) measurements over O(log(n))-bit numbers. This is in contrast to most existing algorithms that focus on the worst case z model, where it is known that Ω(k log(n/k)) measurements over O(log(n))-bit numbers are necessary. Our algorithm has good empirical performance, as validated by simulations.

Compressive phase retrieval algorithms attempt to reconstruct a “sparse high-dimensional vector” from its “low-dimensional intensity measurements”. Suppose x is any length-n input vector over ℂ with exactly k non-zero entries, and A is an m × n (k1x|, ..., |Amx|) (corresponding to component-wise absolute values of the linear measurement Ax) - here Ai's correspond to the rows of the measurement matrix A. In this work, we present a class of measurement matrices A, and a corresponding decoding algorithm that we call SUPER, which can reconstruct x up to a global phase from intensity measurements. The SUPER algorithm is the first to simultaneously have the following properties: (a) it requires only O(k) (order-optimal) measurements, (b) the computational complexity of decoding is O(k log k) (near order-optimal) arithmetic operations, (c) it succeeds with high probability over the design of A. Our results hold for all k ∈ {1, 2, ..., n}.

We formulate and analyze a stochastic threshold group testing problem motivated by biological applications. Here a set of n items contains a subset of d ≪ C n defective items. Subsets (pools) of the n items are tested. The test outcomes are negative if the number of defectives in a pool is no larger than l; positive if the pool contains more than u defectives, and stochastic (negative/positive with some probability) if the number of defectives in the pool is in the interval [l, u]. The goal of our stochastic threshold group testing scheme is to identify the set of d defective items via a “small” number of such tests with high probability. In the regime that l = o(d) we present schemes that are computationally feasible to design and implement, and require near-optimal number of tests. Our schemes are robust to a variety of models for probabilistic threshold group testing.