{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T22:19:27Z","timestamp":1773526767330,"version":"3.50.1"},"reference-count":59,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T00:00:00Z","timestamp":1598832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003958","name":"Stichting voor de Technische Wetenschappen","doi-asserted-by":"publisher","award":["14926"],"award-info":[{"award-number":["14926"]}],"id":[{"id":"10.13039\/501100003958","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003141","name":"Consejo Nacional de Ciencia y Tecnolog\u00eda","doi-asserted-by":"publisher","award":["594494"],"award-info":[{"award-number":["594494"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>To analyze and synthesize signals on networks or graphs, Fourier theory has been extended to irregular domains, leading to a so-called graph Fourier transform. Unfortunately, different from the traditional Fourier transform, each graph exhibits a different graph Fourier transform. Therefore to analyze the graph-frequency domain properties of a graph signal, the graph Fourier modes and graph frequencies must be computed for the graph under study. Although to find these graph frequencies and modes, a computationally expensive, or even prohibitive, eigendecomposition of the graph is required, there exist families of graphs that have properties that could be exploited for an approximate fast graph spectrum computation. In this work, we aim to identify these families and to provide a divide-and-conquer approach for computing an approximate spectral decomposition of the graph. Using the same decomposition, results on reducing the complexity of graph filtering are derived. These results provide an attempt to leverage the underlying topological properties of graphs in order to devise general computational models for graph signal processing.<\/jats:p>","DOI":"10.3390\/a13090214","type":"journal-article","created":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T11:53:49Z","timestamp":1598874829000},"page":"214","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2228-5388","authenticated-orcid":false,"given":"Mario","family":"Coutino","sequence":"first","affiliation":[{"name":"Department of Microelectronics, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The Netherlands"}]},{"given":"Sundeep Prabhakar","family":"Chepuri","sequence":"additional","affiliation":[{"name":"Department of Electrical and Communication Engineering, Indian Institute of Science, Bangalore 560 012, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2101-1484","authenticated-orcid":false,"given":"Takanori","family":"Maehara","sequence":"additional","affiliation":[{"name":"RIKEN Center for Advanced Intelligence Project, Tokyo 103-0027, Japan"}]},{"given":"Geert","family":"Leus","sequence":"additional","affiliation":[{"name":"Department of Microelectronics, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The Netherlands"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1109\/MSP.2012.2235192","article-title":"The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains","volume":"30","author":"Shuman","year":"2013","journal-title":"IEEE Sig. Proc. Mag."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1109\/MSP.2014.2329213","article-title":"Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure","volume":"31","author":"Sandryhaila","year":"2014","journal-title":"IEEE Sig. Proc. Mag."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.acha.2015.02.005","article-title":"Vertex-frequency analysis on graphs","volume":"40","author":"Shuman","year":"2016","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_4","unstructured":"Chung, F.R. (1997). Spectral Graph Theory, American Mathematical Society. Number 92."},{"key":"ref_5","first-page":"407","article-title":"Approximate Fast Graph Fourier Transforms via Multilayer Sparse Approximations","volume":"4","author":"Gribonval","year":"2018","journal-title":"IEEE Trans. Signal Inf. Process. Netw."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1109\/JSTSP.2016.2543461","article-title":"Flexible multilayer sparse approximations of matrices and applications","volume":"10","author":"Gribonval","year":"2016","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Le Magoarou, L., Tremblay, N., and Gribonval, R. (November, January 29). Analyzing the approximation error of the fast graph fourier transform. Proceedings of the 2017 51st Asilomar Conference on the Signals, Systems, and Computers, Pacific Grove, CA, USA.","DOI":"10.1109\/ACSSC.2017.8335133"},{"key":"ref_8","unstructured":"Golub, G.H., and Van Loan, C.F. (2012). Matrix Computations, Johns Hopkins Universtiy Press."},{"key":"ref_9","unstructured":"Diestel, R. (2005). Graph Theory (Graduate Texts in Mathematics), Springer."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Spielman, D.A. (2010). Algorithms, graph theory, and linear equations in Laplacian matrices. Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures, Springer.","DOI":"10.1142\/9789814324359_0164"},{"key":"ref_11","first-page":"2","article-title":"Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners","volume":"2","author":"Vaidya","year":"1991","journal-title":"Talk Based This Manuscr."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Koutis, I., Miller, G.L., and Peng, R. (2010, January 23\u201326). Approaching optimality for solving SDD linear systems. Proceedings of the 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.29"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"Siam J. Sci. Comput."},{"key":"ref_14","unstructured":"Loukas, A., and Vandergheynst, P. (2018). Spectrally approximating large graphs with smaller graphs. arXiv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.crma.2008.03.014","article-title":"The restricted isometry property and its implications for compressed sensing","volume":"346","author":"Candes","year":"2008","journal-title":"Comptes Rendus Math."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Narang, S.K., and Ortega, A. (2011, January 22\u201327). Downsampling graphs using spectral theory. Proceedings of the 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic.","DOI":"10.1109\/ICASSP.2011.5947281"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2786","DOI":"10.1109\/TSP.2012.2188718","article-title":"Perfect reconstruction two-channel wavelet filter banks for graph structured data","volume":"60","author":"Narang","year":"2012","journal-title":"IEEE Trans. Signal Process"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Saad, Y. (2003). Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898718003"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"21","DOI":"10.14495\/jsiaml.6.21","article-title":"Hierarchical graph Laplacian eigen transforms","volume":"6","author":"Irion","year":"2014","journal-title":"JSIAM Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3827","DOI":"10.1109\/TSP.2016.2544747","article-title":"Subgraph-based filterbanks for graph signals","volume":"64","author":"Tremblay","year":"2016","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Szlam, A.D., Maggioni, M., Coifman, R.R., and Bremer, J.C. (2005, January 21). Diffusion-driven multiscale analysis on manifolds and graphs: Top-down and bottom-up constructions. Proceedings of the Wavelets XI. International Society for Optics and Photonics, San Diego, CA, USA.","DOI":"10.1117\/12.616931"},{"key":"ref_22","unstructured":"Kondor, R., Teneva, N., and Garg, V. (2014, January 21\u201326). Multiresolution matrix factorization. Proceedings of the International Conference on Machine Learning, Beijing, China."},{"key":"ref_23","unstructured":"Teneva, N., Mudrakarta, P.K., and Kondor, R. (2016, January 9\u201311). Multiresolution matrix compression. Proceedings of the Artificial Intelligence and Statistics, Cadiz, Spain."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ithapu, V.K., Kondor, R., Johnson, S.C., and Singh, V. (2017, January 21\u201326). The incremental multiresolution matrix factorization algorithm. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Hawaii, HI, USA.","DOI":"10.1109\/CVPR.2017.81"},{"key":"ref_25","unstructured":"Gross, J.L., and Tucker, T.W. (1987). Topological Graph Theory, Courier Corporation."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Beineke, L., and Wilson, R. (2009). Topics in Topological Graph Theory, Cambridge University Press.","DOI":"10.1017\/CBO9781139087223"},{"key":"ref_27","unstructured":"Rosenberg, A.L., and Heath, L.S. (2001). Graph Separators, With Applications, Springer Science & Business Media."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"Siam J. Appl. Math."},{"key":"ref_29","unstructured":"Smith, W.D., and Wormald, N.C. (1998, January 8\u201311). Geometric separator theorems and applications. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), FOCS. IEEE, Palo Alto, CA, USA."},{"key":"ref_30","unstructured":"Rutter, J.D. (1994). A Serial Implementation of Cuppen\u2019s Divide and Conquer Algorithm For the Symmetric Eigenvalue Problem, University of California."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01386217","article-title":"Norms and exclusion theorems","volume":"2","author":"Bauer","year":"1960","journal-title":"Numer. Math."},{"key":"ref_32","unstructured":"Koutis, I., and Miller, G.L. (2007, January 7\u20139). A linear work, O (n 1\/6) time, parallel algorithm for solving planar Laplacians. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, New Orleans, Louisiana."},{"key":"ref_33","unstructured":"(2020, August 31). Matlab Mesh Partitioning and Graph Separator Toolbox. Available online: https:\/\/sites.cs.ucsb.edu\/~gilbert\/cs219\/cs219Spr2018\/Matlab\/meshpart\/meshpart.htm."},{"key":"ref_34","unstructured":"(2020, July 05). MatlabBGL: A Matlab Graph Library. Available online: https:\/\/www.cs.purdue.edu\/homes\/dgleich\/packages\/matlab_bgl\/."},{"key":"ref_35","unstructured":"MatlabBGL (2020, August 31). Planar graphs in MatlabBGL. Available online: https:\/\/www.cs.purdue.edu\/homes\/dgleich\/packages\/matlab_bgl\/planar_graphs\/planar_graphs.html."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Van Mieghem, P. (2010). Graph Spectra for Complex Networks, Cambridge University Press.","DOI":"10.1017\/CBO9780511921681"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"5911","DOI":"10.1109\/TSP.2017.2739099","article-title":"Stationary graph processes and spectral estimation","volume":"65","author":"Marques","year":"2017","journal-title":"IEEE Trans. Signal Process"},{"key":"ref_38","unstructured":"Perraudin, N., Paratte, J., Shuman, D., Martin, L., Kalofolias, V., Vandergheynst, P., and Hammond, D.K. (2014). GSPBOX: A toolbox for signal processing on graphs. arXiv."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Coutino, M., Isufi, E., and Leus, G. (2018). Advances in Distributed Graph Filtering. arXiv.","DOI":"10.1109\/TSP.2019.2904925"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Liu, J., Isufi, E., and Leus, G. (2017, January 14\u201316). Autoregressive moving average graph filter design. Proceedings of the 2017 IEEE Global Conference on. IEEE Signal and Information Processing (GlobalSIP), Montreal, QC, Canada.","DOI":"10.1109\/GlobalSIP.2017.8309028"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"4117","DOI":"10.1109\/TSP.2017.2703660","article-title":"Optimal Graph-Filter Design and Applications to Distributed Linear Network Operators","volume":"65","author":"Segarra","year":"2017","journal-title":"IEEE Trans. Signal Process"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Girault, B., Gon\u00e7alves, P., Fleury, E., and Mor, A.S. (2014, January 4\u20139). Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation. Proceedings of the 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy.","DOI":"10.1109\/ICASSP.2014.6853770"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1109\/TSP.2016.2614793","article-title":"Autoregressive Moving Average Graph Filtering","volume":"65","author":"Isufi","year":"2017","journal-title":"IEEE Trans. Signal Process"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1109\/TSP.2016.2620111","article-title":"Extending classical multirate signal processing theory to graphs Part II: M-channel filter banks","volume":"65","author":"Teke","year":"2017","journal-title":"IEEE Trans. Signal Process"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1109\/LSP.2014.2368128","article-title":"Design of near orthogonal graph filter banks","volume":"22","author":"Tay","year":"2015","journal-title":"IEEE Sig. Proc. Lett."},{"key":"ref_46","unstructured":"Li, S., Jin, Y., and Shuman, D.I. (2016). A Scalable M-Channel Critically Sampled Filter Bank for Graph Signals. arXiv."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1137\/130934283","article-title":"Approximating spectral densities of large matrices","volume":"58","author":"Lin","year":"2016","journal-title":"SIAM Rev."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1944345.1944349","article-title":"Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix","volume":"58","author":"Avron","year":"2011","journal-title":"J. ACM (JACM)"},{"key":"ref_49","unstructured":"Trudeau, R.J. (2013). Introduction to Graph Theory, Courier Corporation."},{"key":"ref_50","unstructured":"Gilbert, J.R. (1981). Graph Separator Theorems and Sparse Gaussian Elimination. [Ph.D. Thesis, Stanford University]."},{"key":"ref_51","unstructured":"Gilbert, J.R., Hutchinson, J.P., and Tarjan, R.E. (1982). A separator theorem for graphs of bounded genus. Technical Report, Cornell University."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0605032","article-title":"A separator theorem for chordal graphs","volume":"5","author":"Gilbert","year":"1984","journal-title":"Siam J. Algebr. Discret. Methods"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/256292.256294","article-title":"Separators for sphere-packings and nearest neighbor graphs","volume":"44","author":"Miller","year":"1997","journal-title":"J. ACM (JACM)"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E. (1980). Area-Efficient Graph Layouts (for VLSI). Technical Report, Carnegie-Mellon University.","DOI":"10.1109\/SFCS.1980.13"},{"key":"ref_55","unstructured":"Arge, L., Italiano, G.F., and Sedgewick, R. (2004). An experimental analysis of a compact graph representation. ALENEX\/ANALC, Society for Industrial and Applied Mathematics."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Cohen-Steiner, D., Kong, W., Sohler, C., and Valiant, G. (2018, January 19\u201323). Approximating the spectrum of a graph. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, UK.","DOI":"10.1145\/3219819.3220119"},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Sanfeliu, A., and Fu, K.S. (1983). A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern., 353\u2013362.","DOI":"10.1109\/TSMC.1983.6313167"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Horn, R.A., and Johnson, C.R. (1991). Topics in Matrix Analysis, Cambridge University Presss.","DOI":"10.1017\/CBO9780511840371"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/214\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:05:14Z","timestamp":1760177114000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,31]]},"references-count":59,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090214"],"URL":"https:\/\/doi.org\/10.3390\/a13090214","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,31]]}}}