Ricerc@Sapienza

A key tool to analyze signals defined over a graph is the so called Graph Fourier Transform (GFT). Alternative definitions of GFT have been proposed, based on the eigen-decomposition of either the graph Laplacian or adjacency matrix. In this paper, we introduce an alternative approach, valid for the general case of directed graphs, that builds the graph Fourier basis as the set of orthonormal vectors that minimize a well-defined continuous extension of the graph cut size, known as Lovász extension.

The analysis of signals defined over a graph is relevant in many applications, such as social and economic networks, big data or biological networks, and so on. A key tool for analyzing these signals is the so-called graph Fourier transform (GFT). Alternative definitions of GFT have been suggested in the literature, based on the eigen-decomposition of either the graph Laplacian or adjacency matrix.