A pinboard by
Santiago Segarra

Postdoc, Massachusetts Institute of Technology


Extending classical signal processing to signals defined on graphs

As humans we have mastered the effective processing of classical signals, namely, speech, image, and video. However, in the past few years, we are observing more and more network data, that is, data associated to the agents of a network. For example, you can think of an opinion profile of the members of a social network as being a signal defined on top of the graph that represents the network.

The philosophy of graph signal processing is to generalize traditional processing tools -- such as filtering, denoising, sampling and reconstruction -- and extend them to the graph domain. This would enhance our capabilities to treat modern signals that reside in some kind of network, such as, denoising brain signals, compressing social opinions, or filtering temperature measurements of a wireless sensor network.


The Dual Graph Shift Operator: Identifying the Support of the Frequency Domain

Abstract: Contemporary data is often supported by an irregular structure, which can be conveniently captured by a graph. Accounting for this graph support is crucial to analyze the data, leading to an area known as graph signal processing (GSP). The two most important tools in GSP are the graph shift operator (GSO), which is a sparse matrix accounting for the topology of the graph, and the graph Fourier transform (GFT), which maps graph signals into a frequency domain spanned by a number of graph-related Fourier-like basis vectors. This alternative representation of a graph signal is denominated the graph frequency signal. Several attempts have been undertaken in order to interpret the support of this graph frequency signal, but they all resulted in a one-dimensional interpretation. However, if the support of the original signal is captured by a graph, why would the graph frequency signal have a simple one-dimensional support? That is why, for the first time, we propose an irregular support for the graph frequency signal, which we coin the dual graph. The dual GSO leads to a better interpretation of the graph frequency signal and its domain, helps to understand how the different graph frequencies are related and clustered, enables the development of better graph filters and filter banks, and facilitates the generalization of classical SP results to the graph domain.

Pub.: 24 May '17, Pinned: 25 Aug '17

Distributed Linear Network Operators using Graph Filters

Abstract: 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 (known as filter coefficients) 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. Perfect and approximate implementation of network operators is also studied for node-variant graph filters. 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. Finally, we present additional numerical experiments comparing the performance of node-invariant and node-variant filters when approximating arbitrary linear network operators.

Pub.: 13 Oct '15, Pinned: 25 Aug '17