Sequential Testing for Sparse Recovery
Sequential Testing for Sparse Recovery
复制标题
DOI：
10.1109/tit.2014.2363846
复制
发表时间：
2012-12
影响因子：
2.5
通讯作者：
Matthew Malloy;R. Nowak
中科院分区：
文献类型：
--
作者：
Matthew Malloy;R. Nowak
本文研究了高维稀疏信号恢复的序贯方法。与固定样本量程序相比，在稀疏环境中，顺序方法可以大幅减少可靠信号支持恢复所需的样本数量。从一个下限开始，我们证明了任何坐标方式的顺序抽样程序在高维限制下失败，只要每个维度的平均测量数小于log（s）/D（P0|| P1），其中s是稀疏性水平，D（P0|| P1）是基础分布之间的Kullback-Leibler散度。一系列的顺序概率比测试，这需要完整的知识的基础分布，以实现这一界限。出于现实世界的实验和最近的工作在自适应传感，我们介绍了一个简单的程序，称为顺序阈值，它可以实现时，底层的测试问题满足单调似然比假设。如果每个维度的平均测量数增长速度快于log（s）/D（P0），则顺序阈值处理可确保精确的支持度恢复||P1），达到下限。为了进行比较，我们显示了任何非顺序过程失败，只要测量数量以小于log（n）/D（P1）的速率增长||P0），其中n是问题的总维数。
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(P0||P1) 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(P1||P0), where n is the total dimension of the problem.