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.

Graph Fourier transform for directed graphs based on Lovász extension of min-cut / Sardellitti, Stefania; Barbarossa, Sergio; Di Lorenzo, Paolo. - ELETTRONICO. - (2017), pp. 3894-3898. ((Intervento presentato al convegno 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 tenutosi a New Orleans; United States nel 2017 [10.1109/ICASSP.2017.7952886].

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

Sardellitti, Stefania;Barbarossa, Sergio;Di Lorenzo, Paolo
2017

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.
9781509041176
File allegati a questo prodotto
File Dimensione Formato  
Sardellitti_Graph_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 3.42 MB
Formato Adobe PDF
3.42 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/11573/1064874
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact