Sparse Legendre expansions via $\ell_1$ minimization

Authors:
  • HRHolger Rauhut
    Holger Rauhut
  • RWRachel Ward
    Rachel Ward

Abstract
We consider the recovery of polynomials that are sparse with respect to the basis of Legendre polynomials from a small number of random sampling points. We show that a Legendre s-sparse polynomial of maximal degree N can be recovered from m = O(s log^4(N)) random samples that are chosen independently according to the Chebyshev probability measure on [-1,1]. As an efficient recovery method, $\ell_1$-minimization can be used. We establish these results by showing the restricted isometry property of a preconditioned random Legendre matrix. Our results extend to a large class of orthogonal polynomial systems. As a byproduct, we obtain condition number estimates for preconditioned random Legendre matrices that should be of interest on their own.