Randomized Greedy Sensor Selection: Leveraging Weak Submodularity
Randomized Greedy Sensor Selection: Leveraging Weak Submodularity
复制标题
DOI：
10.1109/tac.2020.2980924
复制
发表时间：
2021-01-01
影响因子：
6.8
通讯作者：
Topcu, Ufuk
中科院分区：
文献类型：
--
作者：
Hashemi, Abolfazl;Ghasemi, Mahsa;Topcu, Ufuk
我们研究了从在资源约束下运行的传感器网络收集的观测值估计随机过程的问题。当过程的动态和传感器观测是由状态空间模型描述的，并且资源是无限的，传统的卡尔曼滤波器提供最小均方误差（MMSE）估计。然而，在任何给定时间，对可用通信带宽和计算能力和/或功率的限制对网络节点的数量施加了限制，这些节点的观测值可用于计算估计。我们将选择传感器中信息量最大的子集的问题表述为一个在一致矩阵约束下的单调集函数最大化的组合问题。对于MMSE估计准则，我们证明了目标函数的最大元素曲率满足一定的上界约束，因此是弱子模。基于Mirzasoleiman等人关于子模最大化的工作，我们开发了一种高效的随机贪婪算法，用于传感器选择，并在此设置中建立了对估计器性能的保证。大量的仿真结果证明了随机贪心算法与最先进的贪心和半定规划松弛方法相比的有效性。
We study the problem of estimating a random process from the observations collected by a network of sensors that operate under resource constraints. When the dynamics of the process and sensor observations are described by a state-space model and the resource are unlimited, the conventional Kalman filter provides the minimum mean square error (MMSE) estimates. However, at any given time, restrictions on the available communications bandwidth and computational capabilities and/or power impose a limitation on the number of network nodes, whose observations can be used to compute the estimates. We formulate the problem of selecting the most informative subset of the sensors as a combinatorial problem of maximizing a monotone set function under a uniform matroid constraint. For the MMSE estimation criterion, we show that the maximum elementwise curvature of the objective function satisfies a certain upper-bound constraint and is, therefore, weak submodular. Building upon the work of Mirzasoleiman et al. on submodular maximization, we develop an efficient randomized greedy algorithm for sensor selection and establish guarantees on the estimator's performance in this setting. Extensive simulation results demonstrate the efficacy of the randomized greedy algorithm compared to state-of-the-art greedy and semidefinite programming relaxation methods.