Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-01-11T07:33:00.092Z Has data issue: false hasContentIssue false

6 - Adaptive Filtering on Graphs

Published online by Cambridge University Press:  24 November 2022

Paulo S. R. Diniz ,
Marcello L. R. de Campos ,
Wallace A. Martins ,
Markus V. S. Lima  and
Jose A. Apolinário, Jr
Paulo S. R. Diniz
Affiliation:
Universidade Federal do Rio de Janeiro
Marcello L. R. de Campos
Affiliation:
Universidade Federal do Rio de Janeiro
Wallace A. Martins
Affiliation:
University of Luxembourg
Markus V. S. Lima
Affiliation:
Universidade Federal do Rio de Janeiro
Jose A. Apolinário, Jr
Affiliation:
Military Institute of Engineering
Get access

Summary

The chapter discusses how to process data from irregular discrete domains, an emerging area called graph signal processing (GSP). Basically, the type of graph we deal with consists of a network with distributed vertices and weighted edges defining the neighborhood and the connections among the nodes. As such, the graph signals are collected in a vector whose entries represent the values of the signal nodes at a given time. A common issue related to GSP is the sampling problem, given the irregular structure of the data, where some sort of interpolation is possible whenever the graph signals are bandlimited or nearly bandlimited. These interpolations can be performed through the extension of the conventional adaptive filtering to signals distributed on graphs where there is no traditional data structure. The chapter presents the LMS, NLMS, and RLS algorithms for GSP along with their analyses and application to estimate bandlimited signals defined on graphs. In addition, the chapter presents a general framework for data-selective adaptive algorithms for GSP.

Keywords

