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

  • DEADLINE EXTENDED: The 2023 IEEE International Workshop on Machine Learning for Signal Processing is now accepting… https://t.co/NLH2u19a3y
  • ONE MONTH OUT! We are celebrating the inaugural SPS Day on 2 June, honoring the date the Society was established in… https://t.co/V6Z3wKGK1O
  • The new SPS Scholarship Program welcomes applications from students interested in pursuing signal processing educat… https://t.co/0aYPMDSWDj
  • CALL FOR PAPERS: The IEEE Journal of Selected Topics in Signal Processing is now seeking submissions for a Special… https://t.co/NPCGrSjQbh
  • Test your knowledge of signal processing history with our April trivia! Our 75th anniversary celebration continues:… https://t.co/4xal7voFER

IEEE SPS Educational Resources

IEEE SPS Resource Center

IEEE SPS YouTube Channel