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

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.


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.)


Full Text: DOI arXiv


[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.