×

Multi-link wavelets on hierarchical graphs. (English) Zbl 1346.42048

Summary: Much of the recent progress in one- and two-dimensional signal processing can be attributed to the introduction of sparse representation techniques such as wavelets. Researchers have recently focused on extending the sparse representation to more complicated data, such as high-dimensional data and data on graphs. Some wavelet techniques applicable to trees as special cases of graph structures have been proposed that are very computationally efficient and easy to implement. However, a tree is too simple to model a data manifold accurately, in particular since a node has at most one parent. In this paper we propose a new efficient wavelet transform applicable to a directed acyclic graph (DAG), in which nodes are allowed to have multiple parents. Our method generalizes a Haar-like wavelet on an unweighted tree by using a redundant representation. In our method, we treat a DAG that has some nodes with signals we wish to analyze and the remaining nodes without signals. Nodes without signals are used to represent the underlying hierarchical structure of the data domain. We also describe a practical application to semi-supervised learning and show that our approach demonstrates an improvement over tree-based wavelets.

MSC:

42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
05C20 Directed graphs (digraphs), tournaments
65T60 Numerical methods for wavelets
94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

LatDraw
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mallat, S., A Wavelet Tour of Signal Processing (2008), Academic Press: Academic Press New York
[2] Starck, J.; Candès, E.; Donoho, D., The curvelet transform for image denoising, IEEE Trans. Image Process., 11, 6, 670-684 (2002) · Zbl 1288.94011
[3] Chung, F., Spectral Graph Theory (1997), Amer. Math. Soc.
[4] Coifman, R.; Maggioni, M., Diffusion wavelets, Appl. Comput. Harmon. Anal., 21, 1, 53-94 (2006) · Zbl 1095.94007
[5] Hammond, D.; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150 (2011) · Zbl 1213.42091
[6] Jansen, M.; Nason, G.; Silverman, B., 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
[7] Murtagh, F., The Haar wavelet transform of a dendrogram, J. Classification, 24, 1, 3-32 (2007) · Zbl 1141.65094
[8] Shen, G.; Ortega, A., Optimized distributed 2d transforms for irregularly sampled sensor network grids using wavelet lifting, (IEEE International Conference on Acoustics, Speech and Signal Processing (2008)), 2513-2516
[9] Lee, A.; Nadler, B.; Wasserman, L., Treelets: an adaptive multi-scale basis for sparse unordered data, Ann. Appl. Stat., 2, 2, 437-471 (2008) · Zbl 1400.62274
[10] Gavish, M.; Nadler, B.; Coifman, R., Multiscale wavelets on trees, graphs and high dimensional data: Theory and applications to semi supervised learning, (Proceedings of the 27th International Conference on Machine Learning (2010))
[11] Ram, I.; Elad, M., Generalized tree-based wavelet transform, IEEE Trans. Signal Process., 59, 9, 4199-4209 (2011) · Zbl 1392.94419
[12] Kovačević, J.; Chebira, A., Life beyond bases: The advent of frames (Part I), IEEE Signal Process. Mag., 24, 4, 86-104 (2007)
[13] Coifman, R.; Donoho, D., Translation-invariant de-noising, (Wavelets and Statistics (1995), Springer-Verlag), 125-150 · Zbl 0866.94008
[14] Freese, R., Automated lattice drawing, (Proceedings of the 2nd International Conference on Formal Concept Analysis (2004)), 112-127 · Zbl 1198.06001
[15] Goeman, J. J.; Mansmann, U., Multiple testing on the directed acyclic graph of gene ontology, Bioinformatics, 24, 4, 537-544 (2008)
[16] Alhusaini, A. H.; Prasanna, V. K.; Raghavendra, C. S., A unified resource scheduling framework for heterogeneous computing environments, (Proceedings of the 8th Heterogeneous Computing Workshop (1999)), 156-165
[17] Cidon, I.; Rom, R.; Shavitt, Y., Analysis of multi-path routing, IEEE/ACM Trans. Netw., 7, 6, 885-896 (1999)
[18] Jarvis, R. A.; Patrick, E. A., Clustering using a similarity measure based on shared near neighbors, IEEE Trans. Comput., 100, 11, 1025-1034 (1973)
[19] Mallat, S., Geometrical grouplets, Appl. Comput. Harmon. Anal., 26, 2, 161-180 (2009) · Zbl 1183.68693
[20] Sweldens, W., The lifting scheme: a custom-design construction of biorthogonal wavelets, Appl. Comput. Harmon. Anal., 3, 2, 186-200 (1996) · Zbl 0874.65104
[21] Severyn, A.; Moschitti, A., Fast support vector machines for structural kernels, (Machine Learning and Knowledge Discovery in Databases. Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Comput. Sci., vol. 6913 (2011)), 175-190
[22] Belkin, M.; Niyogi, P., Using manifold structure for partially labelled classification, (Proc. Conf. Advances in Neural Information Processing Systems (2002)), 929-936
[23] Johnson, S., Hierarchical clustering schemes, Psychometrika, 32, 3, 241-254 (1967) · Zbl 1367.62191
[24] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B, 58, 1, 267-288 (1996) · Zbl 0850.62538
[25] Zibulevsky, M.; Elad, M., L1-L2 optimization in signal and image processing, IEEE Signal Process. Mag., 27, 3, 76-88 (2010)
[26] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009
[27] Schölkopf, B.; Smola, A.; Müller, K.-R., Kernel principal component analysis, (Schölkopf, B.; Burges, C.; Smola, A., Advances in Kernel Methods — Support Vector Learning (1999), MIT Press: MIT Press Cambridge), 327-352
[28] Mallat, S., A theory for multiresolution signal decomposition: the wavelet representation, IEEE Trans. Pattern Mach. Intell., 11, 7, 674-693 (1989) · Zbl 0709.94650
[29] Simoncelli, E. P.; Adelson, E. H., Noise removal via Bayesian wavelet coring, (Proceedings of the 3rd International Conference on Image Processing (1996)), 379-382
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.