Sensor Selection for Hypothesis Testing: Complexity and Greedy Algorithms
Sensor Selection for Hypothesis Testing: Complexity and Greedy Algorithms
复制标题
DOI：
10.1109/cdc40024.2019.9029235
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Lintao Ye;S. Sundaram
中科院分区：
文献类型：
--
作者：
Lintao Ye;S. Sundaram
在本文中，我们考虑用于（二元）假设检验的传感器选择。给定一对假设和一组用于测量（检测）假设下生成的信号的候选传感器，我们的目标是选择产生最佳信号检测性能的传感器子集（在预算约束下）。特别是，我们根据所选传感器的测量来考虑内曼-皮尔逊检测器。目标是最小化（或最大化）内曼-皮尔逊检测器的漏失概率（或检测概率），同时满足预算约束。我们首先证明 Neyman-Pearson 检测器问题的传感器选择是 NP 困难的。然后，当我们将错过概率的替代物视为优化指标（基于 Kullback-Leibler 距离）时，我们会描述解决传感器选择问题的贪婪算法的性能。通过利用子模块比的概念，我们为贪婪算法的性能提供了限制。
In this paper, we consider sensor selection for (binary) hypothesis testing. Given a pair of hypotheses and a set of candidate sensors to measure (detect) the signals generated under the hypotheses, we aim to select a subset of the sensors (under a budget constraint) that yields the optimal signal detection performance. In particular, we consider the Neyman-Pearson detector based on measurements of the chosen sensors. The goal is to minimize (resp., maximize) the miss probability (resp., detection probability) of the Neyman-Pearson detector, while satisfying the budget constraint. We first show that the sensor selection for the Neyman-Pearson detector problem is NP-hard. We then characterize the performance of greedy algorithms for solving the sensor selection problem when we consider a surrogate to the miss probability as an optimization metric, which is based on the Kullback-Leibler distance. By leveraging the notion of submodularity ratio, we provide a bound on the performance of greedy algorithms.