  This paper studies sequential methods for recovery of sparse signals in high
dimensions. When compared to fixed sample size procedures, in the sparse
setting, sequential methods can result in a large reduction in the number of
samples needed for reliable signal support recovery. Starting with a lower
bound, we show any coordinate-wise sequential sampling procedure fails in the
high dimensional limit provided the average number of measurements per
dimension is less then log s/D(P_0||P_1) where s is the level of sparsity and
D(P_0||P_1) the Kullback-Leibler divergence between the underlying
distributions. A series of Sequential Probability Ratio Tests (SPRT) which
require complete knowledge of the underlying distributions is shown to achieve
this bound. Motivated by real world experiments and recent work in adaptive
sensing, we introduce a simple procedure termed Sequential Thresholding which
can be implemented when the underlying testing problem satisfies a monotone
likelihood ratio assumption. Sequential Thresholding guarantees exact support
recovery provided the average number of measurements per dimension grows faster
than log s/ D(P_0||P_1), achieving the lower bound. For comparison, we show any
non-sequential procedure fails provided the number of measurements grows at a
rate less than log n/D(P_1||P_0), where n is the total dimension of the
problem.
