Sequential Testing for Sparse Recovery
From MaRDI portal
Publication:2979175
DOI10.1109/TIT.2014.2363846zbMATH Open1359.94382arXiv1212.1801OpenAlexW2963852296MaRDI QIDQ2979175FDOQ2979175
Authors: Matthew L. Malloy, Robert D. Nowak 
Publication date: 2 May 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1212.1801
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)
Cited In (5)
- Are there needles in a moving haystack? Adaptive sensing for detection of dynamically evolving signals
- Asymptotically optimal multistage tests for non-i.i.d. data
- Asymptotically optimal sequential multiple testing with asynchronous decisions
- Joint sequential detection and isolation for dependent data streams
- Asymptotically optimal sequential FDR and pFDR control with (or without) prior information on the number of signals
This page was built for publication: Sequential Testing for Sparse Recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979175)
