A matching-related property of bipartite graphs with applications in signal processing and bioinformatics
Speaker: Epameinondas Fritzilas
Date: 27 August 2009 Time: 16:00-18:00
Location: "Mediterranean Studies" Seminar Room, FORTH, Heraklion, Crete
Host: I. Tollis


In many signal processing applications we need to write a given matrix Y as a product Y=AX. Both matrices A and X have to be determined and we assume that from the specifics of the application we can derive some constraints for them. We consider a class of constraints which arise in applications that involve a bipartite network of signal sources and sensors. In this context, Y contains sensor measurements over time, X contains source signals over time and A contains the source-sensor mixing coefficients. We assume that the connectivity of the network is fixed and known a-priori. Does this contribute anything to the uniqueness of the factorization? There are two applications from bioinformatics that can be modeled in this framework: Processing of microarray measurements with non-specific probes and quantification of transcription factor activities in simple regulatory networks.
We first present a characterization of uniqueness up to diagonal scaling in the factorization Y=AX. This characterization is combinatorial, in the sense that it depends only on the structure of the bipartite source-sensor graph; more specifically, on the existence of perfect matchings in certain subgraphs. Then, we investigate two optimization problems that arise in practice. We sketch their NP-hardness and develop integer linear programs for their exact solution. Moreover, for one of them we present a greedy algorithm that guarantees a logarithmic approximation ratio.
Finally, we turn to a question that arises from the need to model uncertainty in the network structure. Given a "good" graph, how robust is it with respect to edge modifications? We present a polynomial-time algorithm for the computation of robustness.


to be announced

© Copyright 2007 FOUNDATION FOR RESEARCH & TECHNOLOGY - HELLAS, All rights reserved.