# NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks

arXiv: https://arxiv.org/abs/1808.04580 · HTML: https://mlsanity.com/paper/1808.04580/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2018.

## Built on by (most cited first, 5 of 5)

- [Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication](https://mlsanity.com/paper/2111.10140/) (2021)
- [A Preconditioned Interior Point Method for Support Vector Machines Using an ANOVA-Decomposition and NFFT-Based Matrix-Vector Products](https://mlsanity.com/paper/2312.00538/) (2023)
- [Joint reconstruction-segmentation on graphs](https://mlsanity.com/paper/2208.05834/) (2022)
- [Graph Laplacian-based Bayesian Multi-fidelity Modeling](https://mlsanity.com/paper/2409.08211/) (2024)
- [PrivateMail: Supervised Manifold Learning of Deep Features With Differential Privacy for Image Retrieval](https://mlsanity.com/paper/2102.10802/) (2021)

## Abstract (arXiv)

The graph Laplacian is a standard tool in data science, machine learning, and image processing. The corresponding matrix inherits the complex structure of the underlying network and is in certain applications densely populated. This makes computations, in particular matrix-vector products, with the graph Laplacian a hard task. A typical application is the computation of a number of its eigenvalues and eigenvectors. Standard methods become infeasible as the number of nodes in the graph is too large. We propose the use of the fast summation based on the nonequispaced fast Fourier transform (NFFT) to perform the dense matrix-vector product with the graph Laplacian fast without ever forming the whole matrix. The enormous flexibility of the NFFT algorithm allows us to embed the accelerated multiplication into Lanczos-based eigenvalues routines or iterative linear system solvers and even consider other than the standard Gaussian kernels. We illustrate the feasibility of our approach on a number of test problems from image segmentation to semi-supervised learning based on graph-based PDEs. In particular, we compare our approach with the Nystr"om method. Moreover, we present and test an enhanced, hybrid version of the Nystr"om method, which internally uses the NFFT.