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.

# A matching-related property of bipartite graphs with applications in signal processing and bioinformatics

27.08.2009

Ομιλητής : Epameinondas Fritzilas

Ημερομηνία : 27.08.2009

Ώρα : 16:00-18:00

Μέρος : Aίθουσα Συναντήσεων "Μεσογειακών Σπουδών", ΙΤΕ, Ηράκλειο, Κρήτη

Φιλοξενείται από : Τόλλης Ιωάννης

Ημερομηνία : 27.08.2009

Ώρα : 16:00-18:00

Μέρος : Aίθουσα Συναντήσεων "Μεσογειακών Σπουδών", ΙΤΕ, Ηράκλειο, Κρήτη

Φιλοξενείται από : Τόλλης Ιωάννης

Περίληψη:

Σύντομο βιογραφικό ομιλητή:

to be announced