2017/11/06 by Lintao Ye, Ye, Lintao, Sandip Roy +3 · 1 citation
Computer Science · Engineering · #Distributed Sensor Networks and Detection Algorithms #FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Stability and Control of Uncertain Systems #Systems and Control (eess.SY) #Target Tracking and Data Fusion in Sensor Networks #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1711.01920
openalex publication_date 2017/11/06 · openalex created_date 2017/11/17 · openalex updated_date 2026/07/28
Given a linear dynamical system, we consider the problem of selecting (at design-time) an optimal set of sensors (subject to certain budget constraints) to minimize the trace of the steady state error covariance matrix of the Kalman filter. Previous work has shown that this problem is NP-hard for certain classes of systems and sensor costs; in this paper, we show that the problem remains NP-hard even for the special case where the system is stable and all sensor costs are identical. Furthermore, we show the stronger result that there is no constant-factor (polynomial-time) 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 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.