Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison

David I. Shuman

A major line of work in graph signal processing [2] during the past 10 years has been to design new transform methods that account for the underlying graph structure to identify and exploit structure in data residing on a connected, weighted, undirected graph. The most common approach is to construct a dictionary of atoms (building block signals) and represent the graph signal of interest as a linear combination of these atoms. Such representations enable visual analysis of data, statistical analysis of data, and data compression, and they can also be leveraged as regularizers in machine learning and ill-posed inverse problems, such as inpainting, denoising, and classification.

In general, the desirable properties when designing dictionaries for graph signals include the following:

  1. The atoms have an interpretable form that accounts for the underlying graph structure so that the inner products between a graph signal and each atom are informative.

  2. The dictionary comprises an orthonormal basis or tight frame for the signal space, so, that the contribution of each atom can be computed via an inner product with the graph signal and the energy of the graph signal is equal to a constant multiple of the energy of the transform coefficients.

  3. It is numerically efficient to apply the dictionary analysis and synthesis operators (forward and inverse transforms).

  4. Signals of certain mathematical classes can be represented exactly or approximately as sparse linear combinations of a subset of the dictionary atoms.

By our count, approximately 100 conference and journal articles written during the past decade have introduced new dictionaries for graph signals. These include designs for analytic dictionaries that are adapted to the graph structure but not any specific training data, as well as techniques for learning dictionaries from training data. Broad classes of dictionaries include graph Fourier transforms (GFTs); windowed GFTs; vertex domain designs, including spatial wavelets, hierarchical trees, lifting transforms, and top-down approaches; diffusion-based designs; spectral domain designs; pyramid transforms; and generalized filter banks (see [1] for references). Despite, or perhaps because of, the number of new graph signal dictionary designs, it remains difficult to identify which dictionary might be best suited for a specific task and to understand subtle qualitative tradeoffs when specifying the parameters of a given dictionary construction.

SPS on Twitter

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar