The mean square error in Kalman filtering sensor selection is approximately supermodular
The mean square error in Kalman filtering sensor selection is approximately supermodular
复制标题
卡尔曼滤波传感器选择中的均方误差近似为超模
DOI：
10.1109/cdc.2017.8263688
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Alejandro Ribeiro
中科院分区：
文献类型：
--
作者：
Luiz F. O. Chamon;George Pappas;Alejandro Ribeiro
研究了大系统中传感器的选择问题，以最小化状态估计均方误差。更具体地说，它利用近似超模块化的概念，在卡尔曼滤波的背景下，这个问题的贪婪的解决方案，以获得近最优证书。它还表明，在典型的应用场景中，这些证书接近典型的1/e保证。这些性能界限是重要的，因为传感器选择问题一般是NP-难的。因此，他们的解决方案只能近似在实践中，即使是中等规模的问题。导出这些近似的一种常见方法是通过凸松弛。然而，这些都没有性能保证。另一种方法使用贪婪搜索，尽管在这种情况下典型的保证也不成立，因为MSE既不是子模的也不是超模的。这个问题通常通过使用替代超模品质因数来解决，例如log det。不幸的是，这并不等同于最小化MSE。这项工作表明，不需要改变原来的问题，以获得性能保证。
This work considers the problem of selecting sensors in large scale system to minimize the state estimation mean-square error (MSE). More specifically, it leverages the concept of approximate supermodularity to derive near-optimality certificates for greedy solutions of this problem in the context of Kalman filtering. It also shows that in typical application scenarios, these certificates approach the typical 1/e guarantee. These performance bounds are important because sensor selection problems are in general NP-hard. Hence, their solution can only be approximated in practice even for moderately large problems. A common way of deriving these approximations is by means of convex relaxations. These, however, come with no performance guarantee. Another approach uses greedy search, although also in this case typical guarantees do not hold since the MSE is neither submodular nor supermodular. This issue is commonly addressed by using a surrogate supermodular figure of merit, such as the log det. Unfortunately, this is not equivalent to minimizing the MSE. This work demonstrates that no change to the original problem is needed to obtain performance guarantees.