Approximate factorizations of Fourier matrices with nonequispaced knots Original Research Article

We propose a new algorithm for the multiplication of vectors with Fourier matrices of the form Atf=(e−2πixkvj/N)N/2−1j,k=−N/2, where both xk and vj are arbitrary knots in [−N/2,N/2). The algorithm is based on an approximate factorization of the transform matrix Atf into sparse matrices which entries are chosen to minimize the Frobenius norm of certain error matrices. Numerical experiments demonstrate that the approximation error introduced by our new algorithm is about 102 times smaller than the approximation error of previously reported algorithms with the Gaussian or B-splines as window functions and as good as a previous algorithm with the Kaiser–Bessel function as window function.