graph signal processinglearning on graph signals
Type
Chapter
Information
Online Learning and Adaptive Filters , pp. 198 - 249
Publisher: Cambridge University Press
Print publication year: 2022

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ortega, A., Frossard, P., Kovacevic, J., M. F. Moura, J., and P. Vandergheynst, Graph signal processing: Overview, challenges, and applications, Proceedings of the IEEE 106, pp. 808-828 (2018).Google Scholar
Moreira, L. A. S., L. L. Ramos, A., L. R. de Campos, M., A. Apolinario Jr., J., and F. G. Serrenho, A graph signal processing approach to direction of arrival estimation, in Proceedings of the 27th European Signal Processing Conference (EUSIPCO), A Coruna, Spain, September 2019, pp. 1-5.Google Scholar
Sandryhaila, A. and M. F. Moura, J., Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure, IEEE Signal Processing Magazine 31, pp. 80-90 (2014).Google Scholar
Chen, Y., Kar, S., and J. M. F. Moura, The internet of things: Secure distributed inference, IEEE Signal Processing Magazine 35, pp. 64-75 (2018).Google Scholar
Friedman, J., Hastie, T., and R. Tibshirani, Sparse inverse covariance estimation with the graphical LASSO, Biostatistics 9, pp. 432-441 (2008).Google Scholar
Daitch, S. I., Kelner, J. A., and D. A. Spielman, Fitting a graph to vector data, in Proceedings of the 26th Annual International Conference on Machine Learning (ICML), Montreal, Canada, June 2009, pp. 201-208.Google Scholar
Dong, X., Thanou, D., Frossard, P., and P. Vandergheynst, Learning Laplacian matrix in smooth graph signal representations, IEEE Transactions on Signal Processing 64, pp. 6160-6173 December (2016).CrossRefGoogle Scholar
Segarra, S., Mateos, G., Marques, A. G., and A. Ribeiro, Blind identification of graph filters, IEEE Transactions on Signal Processing 65, pp. 1146-1159 (2017).Google Scholar
Mei, J. and M. F. Moura, J., Signal processing on graphs: Causal modeling of unstructured data, IEEE Transactions on Signal Processing 65, pp. 2077-2092 (2017).Google Scholar
Thanou, D., Dong, X., Kressner, D., and P. Frossard, Learning heat diffusion graphs, IEEE Transactions on Signal and Information Processing over Networks 3, pp. 484-499 (2017).Google Scholar
Egilmez, H. E., Pavez, E., and A. Ortega, Graph learning from data under Lapla- cian and structural constraints, IEEE Journal of Selected Topics in Signal Processing 11, pp. 825-841 (2017).Google Scholar
Segarra, S., Marques, A. G., Mateos, G., and A. Ribeiro, Network topology inference from spectral templates, IEEE Transactions on Signal and Information Processing over Networks 3, pp. 467-483 (2017).Google Scholar
Pasdeloup, B., Gripon, V., Mercier, G., Pastor, D., and M. G. Rabbat, Characterization and inference of graph diffusion processes from observations of stationary signals, IEEE Transactions on Signal and Information Processing over Networks 4, pp. 481-496 (2018).Google Scholar
Puschel, M. and J .M. F. Moura, The algebraic approach to the discrete cosine and sine transforms and their fast algorithms, SIAM Journal on Computing 32, pp. 1280-1316 (2003).Google Scholar
Puschel, M. and J .M. F. Moura, Algebraic signal processing theory: Cooley-Tukey type algorithms for DCTs and DSTs, IEEE Transactions on Signal Processing 56, pp. 1502-1521 (2008).Google Scholar
Puschel, M. and J .M. F. Moura, Algebraic signal processing theory: Foundation and 1-D time, IEEE Transactions on Signal Processing 56, pp. 3572-3585 (2008).Google Scholar
Puschel, M. and J .M. F. Moura, Algebraic signal processing theory: 1-D space, IEEE Transactions on Signal Processing 56, pp. 3586-3599 (2008).Google Scholar
Sandryhaila, A. and M. F. Moura, J., Discrete signal processing on graphs, IEEE Transactions on Signal Processing 61, pp. 1644-1656 (2013).Google Scholar
Sandryhaila, A. and M. F. Moura, J., Discrete signal processing on graphs: Frequency analysis, IEEE Transactions on Signal Processing 62, pp. 3042-3050 (2014).Google Scholar
Girault, B., Goncalves, P., and E. Fleury, Translation on graphs: An isometric shift operator, IEEE Signal Processing Letters 22, pp. 2416-2420 (2015).Google Scholar
Gavili, A. and Zhang, X. P., On the shift operator, graph frequency, and optimal filtering in graph signal processing, IEEE Transactions on Signal Processing 65, pp. 6303-6318 (2017).Google Scholar
Chung, F. R. K., Spectral Graph Theory (AMS, Providence, 1997).Google Scholar
Belkin, M. and Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation 15, pp. 1373-1396 (2003).Google Scholar
Wagner, R. S., Baraniuk, R. G., Du, S., Johnson, D. B., and A. Cohen, An architecture for distributed wavelet analysis and processing in sensor networks, in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN), Nashville, USA, April 2006, pp. 243-250.Google Scholar
Zhu, X. and Rabbat, M., Approximating signals supported on graphs, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan, March 2012, pp. 3921-3924.Google Scholar
Donoho, D. L. and Grimes, C., Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data, Proceedings of the National Academy of Sciences of the United States of America 100, pp. 5591-5596 (2013).Google Scholar
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Processing Magazine 30, pp. 83-98 (2013).Google Scholar
Romero, D., Ma, M., and G. B. Giannakis, Kernel-based reconstruction of graph signals, IEEE Transactions on Signal Processing 65, pp. 764-778 (2017).Google Scholar
Romero, D., Ioannidis, V. N., and G. B. Giannakis, Kernel-based reconstruction of space-time functions on dynamic graphs, IEEE Journal of Selected Topics in Signal Processing 11, pp. 856-869 (2017).Google Scholar
Ioannidis, V. N., Romero, D., and G. B. Giannakis, Inference of spatio-temporal functions over graphs via multikernel kriged Kalman filtering, IEEE Transactions on Signal Processing 66, pp. 3228-3239 (2018).Google Scholar
Elias, V. R. M., Gogineni, V. C., Martins, W. A., and S. Werner, Kernel regression on graphs in random Fourier features space, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Toronto, Canada, June 2021, pp. 5235-5239.Google Scholar
Elias, V. R. M., Gogineni, V. C., Martins, W. A., and S. Werner, Adaptive graph filters in reproducing kernel Hilbert spaces: Design and performance analysis, IEEE Transactions on Signal and Information Processing over Networks, 77, pp. 62-74 (2021).Google Scholar
Pesenson, I., Sampling in Paley-Wiener spaces on combinatorial graphs, Transactions of the American Mathematical Society 360, pp. 5603-5627 (2008).Google Scholar
Narang, S. K., Gadde, A., and A. Ortega, Signal processing techniques for interpolation in graph structured data, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Vancouver, Canada, May 2013, pp. 5445-5449.Google Scholar
Anis, A., Gadde, A., and A. Ortega, Towards a sampling theorem for signals on arbitrary graphs, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy, May 2014, pp. 3864-3868.Google Scholar
Shomorony, H. and Avestimehr, A. S., Sampling large data on graphs, in Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP), Atlanta, USA, December 2014, pp. 933-936.Google Scholar
Gadde, A. and Ortega, A., A probabilistic interpretation of sampling theory of graph signals, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brisbane, Australia, April 2015, pp. 3257-3261.Google Scholar
Chen, S., Sandryhaila, A., and J. Kovacevic, Sampling theory for graph signals, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brisbane, Australia, April 2015, pp. 3392-3396.Google Scholar
Wang, X., Liu, P., and Y. Gu, Local-set-based graph signal reconstruction, IEEE Transactions on Signal Processing 63, pp. 2432-2444 (2015).Google Scholar
Chen, S., Sandryhaila, A., M. F. Moura, J., and J. Kovacevic, Signal recovery on graphs: Variation minimization, IEEE Transactions on Signal Processing 63, pp. 4609-4624 (2015).Google Scholar
Chen, S., Varma, R., Sandryhaila, A., and J. Kovacevic, Discrete signal processing on graphs: Sampling theory, IEEE Transactions on Signal Processing 63, pp. 6510-6523 (2015).Google Scholar
Anis, A., Gadde, A., and A. Ortega, Efficient sampling set selection for bandlim- ited graph signals using graph spectral proxies, IEEE Transactions on Signal Processing 64, pp. 3775-3789 (2016).Google Scholar
Marques, A. G., Segarra, S., Leus, G., and A. Ribeiro, Sampling of graph signals with successive local aggregations, IEEE Transactions on Signal Processing 64, pp. 1832-1843 (2016).Google Scholar
Chen, S., Varma, R., Singh, A., and J. Kovacevic, Signal recovery on graphs: Fundamental limits of sampling strategies, IEEE Transactions on Signal and Information Processing over Networks 2, pp. 539-554 (2016).Google Scholar
O. Chamon and A. Ribeiro, L. F., Greedy sampling of graph signals, IEEE Transactions on Signal Processing 66, pp. 34-47 (2018).CrossRefGoogle Scholar
Puy, G., Tremblay, N., Gribonval, R., and P. Vandergheynst, Random sampling of bandlimited signals on graphs, Applied and Computational Harmonic Analysis 44, pp. 446-475 (2018).Google Scholar
Shen, Y., Leus, G., and G. B. Giannakis, Online graph-adaptive learning with scalability and privacy, IEEE Transactions on Signal Processing 67, pp. 24712483 (2019).Google Scholar
Cressie, N., The origins of Kriging, Mathematical Geology 22, pp. 239-252 (1990).Google Scholar
Lorenzo, P. D., Banelli, P., and S. Barbarossa, Optimal sampling strategies for adaptive learning of graph signals, in Proceedings of the 25th European Signal Processing Conference (EUSIPCO), Cos, Greece, September 2017, pp. 16841688.Google Scholar
Lorenzo, P. D., Banelli, P., Isufi, E., Barbarossa, S., and G. Leus, Adaptive graph signal processing: Algorithms and optimal sampling strategies, IEEE Transactions on Signal Processing 66, pp. 3584-3598 (2018).Google Scholar
Lorenzo, P., Barbarossa, S., and P. Banelli, Chapter 9 - Sampling and recovery of graph signals, in: P. M. Djuric, C. Richard (Eds.), Cooperative and Graph Signal Processing, Academic Press, 2018, pp. 261-282.Google Scholar
Nassif, R., Richard, C., Chen, J., and A. H. Sayed, A graph diffusion LMS strategy for adaptive graph signal processing, in Proceedings of the 51st Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, USA, November 2017, pp. 1973-1976.Google Scholar
Nassif, R., Richard, C., Chen, J., and A. H. Sayed, Distributed diffusion adaptation over graph signals, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Calgary, Canada, April 2018, pp. 4129-4133.Google Scholar
Hua, F., Nassif, R., Richard, C., Wang, H., and A. H. Sayed, A preconditioned graph diffusion LMS for adaptive graph signal processing, in Proceedings of the 26th European Signal Processing Conference (EUSIPCO), Rome, Italy, September 2018, pp. 111-115.Google Scholar
Hua, F., Nassif, R., Richard, C., Wang, H., and A. H. Sayed, Decentralized clustering for node-variant graph filtering with graph diffusion LMS, in Proceedings of the 52nd Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, USA, October 2018, pp. 1418-1422.Google Scholar
Coutino, M., Isufi, E., and G. Leus, Distributed edge-variant graph filters, in Proceedings of the IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Curacao, Dutch Antilles, December 2017, pp. 1-5.Google Scholar
Wang, X., Wang, M., and Y. Gu, A distributed tracking algorithm for reconstruction of graph signals, IEEE Journal of Selected Topics in Signal Processing 9, pp. 728-740 (2015).Google Scholar
Lorenzo, P. D., Barbarossa, S., Banelli, P., and S. Sardellitti, Adaptive least mean squares estimation of graph signals, IEEE Transactions on Signal and Information Processing over Networks 2, pp. 555-568 (2016).Google Scholar
Lorenzo, P. D., Banelli, P., Barbarossa, S., and S. Sardellitti, Distributed adaptive learning of graph signals, IEEE Transactions on Signal Processing 65, pp. 41934208 (2017).Google Scholar
Qiu, K., Mao, X., Shen, X., Wang, X., Li, T., and Y. Gu, Time-varying graph signal reconstruction, IEEE Journal of Selected Topics in Signal Processing 11, pp. 870-883 (2017).Google Scholar
Lorenzo, P. D. and Ceci, E., Online recovery of time-varying signals defined over dynamic graphs, in Proceedings of the 26th European Signal Processing Conference (EUSIPCO), Rome, Italy, September 2018, pp. 131-135.Google Scholar
M. Spelta and W. A. Martins, M. J., Online temperature estimation using graph signals, in Proceedings of the XXXVI Simposio Brasileiro de Telecomunicacoes e Processamento de Sinais (SBrT), Campina Grande, Brazil, September 2018, pp. 154-158.Google Scholar
M. Spelta and W. A. Martins, M. J., Normalized LMS algorithm and data- selective strategies for adaptive graph signal estimation, Signal Processing 167, 107326 (2020).Google Scholar
Lorenzo, P. D., Isufi, E., Banelli, P., Barbarossa, S., and G. Leus, Distributed recursive least squares strategies for adaptive reconstruction of graph signals, in Proceedings of the 25th European Signal Processing Conference (EUSIPCO), Cos, Greece, September 2017, pp. 2289-2293.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×