Vertex-frequency analysis on graphs. (English) Zbl 1403.94031
Summary: One of the key challenges in the area of signal processing on graphs is to design dictionaries and transform methods to identify and exploit structure in signals on weighted graphs. (For a historical overview see R. Rubinstein, A. M. Bruckstein and M. Elad [Proc. IEEE 98, No. 6, 1045–1057 (2010; doi:10.1109/JPROC.2010.2040551)].) To do so, we need to account for the intrinsic geometric structure of the underlying graph data domain. In this paper, we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting. Our approach is to first define generalized convolution, translation, and modulation operators for signals on graphs, and explore related properties such as the localization of translated and modulated graph kernels. We then use these operators to define a windowed graph Fourier transform, enabling vertex-frequency analysis. When we apply this transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
Keywords:
signal processing on graphs; time-frequency analysis; generalized translation and modulation; spectral graph theory; localization; clusteringReferences:
| [1] | Rubinstein, R.; Bruckstein, A. M.; Elad, M., Dictionaries for sparse representation modeling, Proc. IEEE, 98, 6, 1045-1057 (2010) |
| [2] | Shuman, D. I.; Narang, S. K.; 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, 83-98 (2013) |
| [3] | Shuman, D. I.; Ricaud, B.; Vandergheynst, P., A windowed graph Fourier tranform, (Proc. IEEE Stat. Signal Process. Wkshp. Proc. IEEE Stat. Signal Process. Wkshp, Ann Arbor, MI (2012)), 133-136 |
| [4] | Gleich, D., The MatlabBGL Matlab library |
| [5] | Flandrin, P., Time-Frequency/Time-Scale Analysis (1999), Academic Press · Zbl 0954.94003 |
| [6] | Gröchenig, K., Foundations of Time-Frequency Analysis (2001), Birkhäuser · Zbl 0966.42020 |
| [7] | Mallat, S. G., A Wavelet Tour of Signal Processing (2008), Academic Press |
| [8] | Chung, F. K., Spectral Graph Theory, CBMS Reg. Conf. Ser. Math., vol. 92 (1997), AMS Bokstore · Zbl 0867.05046 |
| [9] | von Luxburg, U., A tutorial on spectral clustering, Stat. Comput., 17, 4, 395-416 (2007) |
| [10] | (Chapelle, O.; Schölkopf, B.; Zien, A., Semi-Supervised Learning (2006), MIT Press) |
| [11] | Elmoataz, A.; Lezoray, O.; Bougleux, S., Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing, IEEE Trans. Image Process., 17, 1047-1060 (2008) |
| [12] | Zhu, X.; Rabbat, M., Approximating signals supported on graphs, (Proc. IEEE Int. Conf. Acc., Speech, and Signal Process. Proc. IEEE Int. Conf. Acc., Speech, and Signal Process, Kyoto, Japan (2012)), 3921-3924 |
| [13] | Dekel, Y.; Lee, J. R.; Linial, N., Eigenvectors of random graphs: nodal domains, Random Structures Algorithms, 39, 1, 39-58 (2011) · Zbl 1223.05275 |
| [14] | Dumitriu, I.; Pal, S., Sparse regular random graphs: spectral density and eigenvectors, Ann. Probab., 40, 5, 2197-2235 (2012) · Zbl 1255.05173 |
| [15] | Tran, L. V.; Vu, V. H.; Wang, K., Sparse random graphs: eigenvalues and eigenvectors, Random Structures Algorithms, 42, 1, 110-134 (2013) · Zbl 1257.05089 |
| [16] | Brooks, S.; Lindenstrauss, E., Non-localization of eigenfunctions on large regular graphs, Israel J. Math., 193, 1, 1-14 (2013) · Zbl 1317.05110 |
| [17] | Strang, G., The discrete cosine transform, SIAM Rev., 41, 1, 135-147 (1999) · Zbl 0939.42021 |
| [18] | Saito, N.; Woei, E., On the phase transition phenomenon of graph Laplacian eigenfunctions on trees, RIMS Kokyuroku, 1743, 77-90 (2011) |
| [19] | Gray, R. M., Toeplitz and Circulant Matrices: A Review (2006), Now Publishers · Zbl 1115.15021 |
| [20] | Olfati-Saber, R., Algebraic connectivity ratio of Ramanujan graphs, (Proc. Amer. Control Conf. Proc. Amer. Control Conf, New York, NY (2007)), 4619-4624 |
| [21] | McGraw, P. N.; Menzinger, M., Laplacian spectra as a diagnostic tool for network structure and dynamics, Phys. Rev. E, 77, 3, 031102-1-031102-14 (2008) |
| [22] | Hammond, D. K.; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150 (2011) · Zbl 1213.42091 |
| [23] | Higham, N. J., Functions of Matrices (2008), Society for Industrial and Applied Mathematics · Zbl 1167.15001 |
| [24] | Grady, L. J.; Polimeni, J. R., Discrete Calculus (2010), Springer · Zbl 1195.68074 |
| [25] | Atkinson, K. E., An Introduction to Numerical Analysis (1989), John Wiley & Sons · Zbl 0718.65001 |
| [26] | Abramowitz, M.; Stegun, I., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (1972), Dover · Zbl 0543.33001 |
| [27] | Metzger, B.; Stollmann, P., Heat kernel estimates on weighted graphs, Bull. Lond. Math. Soc., 32, 4, 477-483 (2000) · Zbl 1023.60064 |
| [28] | Agaskar, A.; Lu, Y. M., An uncertainty principle for functions defined on graphs, (Proc. SPIE. Proc. SPIE, San Diego, CA, vol. 8138 (2011)), pp. 81380T-1-81380T-11 |
| [29] | Agaskar, A.; Lu, Y. M., Uncertainty principles for signals defined on graphs: bounds and characterizations, (Proc. IEEE Int. Conf. Acc., Speech, and Signal Process. Proc. IEEE Int. Conf. Acc., Speech, and Signal Process, Kyoto, Japan (2012)), 3493-3496 |
| [30] | Corless, R. M.; Gonnet, G. H.; Hare, D. E.; Jeffrey, D. J.; Knuth, D. E., On the Lambert W function, Adv. Comput. Math., 5, 1, 329-359 (1996) · Zbl 0863.65008 |
| [31] | Shuman, D. I.; Ricaud, B.; Vandergheynst, P., Vertex-frequency analysis on graphs (2013) |
| [32] | Christensen, O., Frames and Bases (2008), Birkhäuser · Zbl 1152.42001 |
| [33] | Kovačević, J.; Chebira, A., Life beyond bases: the advent of frames (part I), IEEE Signal Process. Mag., 24, 86-104 (2007) |
| [34] | Kovačević, J.; Chebira, A., Life beyond bases: the advent of frames (part II), IEEE Signal Process. Mag., 24, 115-125 (2007) |
| [35] | Jain, A. K.; Farrokhnia, F., Unsupervised texture segmentation using Gabor filters, Pattern Recognit., 24, 12, 1167-1186 (1991) |
| [36] | Combettes, P. L.; Pesquet, J.-C., Proximal splitting methods in signal processing, (Bauschke, H. H.; Burachik, R.; Combettes, P. L.; Elser, V.; Luke, D. R.; Wolkowicz, H., Fixed-Point Algorithms for Inverse Problems in Science and Engineering (2011), Springer-Verlag), 185-212 · Zbl 1242.90160 |
| [37] | Benzi, M.; Golub, G. H., Bounds for the entries of matrix functions with applications to preconditioning, BIT, 39, 417-438 (1999) · Zbl 0934.65054 |
| [38] | Benzi, M.; Razouk, N., Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices, Electron. Trans. Numer. Anal., 28, 16-39 (2007) · Zbl 1171.65034 |
| [39] | Golub, G. H.; Meurant, G., Matrices, Moments and Quadrature with Applications (2010), Princeton University Press · Zbl 1217.65056 |
| [40] | Chung, F. R.K.; Yau, S.-T., Eigenvalues of graphs and Sobolev inequalities, Combin. Probab. Comput., 4, 1, 11-26 (1995) · Zbl 0843.05073 |
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.
