Observability Robustness Under Sensor Failures: A Computational Perspective

This article studies the robustness of observability of a linear time-invariant system under sensor failures from a computational perspective. Our aim is to determine the minimum number of sensors that, if removed, would render the system unobservable, and to determine the minimum number of state variables that need to be shielded from direct measurement by existing sensors to destroy system observability, both in numerical and structural (or structured) system models. The first problem is closely related to the capability of reconstructing a system's state uniquely under adversarial sensor attacks, while the second one has potential for the privacy-preserving design of dynamic systems. Both problems are in the opposite direction of the well-studied minimal controllability problems. We prove that all of these problems are NP-hard for both numerical and structural systems, even restricted to some special cases. Nevertheless, for the first problem, under a common practical assumption that the eigenvalue geometric multiplicities of numerical systems or the matching deficiencies of structural systems are bounded by a constant, we present a method to obtain the optimal solutions by traversing a subset of the feasible solutions, leveraging the rank-one update property of rank functions. Our method has polynomial time complexity in the system dimensions and the number of sensors under the addressed condition.