{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:23:53Z","timestamp":1760239433172,"version":"build-2065373602"},"reference-count":67,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We propose and investigate two new methods to approximate f(A)b for large, sparse, Hermitian matrices A. Computations of this form play an important role in numerous signal processing and machine learning tasks. The main idea behind both methods is to first estimate the spectral density of A, and then find polynomials of a fixed order that better approximate the function f on areas of the spectrum with a higher density of eigenvalues. Compared to state-of-the-art methods such as the Lanczos method and truncated Chebyshev expansion, the proposed methods tend to provide more accurate approximations of f(A)b at lower polynomial orders, and for matrices A with a large number of distinct interior eigenvalues and a small spectral width. We also explore the application of these techniques to (i) fast estimation of the norms of localized graph spectral filter dictionary atoms, and (ii) fast filtering of time-vertex signals.<\/jats:p>","DOI":"10.3390\/a13110295","type":"journal-article","created":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T10:32:47Z","timestamp":1605263567000},"page":"295","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Spectrum-Adapted Polynomial Approximation for Matrix Functions with Applications in Graph Signal Processing"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7598-9218","authenticated-orcid":false,"given":"Tiffany","family":"Fan","sequence":"first","affiliation":[{"name":"Institute for Computational &amp; Mathematical Engineering, Stanford University, Stanford, CA 94305, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1989-3190","authenticated-orcid":false,"given":"David I.","family":"Shuman","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science, Macalester College, St. Paul, MN 55105, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6942-7158","authenticated-orcid":false,"given":"Shashanka","family":"Ubaru","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8614-5360","authenticated-orcid":false,"given":"Yousef","family":"Saad","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Sch\u00f6lkopf, B., and Warmuth, M. (2003). Kernels and Regularization on Graphs. Learning Theory and Kernel Machines, Springer. Lecture Notes in Computer Science.","key":"ref_1","DOI":"10.1007\/b12006"},{"doi-asserted-by":"crossref","unstructured":"Belkin, M., Matveeva, I., and Niyogi, P. (2004). Regularization and Semi-Supervised Learning on Large Graphs. Learnning Theory, Springer. Lecture Notes in Computer Science.","key":"ref_2","DOI":"10.1007\/978-3-540-27819-1_43"},{"unstructured":"Thrun, S., Saul, L., and Sch\u00f6lkopf, B. (2004). Learning with Local and Global Consistency, MIT Press. Advances Neural Information Processing Systems.","key":"ref_3"},{"key":"ref_4","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 Signal Process. Mag."},{"unstructured":"Defferrard, M., Bresson, X., and Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering, MIT Press. Advances Neural Information Processing Systems.","key":"ref_5"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","article-title":"Geometric Deep Learning: Going Beyond Euclidean Data","volume":"34","author":"Bronstein","year":"2017","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_7","first-page":"1002","article-title":"Compressive Spectral Clustering","volume":"48","author":"Tremblay","year":"2016","journal-title":"Proc. Int. Conf. Mach. Learn."},{"doi-asserted-by":"crossref","unstructured":"Orecchia, L., Sachdeva, S., and Vishnoi, N.K. (2012). Approximating the Exponential, the Lanczos Method and an \u00d5(m)-Time Spectral Algorithm for Balanced Separator. Proc. ACM Symp. Theory Comput., 1141\u20131160.","key":"ref_8","DOI":"10.1145\/2213977.2214080"},{"key":"ref_9","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_10","first-page":"468","article-title":"Fast Methods for Estimating the Numerical Rank of Large Matrices","volume":"48","author":"Ubaru","year":"2016","journal-title":"Proc. Int. Conf. Mach. Learn."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1317","DOI":"10.1162\/NECO_a_00951","article-title":"Fast Estimation of Approximate Matrix Ranks Using Spectral Densities","volume":"29","author":"Ubaru","year":"2017","journal-title":"Neural Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1137\/16M1104974","article-title":"Fast Estimation of tr(f(A)) Via Stochastic Lanczos Quadrature","volume":"38","author":"Ubaru","year":"2017","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"A1558","DOI":"10.1137\/16M1078148","article-title":"Approximating Spectral Sums of Large-Scale Matrices Using Stochastic Chebyshev Approximations","volume":"39","author":"Han","year":"2017","journal-title":"SIAM J. Sci. Comput."},{"doi-asserted-by":"crossref","unstructured":"Arora, S., and Kale, S. (2007). A Combinatorial, Primal-Dual Approach to Semidefinite Programs. Proc. ACM Symp. Theory Comput., 227\u2013236.","key":"ref_14","DOI":"10.1145\/1250790.1250823"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1561\/0400000065","article-title":"Faster Algorithms Via Approximation Theory","volume":"9","author":"Sachdeva","year":"2014","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1552","DOI":"10.1137\/S1064827595295337","article-title":"Exponential Integrators for Large Systems of Differential Equations","volume":"19","author":"Hochbruck","year":"1998","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF01060992","article-title":"A Method for Exponential Propagation of Large Systems of Stiff Nonlinear Differential Equations","volume":"4","author":"Friesner","year":"1989","journal-title":"J. Sci. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1137\/0913071","article-title":"Efficient Solution of Parabolic Equations by Krylov Approximation Methods","volume":"13","author":"Gallopoulos","year":"1992","journal-title":"SIAM J. Sci. Stat. Comput."},{"doi-asserted-by":"crossref","unstructured":"Higham, N.J. (2008). Functions of Matrices, SIAM.","key":"ref_19","DOI":"10.1137\/1.9780898717778"},{"doi-asserted-by":"crossref","unstructured":"Davies, P.I., and Higham, N.J. (2005). Computing f(A)b for Matrix Functions f. QCD and Numerical Analysis III, Springer.","key":"ref_20","DOI":"10.1007\/3-540-28504-0_2"},{"doi-asserted-by":"crossref","unstructured":"Frommer, A., and Simoncini, V. (2008). Matrix Functions. Model Order Reduction: Theory, Research Aspects and Applications, Springer.","key":"ref_21","DOI":"10.1007\/978-3-540-78841-6_13"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1137\/S00361445024180","article-title":"Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later","volume":"45","author":"Moler","year":"2003","journal-title":"SIAM Rev."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/S0041-5553(89)80020-5","article-title":"Two Polynomial Methods of Calculating Functions of Symmetric Matrices","volume":"29","author":"Druskin","year":"1989","journal-title":"USSR Comput. Maths. Math. Phys."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1137\/060648945","article-title":"Filtered Conjugate Residual-Type Algorithms with Applications","volume":"28","author":"Saad","year":"2006","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/090778250","article-title":"Computing f(A)b Via Least Squares Polynomial Approximations","volume":"33","author":"Chen","year":"2011","journal-title":"SIAM J. Sci. Comp."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/S0895479895292400","article-title":"Extended Krylov Subspaces: Approximation of the Matrix Square Root and Related Functions","volume":"19","author":"Druskin","year":"1998","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2481","DOI":"10.1137\/050633846","article-title":"A Restarted Krylov Subspace Method for the Evaluation of Matrix Functions","volume":"44","author":"Eiermann","year":"2006","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2293","DOI":"10.1016\/j.laa.2008.06.029","article-title":"Implementation of a Restarted Krylov Subspace Method for the Evaluation of Matrix Functions","volume":"429","author":"Afanasjew","year":"2008","journal-title":"Lin. Alg. Appl."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1137\/16M1072565","article-title":"The Radau-Lanczos Method for Matrix Functions","volume":"38","author":"Frommer","year":"2017","journal-title":"SIAM J. Matrix Anal. Appl."},{"doi-asserted-by":"crossref","unstructured":"Golub, G.H., and Van Loan, C.F. (2013). Matrix Computations, Johns Hopkins University Press.","key":"ref_30","DOI":"10.56021\/9781421407944"},{"doi-asserted-by":"crossref","unstructured":"Mason, J.C., and Handscomb, D.C. (2003). Chebyshev Polynomials, Chapman and Hall.","key":"ref_31","DOI":"10.1201\/9781420036114"},{"unstructured":"Trefethen, L.N. (2013). Approximation Theory and Approximation Practice, SIAM.","key":"ref_32"},{"key":"ref_33","first-page":"736","article-title":"Distributed Signal Processing via Chebyshev Polynomial Approximation","volume":"4","author":"Shuman","year":"2018","journal-title":"IEEE Trans. Signal Inf. Process. Netw."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.acha.2010.04.005","article-title":"Wavelets on Graphs Via Spectral Graph Theory","volume":"30","author":"Hammond","year":"2011","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_35","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."},{"doi-asserted-by":"crossref","unstructured":"Van Mieghem, P. (2011). Graph Spectra for Complex Networks, Cambridge University Press.","key":"ref_36","DOI":"10.1017\/CBO9780511921681"},{"doi-asserted-by":"crossref","unstructured":"Tao, T. (2012). Topics in Random Matrix Theory, American Mathematical Society.","key":"ref_37","DOI":"10.1090\/gsm\/132"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1142\/S0129183194000842","article-title":"Densities of States of Mega-Dimensional Hamiltonian Matrices","volume":"5","author":"Silver","year":"1994","journal-title":"Int. J. Mod. Phys. C"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1006\/jcph.1996.0048","article-title":"Kernel Polynomial Approximations for Densities of States and Spectral Functions","volume":"124","author":"Silver","year":"1996","journal-title":"J. Comput. Phys."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"10154","DOI":"10.1103\/PhysRevB.49.10154","article-title":"Calculating the Density of States and Optical-Absorption Spectra of Large Quantum Systems by the Plane-Wave Moments Method","volume":"49","author":"Wang","year":"1994","journal-title":"Phy. Rev. B"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"3954","DOI":"10.1109\/TSP.2019.2923142","article-title":"Scalable M-channel critically sampled filter banks for graph signals","volume":"67","author":"Li","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"unstructured":"Girard, D. (1987). Un Algorithme Simple et Rapide Pour la Validation Crois\u00e9e G\u00e9n\u00e9ralis\u00e9e sur des Probl\u00e8mes de Grande Taille, Universit\u00e9 Grenoble Alpes. Technical Report.","key":"ref_42"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01395775","article-title":"A fast \u2019Monte-Carlo cross-validation\u2019procedure for large least squares problems with noisy data","volume":"56","author":"Girard","year":"1989","journal-title":"Numer. Math."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1002\/nla.2048","article-title":"Efficient Estimation of Eigenvalue Counts in an Interval","volume":"23","author":"Polizzi","year":"2016","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_45","first-page":"657","article-title":"Structured Sampling and Fast Reconstruction of Smooth Graph Signals","volume":"7","author":"Puy","year":"2018","journal-title":"Inf. Inference A J. IMA"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"4223","DOI":"10.1109\/TSP.2015.2424203","article-title":"Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Frames","volume":"63","author":"Shuman","year":"2015","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1137\/0717021","article-title":"Monotone Piecewise Cubic Interpolation","volume":"17","author":"Fritsch","year":"1980","journal-title":"SIAM J. Numer. Anal."},{"unstructured":"Gleich, D. (2020, November 11). The MatlabBGL Matlab Library. Available online: http:\/\/www.cs.purdue.edu\/homes\/dgleich\/packages\/matlab_bgl\/index.html.","key":"ref_48"},{"unstructured":"Stanford University Computer Graphics Laboratory (2020, November 11). The Stanford 3D Scanning Repository. Available online: http:\/\/graphics.stanford.edu\/data\/3Dscanrep\/.","key":"ref_49"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1109\/TSP.2017.2775589","article-title":"A Time-Vertex Signal Processing Framework: Scalable Processing and Meaningful Representations for Time-Series on Graphs","volume":"66","author":"Grassi","year":"2018","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2049662.2049663","article-title":"The University of Florida Sparse Matrix Collection","volume":"38","author":"Davis","year":"2011","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_52","first-page":"74","article-title":"Generation and Use of Orthogonal Polynomials for Data-Fitting with a Digital Computer","volume":"5","author":"Forsythe","year":"1957","journal-title":"J. SIAM"},{"doi-asserted-by":"crossref","unstructured":"Gautschi, W. (2004). Orthogonal Polynomials: Computation and Approximation, Oxford University Press.","key":"ref_53","DOI":"10.1093\/oso\/9780198506720.001.0001"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/BF01405565","article-title":"The Numerically Stable Reconstruction of Jacobi Matrices from Spectral Data","volume":"44","author":"Gragg","year":"1984","journal-title":"Numer. Math."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1137\/0729014","article-title":"Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator","volume":"29","author":"Saad","year":"1992","journal-title":"SIAM J. Numer. Anal."},{"doi-asserted-by":"crossref","unstructured":"Golub, G.H., and Meurant, G. (2010). Matrices, Moments and Quadrature with Applications, Princeton University Press.","key":"ref_56","DOI":"10.1515\/9781400833887"},{"unstructured":"Perraudin, N., Paratte, J., Shuman, D.I., Kalofolias, V., Vandergheynst, P., and Hammond, D.K. (2014). GSPBOX: A Toolbox for Signal Processing on Graphs. arXiv, Available online: https:\/\/epfl-lts2.github.io\/gspbox-html\/.","key":"ref_57"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MSP.2020.3015024","article-title":"Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison","volume":"37","author":"Shuman","year":"2020","journal-title":"IEEE Signal Process. Mag."},{"doi-asserted-by":"crossref","unstructured":"G\u00f6bel, F., Blanchard, G., and von Luxburg, U. (2018). Construction of tight frames on graphs and application to denoising. Handbook of Big Data Analytics, Springer.","key":"ref_59","DOI":"10.1007\/978-3-319-18284-1_20"},{"unstructured":"de Loynes, B., Navarro, F., and Olivier, B. (2019). Data-Driven Thresholding in Denoising with Spectral Graph Wavelet Transform. arXiv.","key":"ref_60"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1016\/j.acha.2016.05.005","article-title":"Random sampling of bandlimited signals on graphs","volume":"44","author":"Puy","year":"2018","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1016\/j.laa.2010.03.035","article-title":"Quadrature Rule-Based Bounds for Functions of Adjacency Matrices","volume":"433","author":"Benzi","year":"2010","journal-title":"Lin. Alg. Appl."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"1214","DOI":"10.1016\/j.apnum.2007.01.003","article-title":"An Estimator for the Diagonal of a Matrix","volume":"57","author":"Bekas","year":"2007","journal-title":"Appl. Numer. Math."},{"doi-asserted-by":"crossref","unstructured":"Loukas, A., and Foucard, D. (2016, January 7\u20139). Frequency Analysis of Time-Varying Graph Signals. Proceedings of the 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), Washington, DC, USA.","key":"ref_64","DOI":"10.1109\/GlobalSIP.2016.7905861"},{"doi-asserted-by":"crossref","unstructured":"Perraudin, N., Loukas, A., Grassi, F., and Vandergheynst, P. (2017, January 5\u20139). Towards Stationary Time-Vertex Signal Processing. Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA.","key":"ref_65","DOI":"10.1109\/ICASSP.2017.7952890"},{"doi-asserted-by":"crossref","unstructured":"Grady, L.J., and Polimeni, J.R. (2010). Discrete Calculus, Springer.","key":"ref_66","DOI":"10.1007\/978-1-84996-290-2"},{"doi-asserted-by":"crossref","unstructured":"Isufi, E., Loukas, A., Simonetto, A., and Leus, G. (September, January 29). Separable Autoregressive Moving Average Graph-Temporal Filters. Proceedings of the 2016 24th European Signal Processing Conference (EUSIPCO), Budapest, Hungary.","key":"ref_67","DOI":"10.1109\/EUSIPCO.2016.7760238"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/295\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:33:13Z","timestamp":1760178793000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":67,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["a13110295"],"URL":"https:\/\/doi.org\/10.3390\/a13110295","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,11,13]]}}}