Graph Fourier transform based on singular value decomposition of the directed Laplacian. (English) Zbl 1530.94074
Summary: The Graph Fourier transform (GFT) is a fundamental tool in graph signal processing. In this paper, based on singular value decomposition of the Laplacian, we introduce a novel definition of GFT on directed graphs, and use the singular values of the Laplacian to carry the notion of graph frequencies. We show that the proposed GFT has its frequencies and frequency components evaluated by solving some constrained minimization problems with low computational cost, and it could represent graph signals with different modes of variation efficiently. Moreover, the proposed GFT is consistent with the conventional GFT in the undirected graph setting, and on directed circulant graphs, it is the classical discrete Fourier transform, up to some rotation, permutation and phase adjustment.
MSC:
| 94C15 | Applications of graph theory to circuits and networks |
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A15 | Information theory (general) |
| 42C05 | Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis |
Keywords:
graph signal processing; graph Fourier transform; directed graphs; singular value decompositionReferences:
| [1] | Chen, S.; Varma, R.; Sandryhaila, A.; Kovačević, J., Discrete signal processing on graphs: sampling theory, IEEE Trans. Signal Process., 63, 4, 6510-6523 (2015) · Zbl 1395.94094 · doi:10.1109/TSP.2015.2469645 |
| [2] | Cheng, C.; Emirov, N.; Sun, Q., Preconditioned gradient descent algorithm for inverse filtering on spatially distributed networks, IEEE Signal Process. Lett., 27, 1834-1838 (2020) · doi:10.1109/LSP.2020.3029699 |
| [3] | Cheng, C.; Jiang, Y.; Sun, Q., Spatially distributed sampling and reconstruction, Appl. Comput. Harmon. Anal., 47, 1, 109-148 (2019) · Zbl 1435.94164 · doi:10.1016/j.acha.2017.07.007 |
| [4] | Chung, FRK, Spectral Graph Theory (1997), Providence: American Mathematical Society, Providence · Zbl 0867.05046 |
| [5] | Dees, B.S., Stanković, L., Daković, M., Constantinides, A.G., Mandic, D.P.: Unitary shift operators on a graph. arXiv:1909.05767 |
| [6] | Deri, JA; Moura, JMF, Spectral projector-based graph Fourier transforms, IEEE J. Sel. Top. Signal Process., 11, 6, 785-795 (2017) · doi:10.1109/JSTSP.2017.2731599 |
| [7] | Domingos, J.; Moura, JMF, Graph Fourier transform: a stable approximation, IEEE Trans. Signal Process., 68, 4422-4437 (2020) · Zbl 07591045 · doi:10.1109/TSP.2020.3009645 |
| [8] | Ekambaram, V.N., Fanti, G.C., Ayazifar, B., Ramchandran, K.: Circulant structures and graph signal processing. In: Proceedings of International Conference on Image Processing. pp. 834-838 (2013) |
| [9] | Emirov, N.; Cheng, C.; Jiang, J.; Sun, Q., Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering, Sampl. Theory Signal Process. Data Anal., 20, , Article No. 2 (2022) · Zbl 1490.94035 · doi:10.1007/s43670-021-00019-x |
| [10] | Emirov, N.; Cheng, C.; Sun, Q.; Qu, Z., Distributed algorithms to determine eigenvectors of matrices on spatially distributed networks, Signal Process., 196, Article No. 108530 (2022) · doi:10.1016/j.sigpro.2022.108530 |
| [11] | Furutani, S., Shibahara, T., Akiyama, M., Hato, K., Aida, M.: Graph signal processing for directed graphs based on the Hermitian Laplacian. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pp. 447-463. Springer (2020) |
| [12] | Girault, B.; Ortega, A.; Narayanan, SS, Irregularity-aware graph Fourier transforms, IEEE Trans. Signal Process., 66, 21, 5746-5761 (2018) · Zbl 1415.94040 · doi:10.1109/TSP.2018.2870386 |
| [13] | Kadushin, C., Understanding Social Networks: Theories, Concepts, and Findings (2012), Oxford: Oxford University Press, Oxford |
| [14] | Kotzagiannidis, MS; Dragotti, PL, Splines and wavelets on circulant graphs, Appl. Comput. Harmonic Anal., 47, 2, 481-515 (2019) · Zbl 1423.42065 · doi:10.1016/j.acha.2017.10.002 |
| [15] | Kotzagiannidis, MS; Dragotti, PL, Sampling and reconstruction of sparse signals on circulant graphs—an introduction to graph-FRI, Appl. Comput. Harmonic Anal., 47, 3, 539-565 (2019) · Zbl 1422.94012 · doi:10.1016/j.acha.2017.10.003 |
| [16] | Le Magoarou, L.; Gribonval, R.; Tremblay, N., Approximate fast graph Fourier transforms via multilayer sparse approximations, IEEE Trans. Signal Inf. Process. Netw., 4, 2, 407-420 (2018) |
| [17] | Li, Y.; Zhang, Z., Digraph Laplacian and the degree of the asymmetry, Internet Math., 8, 381-401 (2012) · Zbl 1258.05072 · doi:10.1080/15427951.2012.708890 |
| [18] | Lu, K-S; Ortega, A., Fast graph Fourier transforms based on graph symmetry and bipartition, IEEE Trans. Signal Process., 67, 18, 4855-4869 (2019) · Zbl 07123402 · doi:10.1109/TSP.2019.2932882 |
| [19] | Marques, A.; Segarra, S.; Mateos, G., Signal processing on directed graphs: the role of edge directionality when processing and learning from network data, IEEE Signal Process. Mag., 37, 6, 99-116 (2020) · doi:10.1109/MSP.2020.3014597 |
| [20] | Ortega, A.; Frossard, P.; Kovačević, J.; Moura, JMF; Vandergheynst, P., Graph signal processing: overview, challenges, and applications, Proc. IEEE, 106, 5, 808-828 (2018) · doi:10.1109/JPROC.2018.2820126 |
| [21] | Ricaud, B.; Borgnat, P.; Tremblay, N.; Gonçalves, P.; Vandergheynst, P., Fourier could be a data scientist: from graph Fourier transform to signal processing on graphs, C. R. Phys., 20, 5, 474-488 (2019) · doi:10.1016/j.crhy.2019.08.003 |
| [22] | Saito, N.: How can we naturally order and organize graph Laplacian eigenvectors? In: 2018 IEEE Statistical Signal Processing Workshop (SSP). pp. 483-487 (2018) |
| [23] | Sandryhaila, A.; Moura, JMF, Discrete signal processing on graphs, IEEE Trans. Signal Process., 61, 7, 1644-1656 (2013) · Zbl 1393.94424 · doi:10.1109/TSP.2013.2238935 |
| [24] | Sandryhaila, A.; Moura, JMF, Discrete signal processing on graphs: frequency analysis, IEEE Trans. Signal Process., 62, 12, 3042-3054 (2014) · Zbl 1394.94498 · doi:10.1109/TSP.2014.2321121 |
| [25] | Sandryhaila, A.; Moura, JMF, Big data analysis with signal processing on graphs: representation and processing of massive data sets with irregular structure, IEEE Signal Process. Mag., 31, 5, 80-90 (2014) · doi:10.1109/MSP.2014.2329213 |
| [26] | Sardellitti, S.; Barbarossa, S.; Di Lorenzo, P., On the graph Fourier transform for directed graphs, IEEE J. Sel. Top. Signal Process., 11, 6, 796-811 (2017) · doi:10.1109/JSTSP.2017.2726979 |
| [27] | Segarra, S.; Mateos, G.; Marques, AG; Riberio, A., Blind identification of graph filters, IEEE Trans. Signal Process., 65, 5, 1146-1159 (2017) · Zbl 1414.94544 · doi:10.1109/TSP.2016.2628343 |
| [28] | Shafipour, R.; Khodabakhsh, A.; Mateos, G.; Nikolova, E., A directed graph Fourier transform with spread frequency components, IEEE Trans. Signal Process., 67, 4, 946-960 (2019) · Zbl 1415.94222 · doi:10.1109/TSP.2018.2886151 |
| [29] | Shuman, DI; Narang, SK; Frossard, P.; Ortega, A.; Vandergheynst, P., The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30, 3, 83-98 (2013) · doi:10.1109/MSP.2012.2235192 |
| [30] | Singh, R., Chakraborty, A., Manoj, B.: Graph Fourier transform based on directed Laplacian. In: Proceedings of IEEE International Conference on Signal Processing, Information, Communication. pp. 1-5 (2016) |
| [31] | Stanković, L., Daković, M., Sejdić, E.: Introduction to graph signal processing. In: Vertex-Frequency Analysis of Graph Signals, pp. 3-108. Springer (2019) · Zbl 1435.94062 |
| [32] | Wasserman, S.; Faust, K., Social Networks Analysis: Methods and Applications (1994), Cambridge: Cambridge University Press, Cambridge · Zbl 0926.91066 · doi:10.1017/CBO9780511815478 |
| [33] | Wen, Z.; Yin, W., A feasible method for optimization with orthogonality constraints, Math. Program., 142, 1-2, 397-434 (2013) · Zbl 1281.49030 · doi:10.1007/s10107-012-0584-1 |
| [34] | Yang, L.; Qi, A.; Huang, C.; Huang, J., Graph Fourier transform based on \(l_1\) norm variation minimization, Appl. Comput. Harmonic Anal., 52, 348-365 (2021) · Zbl 1479.94077 · doi:10.1016/j.acha.2020.04.001 |
| [35] | Zeng, J.; Cheung, G.; Ortega, A., Bipartite approximation for graph wavelet signal decomposition, IEEE Trans. Signal Process., 65, 20, 5466-5480 (2017) · Zbl 1415.94297 · doi:10.1109/TSP.2017.2733489 |
| [36] | Zhang, X.; He, Y.; Brugnone, N.; Perlmutter, M.; Hirn, M., MagNet: a neural network for directed graphs, Adv. Neural Inf. Process. Syst., 34, 27003-27015 (2021) |
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.
