Wavelets on graphs via spectral graph theory

DOI10.1016/J.ACHA.2010.04.005zbMATH Open1213.42091arXiv0912.3848OpenAlexW2158787690MaRDI QIDQ629253FDOQ629253

Authors: David K. Hammond, P. Vandergheynst, Rémi Gribonval 

Publication date: 9 March 2011

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral decomposition of the discrete graph Laplacian $L$. Given a wavelet generating kernel $g$ and a scale parameter $t$, we define the scaled wavelet operator $T_g^t=g(tL)$. The spectral graph wavelets are then formed by localizing this operator by applying it to an indicator function. Subject to an admissibility condition on $g$, this procedure defines an invertible transform. We explore the localization properties of the wavelets in the limit of fine scales. Additionally, we present a fast Chebyshev polynomial approximation algorithm for computing the transform that avoids the need for diagonalizing $L$. We highlight potential applications of the transform through examples of wavelets on graphs corresponding to a variety of different problem domains.

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

Recommendations

• Diffusion wavelets
• Fractional spectral graph wavelets and their applications
• scientific article; zbMATH DE number 5054757
• Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
• Vertex-frequency analysis on graphs

zbMATH Keywords

waveletsspectral graph theorygraph theoryframesovercomplete wavelet frames

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Ideal spatial adaptation by wavelet shrinkage
• Diffusion wavelets
• Title not available (Why is that?)
• Towards a theoretical foundation for Laplacian-based manifold methods
• Interpolation and approximation by polynomials
• Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition
• Title not available (Why is that?)
• Ten Lectures on Wavelets
• Title not available (Why is that?)
• Complex wavelets for shift invariant analysis and filtering of signals
• Multiscale methods for data on graphs and irregular multidimensional situations
• Wavelet analysis and synthesis of fractional Brownian motion
• A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems
• Wavelets on the 2-sphere: A group-theoretical approach
• Continuous wavelets on compact manifolds
• From graph to manifold Laplacian: the convergence rate
• New tight frames of curvelets and optimal representations of objects with piecewise C² singularities
• Learning Theory
• Continuous and Discrete Wavelet Transforms
• Image denoising using scale mixtures of gaussians in the wavelet domain
• Decomposition of Hardy Functions into Square Integrable Wavelets of Constant Shape
• Title not available (Why is that?)
• Adaptive wavelet thresholding for image denoising and compression
• The Matrix Eigenvalue Problem
• Embedded image coding using zerotrees of wavelet coefficients
• Orthogonal bandelet bases for geometric images approximation
• Variational image restoration by means of wavelets: Simultaneous decomposition, deblurring, and denoising
• A statistical multiscale framework for Poisson inverse problems
• Acceleration of the frame algorithm
• A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable
• Treelets -- an adaptive multi-scale basis for sparse unordered data
• Diffusion polynomial frames on metric measure spaces
• Near-Minimax Polynomial Approximation in an Elliptical Region
• Filtering and deconvolution by the wavelet transform
• A multiscale approach to sensor fusion and the solution of linear inverse problems
• The Haar wavelet transform of a dendrogram
• THE CONTINUOUS WAVELET TRANSFORM ON CONIC SECTIONS

Cited In (only showing first 100 items - show all)

• Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise
• Fast Haar transforms for graph neural networks
• Approximate and exact solutions of intertwining equations through random spanning forests
• Vertex-frequency analysis on graphs
• The DFS fused Lasso: linear-time denoising over general graphs
• Title not available (Why is that?)
• Graph theoretic uncertainty and feasibility
• More power via graph-structured tests for differential expression of gene networks
• Natural graph wavelet packet dictionaries
• Localized Fourier analysis for graph signal processing
• Distributed reconstruction of time-varying graph signals via a modified Newton's method
• Sparse representation on graphs by tight wavelet frames and applications
• Title not available (Why is that?)
• Representation of functions on big data associated with directed graphs
• Perfect reconstruction two-channel filter banks on arbitrary graphs
• Local smoothness of graph signals
• Parseval wavelets on hierarchical graphs
• Random sampling of bandlimited signals on graphs
• Signals on graphs: transforms and tomograms
• Spectral triples and wavelets for higher-rank graphs
• Tensor network and (\(p\)-adic) AdS/CFT
• Uncertainty quantification in graph-based classification of high dimensional data
• Fractional spectral graph wavelets and their applications
• Novel and efficient computation of Hilbert-Huang transform on surfaces
• Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel
• Approximation theorems on graphs
• A Matlab suite for second generation wavelets on an interval and the corresponding adaptive grid
• An adaptive spectral graph wavelet method for PDEs on networks
• Feature-preserving, mesh-free empirical mode decomposition for point clouds and its applications
• Intertwining wavelets or multiresolution analysis on graphs through random forests
• Dual-domain graph convolutional networks for skeleton-based action recognition
• An adaptive meshfree spectral graph wavelet method for partial differential equations
• Tight framelets and fast framelet filter bank transforms on manifolds
• Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
• Graph Fourier transform based on \(\ell_1\) norm variation minimization
• The dual graph shift operator: identifying the support of the frequency domain
• Graph convolutional neural networks via scattering
• A unified framework for harmonic analysis of functions on directed graphs and changing data
• Hierarchical graph Laplacian eigen transforms
• Partition of unity methods for signal processing on graphs
• Signal processing on the permutahedron: tight spectral frames for ranked data analysis
• Graph deconvolutional networks
• Sparse approximation of 3D meshes using the spectral geometry of the Hamiltonian operator
• Data-driven thresholding in denoising with spectral graph wavelet transform
• On the dual geometry of Laplacian eigenfunctions
• Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing
• Spectral graph wavelet optimized finite difference method for solution of Burger's equation with different boundary conditions
• Gabor-type frames for signal processing on graphs
• Multiscale representation of surfaces by tight wavelet frames with applications to denoising
• Representation of functions on big data: graphs and trees
• Harmonic analysis for graph refinements and the continuous graph FFT
• Multi-link wavelets on hierarchical graphs
• Graph spectral image smoothing using the heat kernel
• eGHWT: the extended generalized Haar-Walsh transform
• Tracking network dynamics: a survey using graph distances
• K-plex cover pooling for graph neural networks
• On the optimality of shape and data representation in the spectral domain
• Local measurement and diffusion reconstruction for signals on a weighted graph
• Regularized principal component analysis
• Multilevel approximation of Gaussian random fields: fast simulation
• Invertibility of graph translation and support of Laplacian Fiedler vectors
• Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
• Data Analytics on Graphs Part II: Signals on Graphs
• Data Analytics on Graphs Part III: Machine Learning on Graphs, from Graph Topology to Applications
• A class of Laplacian multiwavelets bases for high-dimensional data
• Title not available (Why is that?)
• Dual wavelet frame transforms on manifolds and graphs
• Adaptive directional Haar tight framelets on bounded domains for digraph signal representations
• Multi-view graph convolutional networks with attention mechanism
• Spectra of Laplacian matrices of weighted graphs: structural genericity properties
• Graphical designs and gale duality
• Parallel Transport Convolution: Deformable Convolutional Networks on Manifold-Structured Data
• Spectral graph wavelet regularization and adaptive wavelet for the backward heat conduction problem
• Graph signal processing on dynamic graphs based on temporal-attention product
• TFA-CLSTMNN: Novel convolutional network for sound-based diagnosis of COVID-19
• A generalization of Gleason's frame function for quantum measurement
• Rutting prediction and analysis of influence factors based on multivariate transfer entropy and graph neural networks
• Fast mesh data augmentation via Chebyshev polynomial of spectral filtering
• \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm
• Polynomial graph filters of multiple shifts and distributed implementation of inverse filtering
• Dual framelets transform on manifolds and graphs
• Multiscale Transforms for Signals on Simplicial Complexes
• Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling
• Splines and wavelets on circulant graphs
• Spatiotemporal analysis using Riemannian composition of diffusion operators
• Optimal design of edge weights in transforming low-frequency graph signals into the spectral domain
• Using graph convolutional networks for approximate reasoning with abstract argumentation frameworks: a feasibility study
• Constraint matrix factorization for space variant PSFs field restoration
• Deep neural network for drawing networks, \({(DNN)^{ 2 }} \)
• Analysis vs synthesis with structure -- an investigation of union of subspace models on graphs
• A graph convolutional neural network for gene expression data analysis with multiple gene networks
• HesGCN: Hessian graph convolutional networks for semi-supervised classification
• Adaptive multi-channel contrastive graph convolutional network with graph and feature fusion
• Extreme values of the Fiedler vector on trees
• Multiscale discrete framelet transform for graph-structured signals
• A noncommutative approach to the graphon Fourier transform
• A gentle introduction to deep learning for graphs
• CT image reconstruction by spatial-Radon domain data-driven tight frame regularization
• Graph Spectral Image Smoothing
• Spectral graph wavelet packets frames

Uses Software

• JPEG2000
• JDQZ

This page was built for publication: Wavelets on graphs via spectral graph theory

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