Graph Fourier Transform for directed graphs based on Lovász extension of min-cut

Abstract

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. To cope with the non-convexity of the problem, we exploit a recently developed method devised for handling orthogonality constraints, with provable convergence properties.