Approximate fast graph Fourier transforms via multi-layer sparse approximations

Luc Le Magoarou 1 Rémi Gribonval 1 Nicolas Tremblay 2, 3
1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA_D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
3 GIPSA-CICS - CICS
GIPSA-DIS - Département Images et Signal
Abstract : The Fast Fourier Transform (FFT) is an algorithm of paramount importance in signal processing as it allows to apply the Fourier transform in O(n log n) instead of O(n 2) arithmetic operations. Graph Signal Processing (GSP) is a recent research domain that generalizes classical signal processing tools, such as the Fourier transform, to situations where the signal domain is given by any arbitrary graph instead of a regular grid. Today, there is no method to rapidly apply graph Fourier transforms. We propose in this paper a method to obtain approximate graph Fourier transforms that can be applied rapidly and stored efficiently. It is based on a greedy approximate diagonalization of the graph Laplacian matrix, carried out using a modified version of the famous Jacobi eigenvalues algorithm. The method is described and analyzed in detail, and then applied to both synthetic and real graphs, showing its potential.
Type de document :
Article dans une revue
IEEE transactions on Signal and Information Processing over Networks, IEEE, 2017, pp.15. 〈10.1109/TSIPN.2017.2710619〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01416110
Contributeur : Luc Le Magoarou <>
Soumis le : vendredi 16 juin 2017 - 11:43:23
Dernière modification le : mardi 5 septembre 2017 - 09:51:06

Fichiers

FFT_graph_hal.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Citation

Luc Le Magoarou, Rémi Gribonval, Nicolas Tremblay. Approximate fast graph Fourier transforms via multi-layer sparse approximations. IEEE transactions on Signal and Information Processing over Networks, IEEE, 2017, pp.15. 〈10.1109/TSIPN.2017.2710619〉. 〈hal-01416110v3〉

Partager

Métriques

Consultations de
la notice

254

Téléchargements du document

93