A Fast Algorithm for Numerical Differentiation from Scattered Data

Numerical differentiation from scattered data is a problem often encountered in many fields such as image processing and numerical solution of differential equations. We propose a fast algorithm for numerical differentiation starting from scattered data. The proposed algorithm uses nonuniform Fast Fourier Transform (nFFT) and the explicit expression of the eigensystem of a Fredholm integral operator associated to the differentiation problem. Several numerical experiments are presented to validate the behaviour of the proposed algorithm with exact data and with noise-contaminated data.