Fast spectral approximation of structured graphs with applications to graph filtering

Mario Coutino, Sundeep Prabhakar Chepuri, Takanori Maehara, Geert Leus

Research output: Contribution to journalArticleScientificpeer-review

8 Downloads (Pure)

Abstract

To analyze and synthesize signals on networks or graphs, Fourier theory has been extended to irregular domains, leading to a so-called graph Fourier transform. Unfortunately, different from the traditional Fourier transform, each graph exhibits a different graph Fourier transform. Therefore to analyze the graph-frequency domain properties of a graph signal, the graph Fourier modes and graph frequencies must be computed for the graph under study. Although to find these graph frequencies and modes, a computationally expensive, or even prohibitive, eigendecomposition of the graph is required, there exist families of graphs that have properties that could be exploited for an approximate fast graph spectrum computation. In this work, we aim to identify these families and to provide a divide-and-conquer approach for computing an approximate spectral decomposition of the graph. Using the same decomposition, results on reducing the complexity of graph filtering are derived. These results provide an attempt to leverage the underlying topological properties of graphs in order to devise general computational models for graph signal processing.

Original languageEnglish
Article number214
Pages (from-to)1-25
Number of pages25
JournalAlgorithms
Volume13
Issue number9
DOIs
Publication statusPublished - 2020

Keywords

  • Approximate graph Fourier transform
  • Divide-and-conquer
  • Graph Fourier transform
  • Graph signal processing

Fingerprint

Dive into the research topics of 'Fast spectral approximation of structured graphs with applications to graph filtering'. Together they form a unique fingerprint.

Cite this