Wavelets on graphs via spectral graph theory. (English) Zbl 1213.42091

Hammond, David K.; Vandergheynst, Pierre; Gribonval, Rémi

Appl. Comput. Harmon. Anal. 30, No. 2, 129-150 (2011).

The classical continuous wavelet transform can be generated by the choice of a single “mother” wavelet \(\psi\). Other wavelets (with different locations and spatial scales) are formed by transforming the mother wavelet, for example, \(\psi_{s,a}(x)=\frac1s\psi\left(\frac{x-a}{s}\right)\). Then for any suitable function (i.e. signal), the wavelet coefficients at scale \(s\) and location \(a\) can be given with \(\psi_{s,a}\). Conversely, the wavelet coefficients enable us to reconstruct the original signal.
Several practical applications require discrete underlying spaces. The authors work out a possible framework of discrete wavelet transformation on weighted graphs. The first problem is the following: how to define \(\psi(sx)\) if \(x\) is a vertex of a graph? There is no expressive meaning of \(sx\), where \(s\) is a real scalar.
The authors get around the problem as follows. They define the Laplacian \[ (\mathcal{L}f)(m)=\sum_{n\sim m}a_{m,n}(f(m)-f(n)), \] where \(a_{m,n}\) is the adjacency matrix of the weighted graph and \(f\) is a real valued function on the vertices.
Since the usual one-dimensional Fourier transform uses the eigenfunctions of the Laplacian (i.e. the functions \(e^{i\omega x}\)), one may define the Fourier transform according to the eigenvectors of the Laplacian above. The authors go further and work out the spectral graph wavelet transform (SGWT) and deduces a number of its properties. It is also shown how can one speed up the SGWT-computations and apply it in practical applications, like transportation networks.
An implemented algorithm can be found at wiki.epfl.ch/sgwt.

Reviewer: István Mező (Debrecen)

MSC:

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

Keywords:

graph theory; spectral graph theory; wavelets; frames; overcomplete wavelet frames

Software:

JPEG2000; JDQZ

References:

