Lausanne EPFL Ecole Polytechnique

Signal-processing on graphs has developed into a very active field of research during the last decade. In particular, the number of applications using frames con-structed from graphs, like wavelets on graphs, has substantially increased. To at-tain scalability for large graphs, fast graph-signal filtering techniques are needed. In this contribution, we propose an accelerated algorithm based on the Lanczos method that adapts to the Laplacian spectrum without explicitly computing it. The result is an accurate, robust, scalable and efficient algorithm. Compared to existing methods based on Chebyshev polynomials, our solution achieves higher accuracy without increasing the overall complexity significantly. Furthermore, it is particu-larly well suited for graphs with large spectral gaps. 1 Index terms — Spectral graph theory, graph signal-processing, graph filter, Chebyshev polynomial, Lanczos method