Fast Interpolation and Fourier Transform in High-Dimensional Spaces

In scientific computing, the problem of finding an analytical representation of a given function f : Omega subset of R-m -> R, C is ubiquitous. The most practically relevant representations are polynomial interpolation and Fourier series. In this article, we address both problems in highdimensional spaces. First, we propose a quadratic-time solution of the Multivariate Polynomial Interpolation Problem (PIP), i.e., the N(m, n) coefficients of a polynomial Q, with deg(Q) <= n, uniquely fitting f on a determined set of generic nodes P subset of R-m are computed in O(N(m, n)(2)) time requiring storage in O( mN(m, n)). Then, we formulate an algorithm for determining the N(m, n) Fourier coefficients with positive frequency of the Fourier series of f up to order n in the same amount of computational time and storage. Especially in high dimensions, this provides a fast Fourier interpolation, outperforming modern Fast Fourier Transform methods. We expect that these fast and scalable solutions of the polynomial and Fourier interpolation problems in high-dimensional spaces are going to influence modern computing techniques occurring in Big Data and Data Mining, Deep Learning, Image and Signal Analysis, Cryptography, and Non-linear Optimization.