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

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.