PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Frames

David I Shuman, Christoph Wiesmeyr, Nicki Holighaus, Pierre Vandergheynst

arXiv:1311.0897v1math.FAcs.ITcs.SI

TL;DR

The paper addresses the limited discriminatory power of graph filters adapted only to spectral length by designing filters adapted to the distribution of Laplacian eigenvalues. It warps uniformly translated kernels using an approximation to the cumulative spectral density, producing tight, computationally efficient vertex-frequency and graph wavelet frames with improved discrimination between graph signals.

  • Problem

    Previous graph wavelet filters are adapted to spectrum length rather than the specific Laplacian eigenvalue distribution, limiting discriminatory power for irregular spectra.

  • Method

    The method warps uniformly translated spectral kernels with a function approximating the graph Laplacian’s cumulative spectral density to construct tight frames.

  • Results

    The construction yields computationally efficient, spectrum-adapted tight vertex-frequency and graph wavelet frames with better ability to discriminate between graph signals.

  • Takeaways & Limitations

    Spectrum adaptation preserves tight-frame and efficient-implementation properties while tailoring dictionary atoms to the specific graph spectrum.

Abstract

from arXiv · show

We consider the problem of designing spectral graph filters for the construction of dictionaries of atoms that can be used to efficiently represent signals residing on weighted graphs. While the filters used in previous spectral graph wavelet constructions are only adapted to the length of the spectrum, the filters proposed in this paper are adapted to the distribution of graph Laplacian eigenvalues, and therefore lead to atoms with better discriminatory power. Our approach is to first characterize a family of systems of uniformly translated kernels in the graph spectral domain that give rise to tight frames of atoms generated via generalized translation on the graph. We then warp the uniform translates with a function that approximates the cumulative spectral density function of the graph Laplacian eigenvalues. We use this approach to construct computationally efficient, spectrum-adapted, tight vertex-frequency and graph wavelet frames. We give numerous examples of the resulting spectrum-adapted graph filters, and also present an illustrative example of vertex-frequency analysis using the proposed construction.

I. INTRODUCTION

The paper designs graph-signal dictionaries whose spectral filters adapt to the specific Laplacian spectrum while retaining tightness and efficient implementation. This addresses limited discriminatory power from filters adapted only to spectral length and avoids the full eigendecomposition required by some spectrum-adapted alternatives.

  • I. INTRODUCTION: Tight frames can improve numerical stability for noisy reconstruction, accelerate some computations, and support energy-density interpretations of spectrograms.These are general benefits cited for tight frames in the paper’s background discussion.
  • I. INTRODUCTION: For irregularly spaced Laplacian eigenvalues, conventional graph wavelets can be highly correlated across nearby vertices and scales, reducing discriminatory power.Earlier kernels are adapted to the maximum eigenvalue rather than the specific eigenvalue distribution.
  • I. INTRODUCTION: Spectrum-adapted filters produce tight dictionaries with fast Chebyshev-based implementation and do not require a full graph-Laplacian eigendecomposition.The construction adapts filters to the entire spectrum while preserving tight-frame structure and computational efficiency.
  • I. INTRODUCTION: The method warps uniformly translated spectral kernels using a function approximating the graph Laplacian’s cumulative spectral density.This adapts the kernels to the entire spectrum rather than only its length.
  • I. INTRODUCTION: The resulting construction yields spectrum-adapted vertex-frequency frames and graph wavelet frames for representing signals on weighted graphs.The vertex-frequency frames generalize time-frequency analysis to the graph setting.
  • I. INTRODUCTION: The paper also introduces a way to generate smooth uniform translates whose squared magnitudes sum to a constant and an approximation method for empirical spectral cumulative distributions.These additional contributions use window construction and spectrum-slicing ideas, respectively.

II. NOTATION AND BACKGROUND

The paper defines graph spectral filtering, generalized-translation dictionaries, and a sufficient condition for tight frames. It then constructs uniformly translated kernels whose squared magnitudes sum to a constant.

  • Notation and background: Graph spectral filters multiply graph Fourier coefficients, and inverse transformation returns the filtered signal in the vertex domain.
  • Notation and background: Dictionaries contain M·N atoms generated by applying generalized translations to M graph spectral filters at every vertex.Translation localizes each atom around its center vertex, while filter smoothness controls spatial spread.
  • Notation and background: Earlier spectral graph wavelet filters are adapted mainly to spectrum length, motivating filters that account for graph-specific spectral structure.
  • Uniform translates: If the aggregate squared filter magnitude G(λ) is constant on the graph spectrum, generalized translations of the filters form a tight frame.
  • Uniform translates: With γ=λmax, the translated filter banks cover the graph spectrum while maintaining constant G(λ), so the resulting dictionaries are tight frames.Increasing R at fixed M increases filter overlap.

IV. WARPING

