Spectrum-adapted polynomial approximation for matrix functions with applications in graph signal processing

Tiffany Fan, David I. Shuman, Shashanka Ubaru, Yousef Saad

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number295
Pages (from-to)1-22
Number of pages22
JournalAlgorithms
Volume13
Issue number11
DOIs
StatePublished - Nov 2020

Keywords

  • Graph spectral filtering
  • Matrix function
  • Orthogonal polynomials
  • Polynomial approximation
  • Spectral density estimation
  • Weighted least squares polynomial regression

Fingerprint Dive into the research topics of 'Spectrum-adapted polynomial approximation for matrix functions with applications in graph signal processing'. Together they form a unique fingerprint.

Cite this