×

Adaptive directional Haar tight framelets on bounded domains for digraph signal representations. (English) Zbl 1459.42049

Summary: Based on hierarchical partitions, we provide the construction of Haar-type tight framelets on any compact set \(K\subseteq \mathbb{R}^d\). In particular, on the unit block \([0,1]^d\), such tight framelets can be built to be with adaptivity and directionality. We show that the adaptive directional Haar tight framelet systems can be used for digraph signal representations. Some examples are provided to illustrate results in this paper.

MSC:

42C15 General harmonic expansions, frames
05C20 Directed graphs (digraphs), tournaments
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bronstein, MM; Bruna, J.; LeCun, Y.; Szlam, A.; Vandergheynst, P., Geometric deep learning: going beyond euclidean data, IEEE Signal Process. Mag., 34, 4, 18-42 (2017)
[2] Candès, EJ; Donoho, DL, New tight frames of curvelets and optimal representations of objects with piecewise \(C^2\) singularities, Commun. Pure Appl. Math., 57, 2, 219-266 (2004) · Zbl 1038.94502
[3] Che, Z.; Zhuang, X., Digital affine shear filter banks with 2-Layer structure and their applications in image processing, IEEE Trans. Image Process., 27, 8, 3931-3941 (2018) · Zbl 1409.94081
[4] Cheng, C., Emirov, N., Sun, Q.: Preconditioned gradient descent algorithm for inverse filtering on spatially distributed networks. arXiv:2007.11491 (2020)
[5] Chui, CK, An Introduction to Wavelets. Wavelet Analysis and its Applications (1992), Boston: Academic Press Inc, Boston
[6] Chui, CK; Donoho, DL, Special issue: diffusion maps and wavelets, Appl. Comput. Harmon. Anal., 21, 1, 31 (2006)
[7] Chui, CK; Filbir, F.; Mhaskar, HN, Representation of functions on big data: graphs and trees, Appl. Comput. Harmon. Anal., 38, 3, 489-509 (2015) · Zbl 1329.62033
[8] Chui, CK; Mhaskar, HN; Zhuang, X., Representation of functions on big data associated with directed graphs, Appl. Comput. Harmon. Anal., 44, 1, 165-188 (2018) · Zbl 1378.68134
[9] Chung, FRK, Spectral Graph Theory (1997), Providence: American Mathematical Soc, Providence · Zbl 0867.05046
[10] Chung, F., Laplacians and the cheeger inequality for directed graphs, Ann. Combin., 9, 1, 1-19 (2005) · Zbl 1059.05070
[11] Cohen, A.; Daubechies, I.; Vial, P., Wavelets on the interval and fast wavelet transforms, Appl. Comput. Harmon. Anal., 1, 1, 54-81 (1993) · Zbl 0795.42018
[12] Daubechies, I.: Ten Lectures on Wavelets. CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), vol. 61, Philadelphia, PA (1992)
[13] Diao, C.; Han, B., Quasi-tight framelets with high vanishing moments derived from arbitrary renable functions, Appl. Comput. Harmon. Anal., 49, 1, 123-151 (2020) · Zbl 1437.42052
[14] Dong, B., Sparse representation on graphs by tight wavelet frames and applications, Appl. Comput. Harmon. Anal., 42, 3, 452-479 (2017) · Zbl 1366.42033
[15] Donoho, D.L., Kutyniok, G., Shahram, M., Zhuang, X.: A rational design of a digital shearlet transform. In: The 9th International Conference on Sampling Theory and Applications (SampTA’11). Singapore (2011)
[16] Emirov, N., Cheng, C., Jiang, J., Sun, Q.: Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering. arXiv:2003.11152 (2020)
[17] Garcia-Cardona, C., Merkurjev, E., Bertozzi, A.L., Flenner, A., Percus, A.G.: Fast multiclass segmentation using diffuse interface methods on graphs. Technical report, DTIC Document (2013) · Zbl 1329.68222
[18] Gavish, M., Nadler, B., Coifman, R.R.: Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning. In: Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp 367-374 (2010)
[19] Haar, A., Zur theorie der orthogonalen funktionensysteme, Math. Ann., 69, 3, 331-371 (1910) · JFM 41.0469.03
[20] Hammond, DK; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150 (2011) · Zbl 1213.42091
[21] Han, B.: Framelets and Wavelets: Algorithms, Analysis, and Applications. Birkhäuser (2017) · Zbl 1387.42001
[22] Han, B.; Michelle, M., Construction of wavelets and framelets on a bounded interval, Anal. Appl., 16, 6, 807-849 (2018) · Zbl 1404.42065
[23] Han, B.; Zhuang, X., Algorithms for matrix extension and orthogonal wavelet filter banks over algebraic number fields, Math. Comput., 82, 281, 459-490 (2013) · Zbl 1275.42052
[24] Han, B.; Zhuang, X., Smooth affine shear tight frames with MRA structures, Appl. Comput. Harmon. Anal., 39, 2, 300-338 (2015) · Zbl 1393.42032
[25] Han, X., Chen, Y., Shi, J., He, Z.: An extended cell transmission model based on digraph for urban traffic road network. In: 15th International IEEE Conference on Intelligent Transportation Systems (ITSC) (2012)
[26] Han, B.; Zhao, Z.; Zhuang, X., Directional tensor product complex tight framelets with low redundancy, Appl. Comput. Harmon. Anal., 41, 2, 603-637 (2016) · Zbl 1346.42046
[27] Han, B.; Li, T.; Zhuang, X., Directional compactly supported box spline tight framelets with simple geometric structure, Appl. Math. Lett, 91, 213-219 (2019) · Zbl 1407.42025
[28] Han, B.; Mo, Q.; Zhao, Z.; Zhuang, X., Directional compactly supported tensor product complex tight framelets with applications to image denoising and inpainting, SIAM J. Imaging Sci., 12, 4, 1739-1771 (2019) · Zbl 1434.42044
[29] Jiang, J.; Tay, DB; Sun, Q.; Ouyang, S., Design of nonsubsampled graph filter banks via lifting schemes, IEEE Signal Process. Lett., 27, 441-445 (2020)
[30] Kutyniok, G.; Labate, D., Shearlets: Multiscale Analysis for Multivariate Data, Applied and Numerical Harmonic Analysis (2012), New York: Springer, New York · Zbl 1237.42001
[31] Lafon, S.; Lee, AB, Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, 9, 1393-1403 (2006)
[32] Li, Y.; Zhang, Z-L, Digraph laplacian and the degree of asymmetry, Internet Math., 8, 4, 381-401 (2012) · Zbl 1258.05072
[33] Li, Y.-R., Zhuang, X.: Parallel magnetic resonance imaging reconstruction algorithm by 3-dimension directional Haar tight framelet regularization. In: Wavelets and Sparsity XVIII, SPIE Proc. 11138-47 (2019)
[34] Li, Y-R; Chan, RH; Shen, L.; Hsu, Y-C; Tseng, W-YI, An adaptive directional Haar framelet-based reconstruction algorithm for parallel magnetic resonance imaging, SIAM J. Imaging Sci., 9, 2, 794-821 (2016) · Zbl 1366.94057
[35] Li, M.; Ma, Z.; Wang, YG; Zhuang, X., Fast Haar transform for graph neural networks, Neural Netw., 128, 188-198 (2020)
[36] Lim, L.-H.: Hodge laplacians on graphs. arXiv:1507.05379 (2015)
[37] Mallat, S.: A Wavelet Tour of Signal Processing. Elsevier/Academic Press, Amsterdam, Third edition, The Sparse Way, With Contributions from Gabriel Peyré (2009) · Zbl 1170.94003
[38] Malliaros, FD; Vazirgiannis, M., Clustering and community detection in directed networks: a survey, Phys. Rep., 533, 4, 95-142 (2013) · Zbl 1356.05151
[39] Newman, ME, The structure and function of complex networks, SIAM Rev., 45, 2, 167-256 (2003) · Zbl 1029.68010
[40] Pesenson, I., Sampling in Paley-Wiener spaces on combinatorial graphs, Trans. Am. Math. Soc., 360, 10, 5603-5627 (2008) · Zbl 1165.42010
[41] Pesenson, I., Le Gia, Q.T., Mayeli, A., Mhaskar, H., Zhou, D.X.: Recent Applications of Harmonic Analysis to Function Spaces, Differential Equations, and Data Science: Novel Methods in Harmonic Analysis, vol. 2. Applied and Numerical Harmonic Analysis, Birkhäuser (2017) · Zbl 1378.42001
[42] Przulj, N., Introduction to the special issue on biological networks, Internet Math., 7, 4, 207-208 (2011)
[43] Satuluri, V., Parthasarathy, S.: Symmetrizations for clustering directed graphs. In: ACM Proceedings of the 14th International Conference on Extending Database Technology, pp. 343-354 (2011)
[44] Selesnick, IW; Baraniuk, RG; Kingsbury, NC, The dual-tree complex wavelet transform, IEEE Signal Process. Mag., 22, 6, 123-151 (2005)
[45] Singer, A.: From graph to manifold Laplacian: the convergence rate. Appl. Comput. Harmon. Anal. 21(1), 128-134 (2006) · Zbl 1095.68102
[46] Smith, L.M., Zhu, L., Lerman,K., Kozareva, Z.: The role of social media in the discussion of controversial topics. In: 2013 IEEE International Conference on Social Computing (SocialCom)
[47] Stein, EM, Harmonic Analysis: Real-Variable Methods, Orthogonality, and Oscillatory Integrals (1993), Princeton: Princeton University Press, Princeton · Zbl 0821.42001
[48] Van Dongen, S.M.: Graph Clustering by Flow Simulation, PhD thesis, University of Utrecht (2001)
[49] Wang, Y. G., Zhuang, X.: Tight framelets on graphs for multiscale data analysis. In: Wavelets and Sparsity XVIII, SPIE Proc. 11138-11 (2019)
[50] Wang, YG; Zhuang, X., Tight framelets and fast framelet filter bank transforms on manifolds, Appl. Comput. Harmon. Anal., 48, 1, 64-95 (2020) · Zbl 1447.42033
[51] Wang, Y. G., Li, M., Ma, Z., Montufar, G., Zhuang, X., Fan, Y.: Haar graph pooling. In: Proceedings of ICML 2020 (ICML 2020), pp. 3807-3817 (2020)
[52] Zhuang, X., Digital affine shear transforms: fast realization and applications in image/video processing, SIAM J. Imaging Sci., 9, 3, 1437-1466 (2016) · Zbl 1387.94025
[53] Zhuang, X., Han, B.: Compactly supported tensor product complex tight framelets with directionality. In: 2019 International Conference on Sampling Theory and Applications (SampTA), pp. 1-5 Bordeaux, France (2019)
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.