The warping framework transforms uniform spectral translates into filters adapted to alternative spectral scalings. Because warping preserves the aggregate squared magnitudes, tight-frame structure is retained.

  • Warping: Warped filters are defined by composing each uniform filter with a nondecreasing warping function, c g_m(λ)=c g_Um(ω(λ)).The warping function rescales the spectrum for application-specific designs.
  • Warping: Logarithmic warping yields graph wavelet frames adapted to spectrum length, while eigenvalue-distribution warping yields spectrum-adapted vertex-frequency frames.
  • Warping: The warping function should be nondecreasing and preferably smooth so that the warped filters remain smooth.
  • Warping: The squared magnitudes of warped filters sum to the same quantity as those of the original translates, supporting tight-frame construction.
  • Warping: When the warping maps the spectrum into the uniform-translate design range, the translated warped atoms remain a tight frame.

A. Example: Tight Graph Wavelet Frames

The paper applies logarithmic warping to construct tight graph wavelet frames from uniform translates. The resulting kernels have localized spectral support while retaining tightness.

  • A. Example: Tight Graph Wavelet Frames: The logarithmic construction follows earlier warped-Gabor ideas while providing a corresponding tight wavelet-frame method in the graph setting.
  • A. Example: Tight Graph Wavelet Frames: The construction uses M−1 wavelet kernels and one scaling kernel, beginning with ω(x)=log(x) and uniformly translated kernels.
  • A. Example: Tight Graph Wavelet Frames: For λmax=12, R=3, and M=8, the example compares Hann-based kernels with the SGWT and Meyer-like graph wavelet frames.
  • A. Example: Tight Graph Wavelet Frames: The log-warped graph wavelet system is a tight frame, and each wavelet kernel has support strictly smaller than the full graph spectrum.Its overlap and shape are closer to spline-based SGWT kernels than to the corresponding logarithmic support pattern.

V. SPECTRUM-ADAPTED FILTERS √

Uniformly translated spectral filters can allocate very different numbers of graph-Laplacian eigenvalues to frequency bands because they use only the spectrum's length. Spectrum-adapted warping incorporates eigenvalue locations to produce more informative, localized atoms.

  • Uniform spectral translations may place unequal numbers of eigenvalues in frequency bands, reducing their usefulness for information extraction.The problem is especially pronounced when Laplacian eigenvalues are irregularly spaced or concentrated in particular spectral regions.
  • For the comet graph, one uniform filter produces zero analysis coefficients for every vertex and signal, so it provides no additional information.
  • The proposed method estimates eigenvalue density and warps uniform spectral translates so their analysis coefficients better reflect the graph spectrum.The warped filters are formed through the graph-Laplacian matrix function and are designed to preserve smoothness and localization properties.
  • Full-spectrum knowledge is computationally prohibitive for extremely large graphs, motivating more efficient density-approximation methods.

A. Spectrum-Based Warping Functions

The paper constructs smooth spectrum-adapted filters by warping uniformly translated kernels with an interpolated cumulative spectral density. The method can use all or only a subset of eigenvalues, and spectrum slicing provides a scalable approximation when the full spectrum is unavailable.

  • A. Spectrum-Based Warping Functions: Warping uniformly translated kernels with the cumulative spectral density gives each filter support over a more balanced number of eigenvalues.The filters use c_gm(λ) = c_gU_m(ω(λ)); direct cumulative distributions are replaced by smooth interpolants for finite graphs.
  • A. Spectrum-Based Warping Functions: Monotonic cubic or linear interpolation produces smooth warping functions, with endpoints mapping [0, λmax] to the full support of the uniform translates.
  • A. Spectrum-Based Warping Functions: Interpolating only 8 of 64 eigenvalues yields similar warping functions and smoother spectrum-adapted filters than using the full spectrum.
  • A. Spectrum-Based Warping Functions: Spectrum slicing estimates cumulative spectral density by counting eigenvalues below sampled points through triangular factorizations, followed by monotonic cubic interpolation.
  • A. Spectrum-Based Warping Functions: The paper identifies spectral-density approximation for large graph Laplacians as an open problem and notes that Lanczos eigendecomposition does not accurately predict spectral density.
  • A. Spectrum-Based Warping Functions: For sparse mesh-like graphs with mean degree 3, warping computation takes approximately 1.5 seconds at 50k vertices and 5 minutes at 1m vertices.

VI. FILTERS ADAPTED TO CLASSES OF LARGE RANDOM GRAPHS

The paper adapts filters to graph classes whose asymptotic empirical spectral distributions are known, using those distributions as warping functions. For random regular graphs, this allows one filter system to transfer across realizations without recomputing each spectrum.

  • VI. FILTERS ADAPTED TO CLASSES OF LARGE RANDOM GRAPHS: Deterministic graphs resembling a random-graph class can use that class's empirical spectral distribution to construct an approximate spectrum-adapted warping function.
  • A. Graph Laplacian Spectrum of Large Random Regular Graphs: For random regular graphs, the procedure estimates an upper spectral bound, uses the empirical cumulative distribution on that interval, and sets γ = ωRR(λupper) = 1.
  • A. Graph Laplacian Spectrum of Large Random Regular Graphs: For degree-3 random regular graphs, the filters are adapted to the class rather than the particular realization, so the same filters can apply to larger realizations without scalability problems.
  • A. Graph Laplacian Spectrum of Large Random Regular Graphs: Finite random regular graphs may have λmax above the asymptotic bound, so the construction restricts the empirical cumulative distribution to [0, λupper] to keep the warping function defined.
  • A. Graph Laplacian Spectrum of Large Random Regular Graphs: The resulting filters are narrower in spectral regions with higher eigenvalue density, despite not being adapted to the specific graph realization.

