University of Minnesota
University Relations
http://www.umn.edu/urelate
612-624-6868
myU OneStop


Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Monday, October 19, 2015

DTC Seminar Series

Distributed Linear Network Operators using Graph Filters

by

Antonio Marqués
Universidad Rey Juan Carlos
Madrid, Spain

Monday, October 19, 2015
4:30 p.m. reception
5:00 p.m. seminar

401/402 Walter Library

Antonio Marqués

A plethora of graph-supported signals exist in different fields, including gene-expression patterns defined on top of gene networks, the spread of epidemics over a social network, and the congestion level at the nodes of a telecommunication network, to name a few. Transversal to the particular application, we must address the question of how to redesign traditional tools originally conceived to study and process signals defined on regular domains and extend them to the more complex graph domain.

In this talk, we study the design of graph filters to implement arbitrary linear transformations between graph signals. Graph filters can be represented by matrix polynomials of the graph-shift operator, which captures the structure of the graph and is assumed to be given. Thus, graph-filter design consists in choosing the coefficients of these polynomials to resemble desired linear transformations. Due to the local structure of the graph-shift operator, graph filters can be implemented distributedly across nodes, making them suitable for networked settings. We determine spectral conditions under which a specific linear transformation can be implemented perfectly using graph filters. Furthermore, for the cases where perfect implementation is infeasible, the design of optimal approximations for different error metrics is analyzed. We introduce the notion of a node-variant graph filter, which allows the simultaneous implementation of multiple (regular) graph filters in different nodes of the graph. This additional flexibility enables the design of more general operators without undermining the locality in implementation.

Finally, we demonstrate the practical relevance of the developed framework by studying in detail the application of graph filters to the problems of finite-time consensus and analog network coding.