Approximate Supermodularity of Kalman Filter Sensor Selection
Approximate Supermodularity of Kalman Filter Sensor Selection
复制标题
卡尔曼滤波器传感器选择的近似超模性
DOI：
--
复制
发表时间：
2019
影响因子：
6.8
通讯作者：
Alejandro Ribeiro
中科院分区：
文献类型：
--
作者：
Luiz F. O. Chamon;George Pappas;Alejandro Ribeiro
本文考虑了大系统中传感器的选择问题，以使状态估计误差最小，特别是状态估计均方误差（MSE）和卡尔曼滤波和平滑的最坏情况误差最小。这样的选择问题通常是NP难的，即，它们的解在实践中甚至对于中等大的问题也只能是近似的。由于其低复杂性和迭代性质，贪婪算法通常用于通过每次选择一个传感器来获得这些近似值，在每一步选择使估计性能度量最小化的传感器。当这个度量是超模时，这个解保证是<inline-formula><tex-math notation="LaTeX">$（1-1/e）$</tex-math></inline-formula>-最优的。然而，对于MSE或最坏情况错误，情况并非如此。这个问题通常可以通过使用超模块化的代理来规避，比如<inline-formula><tex-math notation="LaTeX">$log det$</tex-math></inline-formula>，尽管最小化<inline-formula><tex-math notation="LaTeX">$log det$</tex-math></inline-formula>并不等同于最小化MSE。在这里，这个问题是通过利用近似超模块化的概念，以获得接近最优证书的greetings最小化的估计均方和最坏情况下的错误。在典型的应用场景中，这些证书接近于超模函数的<inline-formula><tex-math notation="LaTeX">$（1-1/e）$</tex-math></inline-formula>保证，从而证明了不需要改变原始问题就可以获得保证的良好性能。
This article considers the problem of selecting sensors in a large-scale system to minimize the error in estimating its states, more specifically, the state estimation mean-square error (MSE) and worst-case error for Kalman filtering and smoothing. Such selection problems are in general NP-hard, i.e., their solution can only be approximated in practice even for moderately large problems. Due to its low complexity and iterative nature, greedy algorithms are often used to obtain these approximations by selecting one sensor at a time choosing at each step the one that minimizes the estimation performance metric. When this metric is supermodular, this solution is guaranteed to be <inline-formula><tex-math notation="LaTeX">$(1-1/e)$</tex-math></inline-formula>-optimal. This is, however, not the case for the MSE or the worst-case error. This issue is often circumvented by using supermodular surrogates, such as the <inline-formula><tex-math notation="LaTeX">$log det$</tex-math></inline-formula>, despite the fact that minimizing the <inline-formula><tex-math notation="LaTeX">$log det$</tex-math></inline-formula> is not equivalent to minimizing the MSE. Here, this issue is addressed by leveraging the concept of approximate supermodularity to derive near-optimality certificates for greedily minimizing the estimation mean-square and worst-case error. In typical application scenarios, these certificates approach the <inline-formula><tex-math notation="LaTeX">$(1-1/e)$</tex-math></inline-formula> guarantee obtained for supermodular functions, thus demonstrating that no change to the original problem is needed to obtain guaranteed good performance.