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".
Hu, X., Iwen, M. & Kim, H. Numer. Algor. (2017) 74: 1029.
DOI: 10.1007/s11075-016-0184-x


(see: 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] → ? 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.