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.
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.