RECORD
Approximate Supermodularity of Kalman Filter Sensor Selection
Optimization and Control · Submitted 9 Dec 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In typical application scenarios, these certificates approach the (1-1/e) guarantee obtained for supermodular functions, thus demonstrating that no change to the original problem is needed to obtain guaranteed good performance.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
This work 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 (1-1/e)-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 logdet, despite the fact that minimizing the logdet 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 (1-1/e) guarantee obtained for supermodular functions, thus demonstrating that no change to the original problem is needed to obtain guaranteed good performance.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This work considers the problem of selecting sensors in a large scale system to minimize the error in estimating its states. | background 0.90 | 0.35 | 0.03 | asserted 0.91 |
| s1 | More specifically, the state estimation mean-square error(MSE) and worst-case error for Kalman filtering and smoothing. | background 0.86 | 0.18 | 0.03 | unclear 0.58 |
| s2 | Such selection problems are in general NP-hard, i.e., their solution can only be approximated in practice even for moderately large problems. | background 1.00 | 0.06 | 0.02 | asserted 0.99 |
| s3 | 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. | background 0.95 | 0.05 | 0.02 | asserted 0.83 |
| s4 | When this metric is supermodular, this solution is guaranteed to be (1-1/e)-optimal. | background 1.00 | 0.07 | 0.06 | asserted 1.00 |
| s5 | This is however not the case for the MSE or the worst-case error. | gap 0.54 | 0.14 | 0.03 | asserted 1.00 |
| s6 | This issue is often circumvented by using supermodular surrogates, such as the logdet, despite the fact that minimizing the logdet is not equivalent to minimizing the MSE. | background 0.94 | 0.06 | 0.04 | asserted 0.97 |
| s7 | 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. | contribution 0.92 | 0.92 | 0.34 | asserted 1.00 |
| s8 | In typical application scenarios, these certificates approach the (1-1/e) guarantee obtained for supermodular functions, thus demonstrating that no change to the original problem is needed to obtain guaranteed good performance. | interpretation 0.55 | 0.84 | 0.78 | asserted 0.97 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
This work 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 (1-1/e)-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 logdet, despite the fact that minimizing the logdet 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 (1-1/e) guarantee obtained for supermodular functions, thus demonstrating that no change to the original problem is needed to obtain guaranteed good performance.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.