Structural Identifiability in Low-Rank Matriz Factorization
In many signal processing and data mining applications, we need to approximate a given matrix y of sensor measurements over several experiments by a low-rank product Y ≈ A ·X, where X contains source signals for each experiment, A contains source-sensor mixing coefficients, and both A and X are unknown. We assume that the only a-priori information available is that A must have zeros at certain positions; this constrains the source-sensor network connectivity pattern. In general, different AX factorizations approximate a given Y equally well, so a fundamental question is how the connectivity restricts the solution space. We present a combinatorial characterization of uniqueness up to diagonal scaling, called structural identifiability of the model, using the concept of structural rank from combinatorial matrix theory. Next, we define an optimization problem that arises in the need for efficient experimental design: to minimize the number of sensors while maintaining structural identifiability. We prove its NP-hardness and present a mixed integer linear programming framework with two cutting-plane approaches. Finally, we experimentally compare these approaches on simulated instances of various sizes.
Epameinondas Pritzilas Yasmin A. Rios-Solis Sven Rahmann
Faculty of Technology, Bielefeld University, Germany Faculty of Technology, Bielefeld University,Germany Computer Science 11, Technische Universitat Dortmund, Germany
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
140-148
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）