Natural graph wavelet packet dictionaries

DOI10.1007/S00041-021-09832-3zbMATH Open1462.65229arXiv2009.09020OpenAlexW3157727345MaRDI QIDQ829903FDOQ829903

Authors: Alexander Cloninger, Haotian Li, Naoki Saito 

Publication date: 6 May 2021

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Abstract: We introduce a set of novel multiscale basis transforms for signals on graphs that utilize their "dual" domains by incorporating the "natural" distances between graph Laplacian eigenvectors, rather than simply using the eigenvalue ordering. These basis dictionaries can be seen as generalizations of the classical Shannon wavelet packet dictionary to arbitrary graphs, and do not rely on the frequency interpretation of Laplacian eigenvalues. We describe the algorithms (involving either vector rotations or orthogonalizations) to construct these basis dictionaries, use them to efficiently approximate graph signals through the best basis search, and demonstrate the strengths of these basis dictionaries for graph signals measured on sunflower graphs and street networks.

Full work available at URL: https://arxiv.org/abs/2009.09020

Recommendations

• Hierarchical graph Laplacian eigen transforms
• Spectral graph wavelet packets frames
• Wavelets on graphs via spectral graph theory
• Diffusion wavelet packets
• scientific article; zbMATH DE number 515889

zbMATH Keywords

best basis algorithmdual geometry of graphgraph Laplacian eigenvectorsgraph signal approximationwavelet packet dictionaries on graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for wavelets (65T60) Graph theory (including graph drawing) in computer science (68R10) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cites Work

• CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters
• Diffusion wavelets
• Modern multidimensional scaling. Theory and applications.
• A wavelet tour of signal processing. The sparse way.
• Wavelets on graphs via spectral graph theory
• A simple general procedure for orthogonal rotation
• Ten Lectures on Wavelets
• Entropy-based algorithms for best basis selection
• The varimax criterion for analytic rotation in factor analysis
• Harmonic analysis of digital data bases
• Title not available (Why is that?)
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels
• Foundations of factor analysis
• The Discrete Cosine Transform
• Wavelets. Tools for science and technology
• Optimal approximation for the submodular welfare problem in the value oracle model
• Analysis of neuronal dendrite patterns using eigenvalues of graph Laplacians
• Treelets -- an adaptive multi-scale basis for sparse unordered data
• The Haar wavelet transform of a dendrogram
• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex-frequency analysis on graphs
• Constructing the sunflower head
• A fast algorithm for adapted time-frequency tilings
• Mysteries around the graph Laplacian eigenvalue 4
• Gaussian bandwidth selection for manifold learning and classification
• Hierarchical graph Laplacian eigen transforms
• Archimedean Voronoi spiral tilings
• Spectral embedding norm: looking deep into the spectrum of the graph Laplacian
• On suprema of autoconvolutions with an application to Sidon sets

Cited In (11)

• Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
• Title not available (Why is that?)
• Signals on graphs: transforms and tomograms
• \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm
• Multiscale Transforms for Signals on Simplicial Complexes
• The dual graph shift operator: identifying the support of the frequency domain
• Hierarchical graph Laplacian eigen transforms
• Overview of the topical collection: harmonic analysis on combinatorial graphs
• Spectral graph wavelet packets frames
• Multi-link wavelets on hierarchical graphs
• eGHWT: the extended generalized Haar-Walsh transform

Uses Software

• viridis
• GitHub
• CayleyNets
• NGWP.jl
• MultiscaleGraphSignalTransforms.jl
• JuliaGeometry

This page was built for publication: Natural graph wavelet packet dictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q829903)