An Integer Programming Approach for Analyzing the Measurement Redundancy in Structured Linear Systems

A linear system whose model matrix is of size n×p is considered structured if some p row vectors in the model matrix are linearly dependent. Computing the degree of redundancy for structured linear systems is proven NP-hard. Previous computation strategy is divide-and-conquer, materialized in a bound-and-decompose algorithm, which, when the required conditions are satisfied, can compute the degree of redundancy on a set of much smaller submatrices instead of directly on the original model matrix. The limitation of this algorithm is that the current decomposition conditions are still restrictive and not always satisfied for many applications. We present a mixed integer programming (MIP) formulation of the redundancy degree problem and solve it using an existing MIP solver. Our numerical studies indicate that our approach outperforms the existing methods for many applications, especially when the decomposition conditions are not satisfied. The main contribution of the paper is that we tackle this challenging problem from a different angle and test a promising new approach. The resulting approach points to a path that can potentially solve the problem in its entirety.