oa A Decomposition Algorithm to Measure Redundancy in Structured Linear Systems

Nowadays, inexpensive smart devices with multiple heterogeneous on-board sensors, networked through wired or wireless links and deployable in large numbers, are distributed throughout a physical process or in a physical environment, providing real-time, and dense spatio-temporal measurements and enabling surveillance and monitoring capability that could not be imagined a decade ago. Such a system-wide deployment of sensing devices is known as distributed sensing, and is considered one of the top ten emerging technologies that will change the world. Oil and gas pipeline systems, electrical grid systems, transportation systems, environmental and ecological monitoring systems, security systems, and advanced manufacturing systems are just a few examples among many others. Malfunction of any of the large-scale systems typically results in enormous economic loss and sometimes even endangers critical infrastructure and human lives. In any of these systems, the system state variables, whose values trigger various actions, are estimated based on the measurements gathered by the sensor system that monitors and controls the system of interest. Consequently, the reliability of these estimations is of utmost importance in economic and safe operation of these large-scale systems. In a linear sensor system, the sensor measurements are combined linear responses of the system states that need to be estimated. In the engineering literature, a linear model is often used to establish connection between sensor measurements in a system and the system's state variables through the sensor system's design matrix. In such systems, the sensor outputs y and the system states x are linked by the set of linear equations represented as y =  Ax+e, where y and e are n by 1 vectors, and x is a p by 1 vector. A is an n by p design matrix (n &gt;&gt; p) that models the linear measurement process. The matrix A is assumed to be of full column rank i.e., r(A) = p, where r(A) denotes the rank of A. The last term e is a random noise vector, which is assumed to be normally distributed with mean 0. In the context of estimation reliability, the redundancy degree in a sensor system is the minimum number of sensor failures (or measurement outliers) which can happen before the identifiability of any state is compromised. This number, called the degree of redundancy of the matrix A and denoted by d(A), is formally defined as d(A) =  {d-1: there esists A[-d] s.t. r(A[-d]) < r(A)}, where A[ − d] is the reduced matrix after deleting some d rows from the original matrix. The degree of redundancy of linear sensor systems is a measure of robustness of the system against sensor failures and hence the reliability of a linear sensor system. Finding the degree of redundancy for structured linear systems is proven to be NP-hard. Bound and decompose, mixed integer programming, l1-minimization methods have all been studied and compared in the literature. But none of these methods are suitable for finding the degree of redundancy in large scale sensor systems. We propose a decomposition approach which effectively disintegrates the problem into a reasonable number of smaller subproblems utilizing the structure inherent in such linear systems using concepts of duality and connectivity from matroid theory. We propose two different but related algorithms, both of which solves the same redundancy degree problem. While the former algorithm applies the decomposition technique over the vector matroid (the design matrix), the latter uses its corresponding dual matroid. These subproblems are then solved using mixed integer programming to evaluate the degree of redundancy for the whole sensor system. We report substantial computational gains (up to 10 times) for both these algorithms as compared to even the best known existing algorithms.