Rapidly Computing Sparse Legendre Expansions via Sparse Fourier Transforms

Rapidly computing sparse Legendre expansions via sparse Fourier transforms


"Rapidly Computing Sparse Legendre Expansions via Sparse Fourier Transforms" 
Xianfeng Hu, Mark Iwen, Hyejin Kim

Numer. Algor. (2017) 74: 1029.
DOI: 10.1007/s11075-016-0184-x

Link: http://users.math.msu.edu/users/markiwen/Papers/Legendre_SUBMITTED.pdf

In this paper we propose a general strategy for rapidly computing sparse Legendre expansions. The resulting methods yield a new class of fast algorithms capable of approximating a given function f : [−1, 1] → R with a near-optimal linear combination of s Legendre polynomials of degree ≤ N in just (s log N)O(1)-time. When s « N these algorithms exhibit sublinear runtime complexities in N, as opposed to traditional Omega(N log N)-time methods for computing all of the first N Legendre coefficients of f. Theoretical as well as numerical results demonstrate the effectiveness of the proposed methods.