B. Graph Laplacian Spectrum of Erd˝os-R´enyi Random Graphs

For Erdős–Rényi graphs, the shifted and scaled Laplacian spectrum converges to a free additive convolution involving a standard normal and semicircular distribution. The resulting deterministic approximation supports filter construction but introduces non-compact-support and finite-size caveats.

  • B. Graph Laplacian Spectrum of Erd˝os-R´enyi Random Graphs: The shifted and scaled empirical Laplacian spectral distribution of large Erdős–Rényi graphs converges almost surely to a free additive convolution of standard normal and semicircular distributions.
  • B. Graph Laplacian Spectrum of Erd˝os-R´enyi Random Graphs: The Erdős–Rényi construction approximates the empirical cumulative distribution from the asymptotic model and then uses it as ωER for warped filters.
  • B. Graph Laplacian Spectrum of Erd˝os-R´enyi Random Graphs: For finite graphs, the empirical spectral distribution is random, whereas the method uses a deterministic asymptotic approximation as the warping function.
  • B. Graph Laplacian Spectrum of Erd˝os-R´enyi Random Graphs: Because the relevant density has non-compact support, ωER(0) is only approximately zero and no strict upper spectral bound exists.For any ε > 0, λupper can instead be chosen so the probability of an eigenvalue above it is less than ε.

C. Normalized Graph Laplacian Spectrum of Erd˝os-R´enyi Random Graphs

The section derives spectrum-adapted filters for normalized graph Laplacians of large Erdős–Rényi graphs by approximating their empirical spectral distribution and cumulative distribution.

  • The resulting warped filters are narrower where the normalized Laplacian eigenvalue density is higher, although they are not adapted to a particular realization.
  • The normalized Laplacian spectrum of large Erdős–Rényi graphs converges weakly to a shifted and scaled semi-circular distribution.
  • The filter construction uses an approximate empirical spectral cumulative distribution as a deterministic warping function for random graphs.
  • For finite graphs, the upper spectral bound can be computed more precisely or set to the trivial normalized-Laplacian bound 2.

VII. SPECTRUM-ADAPTED TIGHT GRAPH WAVELET FRAMES

This section constructs spectrum-adapted tight graph wavelet and vertex-frequency frames by warping uniform filter systems with spectral-density information, then demonstrates their coherence and analysis properties.

  • Coherence comparison: The spectrum-adapted tight wavelet frame has the smallest cumulative coherence and atom-norm standard deviation across the four tested graphs.Table I compares five graph wavelet constructions for graphs with 256, 500, 64, and 1000 vertices.
  • Spectrum-adapted wavelet frames: The composite warping function adapts tight-frame kernels to the empirical spectral cumulative distribution rather than only to the spectrum length.
  • Vertex-frequency analysis: The graph Fourier transform shows frequency components but does not reveal their localization across graph regions, which the vertex-frequency coefficients expose.
  • Vertex-frequency analysis: Vertex-frequency atoms generated from warped filters reveal how different frequency components are localized across regions of the Minnesota road graph.The analysis uses 15 spectral graph filters and omits filters whose coefficients are nearly zero.
  • Practical advantages: The proposed vertex-frequency analysis avoids full Laplacian eigendecomposition, supports energy-density interpretation through tightness, and can reduce redundancy with fewer filters than vertices.

IX. CONCLUSION

The conclusion presents tight, computationally efficient graph frames whose filters are warped to the distribution of Laplacian eigenvalues, improving their discrimination between graph signals.

  • The method warps uniformly translated spectral kernels and translates them to graph vertices to construct dictionary atoms.
  • The resulting frames are tight, computationally efficient without full Laplacian eigendecomposition, and adapted to the specific eigenvalue distribution.
  • The spectrum-adapted construction is intended to produce dictionary atoms with better ability to discriminate between different graph signals.
  • The paper uses cumulative spectral density approximations for tight vertex-frequency frames and combines them with logarithmic warping for tight graph wavelet frames.
  • Ongoing work concerns methods for approximating the cumulative spectral density function for extremely large graphs.

X. APPENDIX

The appendix supplies proofs for the frame results using Parseval’s relation, eigenvector orthonormality, and roots-of-unity identities.

  • The proof of Lemma 1 uses Parseval’s relation and the orthonormality of graph Laplacian eigenvectors to establish the stated frame identities.
  • The argument expands cosines into complex exponentials and applies roots-of-unity identities under the condition K < R/2.
  • The proof concludes by substituting the derived identity back into the preceding expression.
  • The proof of Corollary 1 follows immediately from Theorem 1 after setting h-hat(y) = q(y).
Loading 1311.0897v1…