Rapidly computing sparse Legendre expansions via sparse Fourier transforms
"Rapidly computing sparse Legendre expansions via sparse Fourier transforms".
Hu, X., Iwen, M. & Kim, H. 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] → ? 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 Ω(NlogN)-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.