# On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering

arXiv: https://arxiv.org/abs/2003.11951 · HTML: https://mlsanity.com/paper/2003.11951/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2020.

## Built on by (most cited first, 2 of 2)

- [Submodular Information Selection for Hypothesis Testing with Misclassification Penalties](https://mlsanity.com/paper/2405.10930/) (2024)
- [Robust Information Selection for Hypothesis Testing with Misclassification Penalties](https://mlsanity.com/paper/2502.14738/) (2025)

## Abstract (arXiv)

Given a linear dynamical system affected by stochastic noise, we consider the problem of selecting an optimal set of sensors (at design-time) to minimize the trace of the steady state a priori or a posteriori error covariance of the Kalman filter, subject to certain selection budget constraints. We show the fundamental result that there is no polynomial-time constant-factor approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity (or supermodularity) of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering. We then study the problem of attacking (i.e., removing) a set of installed sensors, under predefined attack budget constraints, to maximize the trace of the steady state a priori or a posteriori error covariance of the Kalman filter. Again, we show that there is no polynomial-time constant-factor approximation algorithm for this problem, and show specifically that greedy algorithms can perform arbitrarily poorly.