Structural Identifiability in Low-Rank Matrix Factorization
In many signal processing and data mining applications, we need to approximate a given matrix Y with a low-rank product Ya parts per thousand AX. Both matrices A and X are to be determined, but we assume that from the specifics of the application we have an important piece of a-priori knowledge: A must have zeros at certain positions. In general, different AX factorizations approximate a given Y equally well, so a fundamental question is whether the known zero pattern of A contributes to the uniqueness of the factorization. Using the notion of structural rank, we present a combinatorial characterization of uniqueness up to diagonal scaling (subject to a mild non-degeneracy condition on the factors), called structural identifiability of the model. Next, we define an optimization problem that arises in the need for efficient experimental design. In this context, Y contains sensor measurements over several time samples, X contains source signals over time samples and A contains the source-sensor mixing coefficients. Our task is to monitor the signal sources with the cheapest subset of sensors, while maintaining structural identifiability. Firstly, we show that this problem is NP-hard. Secondly, we present a mixed integer linear program for its exact solution together with two practical incremental approaches. We also propose a greedy approximation algorithm. Finally, we perform computational experiments on simulated problem instances of various sizes.
low-rank matrix factorization structural rank approximation algorithm bipartite matching computational complexity integer programming