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. In this paper, we address the general case of directed graphs and we propose an alternative approach that builds the graph Fourier basis as the set of orthonormal vectors that minimize a continuous extension of the graph cut size, known as the Lovász extension. To cope with the nonconvexity of the problem, we propose two alternative iterative optimization methods, properly devised for handling orthogonality constraints. Finally, we extend the method to minimize a continuous relaxation of the balanced cut size. The formulated problem is again nonconvex, and we propose an efficient solution method based on an explicit-implicit gradient algorithm.

On the graph Fourier transform for directed graphs

Sardellitti, Stefania;
2017-01-01

Abstract

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. In this paper, we address the general case of directed graphs and we propose an alternative approach that builds the graph Fourier basis as the set of orthonormal vectors that minimize a continuous extension of the graph cut size, known as the Lovász extension. To cope with the nonconvexity of the problem, we propose two alternative iterative optimization methods, properly devised for handling orthogonality constraints. Finally, we extend the method to minimize a continuous relaxation of the balanced cut size. The formulated problem is again nonconvex, and we propose an efficient solution method based on an explicit-implicit gradient algorithm.
2017
Clustering
graph Fourier transform
graph signal processing
total variation
Signal Processing
Electrical and Electronic Engineering
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12606/7029
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 95
social impact