Rapidly Computing Sparse Legendre Expansions via Sparse Fourier Transforms

  • May 2, 2017
  • News, Publications

Article:

"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

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