Back to Search
Start Over
Sequential Testing for Sparse Recovery.
- Source :
-
IEEE Transactions on Information Theory . Dec2014, Vol. 60 Issue 12, p7862-7873. 12p. - Publication Year :
- 2014
-
Abstract
- This paper studies sequential methods for recovery of sparse signals in high dimensions. When compared with 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(P0||P1) , where s is the level of sparsity and D(P_{0}||P_{1}) is the Kullback–Leibler divergence between the underlying distributions. A series of sequential probability ratio tests, 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(P0||P1) , achieving the lower bound. For comparison, we show any nonsequential 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 60
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 100027670
- Full Text :
- https://doi.org/10.1109/TIT.2014.2363846