Discrete Signal Processing on Graphs: Frequency Analysis

Дискретная обработка сигналов на графах: частотный анализ
José M. F. Moura, Aliaksei Sandryhaila
2014-04-30

graph filtersgraph frequency analysisgraph signal processingsensor malfunction detectiontotal variation
Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high- and band-pass graph signals and graph filters. In traditional signal processing, these concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.
1
A graph-signal total variation is proposed that induces a frequency ordering and defines low-, high-, and band-pass graph signals and filters.
2
It identifies the lack of a natural frequency ordering as a central challenge for frequency analysis on generic graphs.
3
The approach is illustrated through applications in sensor malfunction detection and data classification.
4
The paper develops graph-filter design methods for achieving specified frequency responses.
5
The paper extends signal-processing concepts to signals defined on arbitrary graphs across physical, social, genetic, and biomolecular domains.

signals and datasets supported by arbitrary graphs (graph signals)

graph-frequency concepts and ordering, including total variation, low-, high-, and band-pass graph signals and filters, and their specified frequency responses

Publication Details
Publication Date
2014-04-30
Journal
Publisher
ISSN
Cited by
879
Access Type
Author Information
Authors
José M. F. Moura
Aliaksei Sandryhaila
Explore further
Open the scid.ai AI chat with a ready-made request: it will find papers on a similar topic and help build a literature review.
Find similar papers in the chat →
Make a presentation
100%