Affordable Access

Fast Multiscale Diffusion on Graphs

Authors
  • Marcotte, Sibylle
  • Barbe, Amélie
  • Gribonval, Rémi
  • Vayer, Titouan
  • Sebban, Marc
  • Borgnat, Pierre
  • Gonçalves, Paulo
Publication Date
Apr 29, 2021
Source
HAL-INRIA
Keywords
Language
English
License
Unknown
External links

Abstract

Diffusing a graph signal at multiple scales requires computing the action of the exponential of several multiples of the Laplacian matrix. We tighten a bound on the approximation error of truncated Chebyshev polynomial approximations of the exponential, hence significantly improving a priori estimates of the polynomial order for a prescribed error. We further exploit properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus reducing drastically its computational cost.

Report this publication

Statistics

Seen <100 times