Fast multiscale regularization methods for high-order numerical differentiation

The first-order and higher-order derivatives of a function can be viewed as the solutions of Volterra integral equations of the first kind. In this paper we propose a fast multiscale solver for the numerical solution of the Tikhonov regularization of the Volterra equations. In association with the special form of the kernels, the matrices resulting from the discretization by multiscale bases are sparse. Moreover, they can be truncated using proper strategies with only a minor loss of accuracy. In the best case, the number of nonzero entries of the truncated matrices is linear with respect to the dimensions of the matrices. The accuracy of the solution from the solver is analysed theoretically and verified by numerical experiments.