TY - JOUR
T1 - Spectrum-adapted polynomial approximation for matrix functions with applications in graph signal processing
AU - Fan, Tiffany
AU - Shuman, David I.
AU - Ubaru, Shashanka
AU - Saad, Yousef
N1 - Publisher Copyright:
© 2020 by the authors. Licensee MDPI, Basel, Switzerland..
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/11
Y1 - 2020/11
N2 - 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.
AB - 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.
KW - Graph spectral filtering
KW - Matrix function
KW - Orthogonal polynomials
KW - Polynomial approximation
KW - Spectral density estimation
KW - Weighted least squares polynomial regression
UR - http://www.scopus.com/inward/record.url?scp=85096425840&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096425840&partnerID=8YFLogxK
U2 - 10.3390/a13110295
DO - 10.3390/a13110295
M3 - Article
AN - SCOPUS:85096425840
VL - 13
SP - 1
EP - 22
JO - Algorithms
JF - Algorithms
SN - 1999-4893
IS - 11
M1 - 295
ER -