[1]	Shapiro, J., Embedded image coding using zerotrees of wavelet coefficients, IEEE trans. signal process., 41, 12, 3445-3462, (1993) · Zbl 0841.94020
[2]	Said, A.; Pearlman, W., A new, fast, and efficient image codec based on set partitioning in hierarchical trees, IEEE trans. circuits syst. video technol., 6, 3, 243-250, (1996)
[3]	Hilton, M., Wavelet and wavelet packet compression of electrocardiograms, IEEE trans. biomed. eng., 44, 5, 394-402, (1997)
[4]	Buccigrossi, R.; Simoncelli, E., Image compression via joint statistical characterization in the wavelet domain, IEEE trans. image process., 8, 12, 1688-1701, (1999)
[5]	Taubman, D.; Marcellin, M., JPEG2000: image compression fundamentals, standards and practice, (2002), Kluwer Academic Publishers
[6]	Donoho, D.L.; Johnstone, I.M., Ideal spatial adaptation by wavelet shrinkage, Biometrika, 81, 425-455, (1994) · Zbl 0815.62019
[7]	Chang, S.; Yu, B.; Vetterli, M., Adaptive wavelet thresholding for image denoising and compression, IEEE trans. image process., 9, 9, 1532-1546, (2000) · Zbl 0962.94028
[8]	Sendur, L.; Selesnick, I., Bivariate shrinkage functions for wavelet-based denoising exploiting interscale dependency, IEEE trans. signal process., 50, 11, 2744-2756, (2002)
[9]	Portilla, J.; Strela, V.; Wainwright, M.J.; Simoncelli, E.P., Image denoising using scale mixtures of gaussians in the wavelet domain, IEEE trans. image process., 12, 1338-1351, (2003) · Zbl 1279.94028
[10]	Daubechies, I.; Teschke, G., Variational image restoration by means of wavelets: simultaneous decomposition, deblurring, and denoising, Appl. comput. harmon. anal., 19, 1, 1-16, (2005) · Zbl 1079.68104
[11]	Starck, J.-L.; Bijaoui, A., Filtering and deconvolution by the wavelet transform, Signal process., 35, 3, 195-211, (1994) · Zbl 0795.68204
[12]	Donoho, D.L., Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition, Appl. comput. harmon. anal., 2, 2, 101-126, (1995) · Zbl 0826.65117
[13]	Miller, E.; Willsky, A.S., A multiscale approach to sensor fusion and the solution of linear inverse problems, Appl. comput. harmon. anal., 2, 2, 127-147, (1995) · Zbl 0826.65118
[14]	Nowak, R.; Kolaczyk, E., A statistical multiscale framework for Poisson inverse problems, IEEE trans. inform. theory, 46, 5, 1811-1825, (2000) · Zbl 0999.94004
[15]	Bioucas-Dias, J., Bayesian wavelet-based image deconvolution: A GEM algorithm exploiting a class of heavy-tailed priors, IEEE trans. image process., 15, 4, 937-951, (2006)
[16]	Manthalkar, R.; Biswas, P.K.; Chatterji, B.N., Rotation and scale invariant texture features using discrete wavelet packet transform, Pattern recognit. lett., 24, 14, 2455-2462, (2003)
[17]	Flandrin, P., Wavelet analysis and synthesis of fractional Brownian motion, IEEE trans. inform. theory, 38, 2, 910-917, (1992), (Part 2) · Zbl 0743.60078
[18]	D. Lowe, Object recognition from local scale-invariant features, in: Proceedings of the Seventh IEEE International Conference on Computer Vision, vol. 2, 1999, pp. 1150-1157.
[19]	Apté, C.; Damerau, F.; Weiss, S.M., Automated learning of decision rules for text categorization, ACM trans. inf. syst., 12, 3, 233-251, (1994)
[20]	Chung, F.K., Spectral graph theory, CBMS reg. conf. ser. math., vol. 92, (1997), AMS Bookstore · Zbl 0867.05046
[21]	Mallat, S., A wavelet tour of signal processing, (1998), Academic Press · Zbl 0937.94001
[22]	Burt, P.J.; Adelson, E.H., The Laplacian pyramid as a compact image code, IEEE trans. commun., 31, 4, 532-540, (1983)
[23]	Simoncelli, E.P.; Freeman, W.T.; Adelson, E.H.; Heeger, D.J., Shiftable multi-scale transforms, IEEE trans. inform. theory, 38, 2, 587-607, (1992), special issue on wavelets
[24]	Kingsbury, N., Complex wavelets for shift invariant analysis and filtering of signals, Appl. comput. harmon. anal., 10, 3, 234-253, (2001) · Zbl 0990.94005
[25]	Candes, E.; Donoho, D., New tight frames of curvelets and optimal representations of objects with piecewise \(C^2\) singularities, Comm. pure appl. math., 57, 219-266, (2003) · Zbl 1038.94502
[26]	Peyré, G.; Mallat, S., Orthogonal bandlet bases for geometric images approximation, Comm. pure appl. math., 61, 9, 1173-1212, (2008) · Zbl 1255.94026
[27]	Antoine, J.; Vandergheynst, P., Wavelets on the 2-sphere: A group-theoretical approach, Appl. comput. harmon. anal., 7, 3, 262-291, (1999) · Zbl 0945.42023
[28]	Wiaux, Y.; McEwen, J.D.; Vandergheynst, P.; Blanc, O., Exact reconstruction with directional wavelets on the sphere, Mon. not. R. astron. soc., 388, 770, (2008)
[29]	Antoine, J.-P.; Bogdanova, I.; Vandergheynst, P., The continuous wavelet transform on conic sections, Int. J. wavelets multiresolut. inf. process., 6, 2, 137-156, (2008) · Zbl 1142.42319
[30]	M. Crovella, E. Kolaczyk, Graph wavelets for spatial traffic analysis, in: INFOCOM 2003, Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, 2003, pp. 1848-1857.
[31]	Smalter, A.; Huan, J.; Lushington, G., Graph wavelet alignment kernels for drug virtual screening, J. bioinform. comput. biol., 7, 473-497, (2009)
[32]	Jansen, M.; Nason, G.P.; Silverman, B.W., Multiscale methods for data on graphs and irregular multidimensional situations, J. R. stat. soc. ser. B stat. methodol., 71, 1, 97-125, (2009) · Zbl 1231.62054
[33]	Murtagh, F., The Haar wavelet transform of a dendrogram, J. classification, 24, 1, 3-32, (2007) · Zbl 1141.65094
[34]	Lee, A.B.; Nadler, B.; Wasserman, L., Treelets an adaptive multi-scale basis for sparse unordered data, Ann. appl. stat., 2, 435-471, (2008) · Zbl 1400.62274
[35]	Coifman, R.R.; Maggioni, M., Diffusion wavelets, Appl. comput. harmon. anal., 21, 53-94, (2006) · Zbl 1095.94007
[36]	Maggioni, M.; Mhaskar, H., Diffusion polynomial frames on metric measure spaces, Appl. comput. harmon. anal., 24, 3, 329-353, (2008) · Zbl 1242.42027
[37]	Geller, D.; Mayeli, A., Continuous wavelets on compact manifolds, Math. Z., 262, 895-927, (2009) · Zbl 1193.42123
[38]	Grossmann, A.; Morlet, J., Decomposition of Hardy functions into square integrable wavelets of constant shape, SIAM J. math. anal., 15, 4, 723-736, (1984) · Zbl 0578.42007
[39]	Hein, M.; Audibert, J.; von Luxburg, U., From graphs to manifolds - weak and strong pointwise consistency of graph Laplacians, (), 470-485 · Zbl 1095.68097
[40]	Singer, A., From graph to manifold Laplacian: the convergence rate, Appl. comput. harmon. anal., 21, 1, 128-134, (2006), diffusion maps and wavelets · Zbl 1095.68102
[41]	Belkin, M.; Niyogi, P., Towards a theoretical foundation for Laplacian-based manifold methods, J. comput. system sci., 74, 8, 1289-1308, (2008), learning theory, 2005 · Zbl 1157.68056
[42]	Reed, M.; Simon, B., Methods of modern mathematical physics, vol. 1: functional analysis, (1980), Academic Press
[43]	Daubechies, I., Ten lectures on wavelets, (1992), Society for Industrial and Applied Mathematics · Zbl 0776.42018
[44]	Heil, C.E.; Walnut, D.F., Continuous and discrete wavelet transforms, SIAM rev., 31, 4, 628-666, (1989) · Zbl 0683.42031
[45]	Watkins, D., The matrix eigenvalue problem - GR and Krylov subspace methods, (2007), Society for Industrial and Applied Mathematics · Zbl 1142.65038
[46]	Sleijpen, G.L.G.; der Vorst, H.A.V., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. matrix anal. appl., 17, 2, 401-425, (1996) · Zbl 0860.65023
[47]	Cheney, E., Introduction to approximation theory, (1966), McGraw-Hill New York · Zbl 0161.25202
[48]	Fraser, W., A survey of methods of computing minimax and near-minimax polynomial approximations for functions of a single independent variable, J. assoc. comput. Mach., 12, 295-314, (1965) · Zbl 0141.33601
[49]	Geddes, K.O., Near-minimax polynomial approximation in an elliptical region, SIAM J. numer. anal., 15, 6, 1225-1233, (1978) · Zbl 0413.65024
[50]	Phillips, G.M., Interpolation and approximation by polynomials, CMS books math., (2003), Springer-Verlag · Zbl 1023.41002
[51]	Grochenig, K., Acceleration of the frame algorithm, IEEE trans. signal process., 41, 12, 3331-3340, (1993) · Zbl 0841.94009
[52]	Zaroubi, S.; Goelman, G., Complex denoising of MR data via wavelet analysis: application for functional MRI, Magnetic resonance imaging, 18, 1, 59-68, (2000)
[53]	Ruttimann, U.; Unser, M.; Rawlings, R.; Rio, D.; Ramsey, N.; Mattay, V.; Hommer, D.; Frank, J.; Weinberger, D., Statistical analysis of functional MRI data in the wavelet domain, IEEE trans. medical imaging, 17, 2, 142-154, (1998)
[54]	Ville, D.V.D.; Blu, T.; Unser, M., Integrated wavelet processing and spatial statistical testing of fMRI data, Neuroimage, 23, 4, 1472-1485, (2004)
[55]	Hagmann, P.; Cammoun, L.; Gigandet, X.; Meuli, R.; Honey, C.J.; Wedeen, V.J.; Sporns, O., Mapping the structural core of human cerebral cortex, Plos comput. biol., 6, 7, e159, (2008)
[56]	Wessel, P.; Smith, W.H.F., A global, self-consistent, hierarchical, high-resolution shoreline database, J. geophys. res., 101, B4, 8741-8743, (1996)
[57]	R.I. Kondor, J. Lafferty, Diffusion kernels on graphs and other discrete input spaces, in: Proceedings of the 19th International Conference on Machine Learning, 2002.