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.
Also closely related to the work here are the lower bounds of @cite_9 . The lower bounds presented in @cite_9 are stronger in that they are not restricted to the assumption, but weaker in that they are terms of the expected set difference and restricted to the Gaussian setting. The results of @cite_9 were published after the initial work in @cite_14 @cite_11 .
@cite_9 @cite_14 @cite_11
2170707542 2008786239
This paper gives a precise characterization of the fundamental limits of adaptive sensing for diverse estimation and testing problems concerning sparse signals. We consider in particular the setting introduced in (IEEE Trans. Inform. Theory 57 (2011) 6222–6235) and show necessary conditions on the minimum signal magnitude for both detection and estimation: if x ? R^n is a sparse vector with s non-zero components then it can be reliably detected in noise provided the magnitude of the non-zero components exceeds v 2 s . Furthermore, the signal support can be exactly identified provided the minimum magnitude exceedsv 2 log s . Notably there is no dependence on n , the extrinsic signal dimension. These results show that the adaptive sensing methodologies proposed previously in the literature are essentially optimal, and cannot be substantially improved. In addition, these results provide further insights on the limits of adaptive compressive sensing. This paper presents results pertaining to sequential methods for support recovery of sparse signals in noise. Specifically, we show that any sequential measurement procedure fails provided the average number of measurements per dimension grows slower then log s D(f0||f1) where s is the level of sparsity, and D(f0||f1) the Kullback-Leibler divergence between the underlying distributions. For comparison, we show any non-sequential procedure fails provided the number of measurements grows at a rate less than log n D(f1||f0), where n is the total dimension of the problem. Lastly, we show that a simple procedure termed sequential thresholding guarantees exact support recovery provided the average number of measurements per dimension grows faster than (log s + log log n) D(f0||f1), a mere additive factor more than the lower bound.