Sparse Legendre expansions via l1-minimization

Holger Rauhut, Rachel Ward

Abstract

We consider the problem of recovering polynomials that are sparse with respect to the basis of Legendre polynomials from a small number of random samples. In particular, we show that a Legendre s -sparse polynomial of maximal degree N can be recovered from m ≍ s log 4 ( N ) random samples that are chosen independently according to the Chebyshev probability measure d ν ( x ) = π − 1 ( 1 − x 2 ) − 1 / 2 d x . As an efficient recovery method, ℓ 1 -minimization can be used. We establish these results by verifying the restricted isometry property of a preconditioned random Legendre matrix. We then extend these results to a large class of orthogonal polynomial systems, including the Jacobi polynomials, of which the Legendre polynomials are a special case. Finally, we transpose these results into the setting of approximate recovery for functions in certain infinite-dimensional function spaces.
BibTeX
@article{rauhut2012sparse,
  author = {Holger Rauhut and Rachel Ward},
  title = {{Sparse Legendre expansions via l1-minimization}},
  journal = {J. Approx. Theory},
  year = {2012},
  url = {https://openreview.net/forum?id=IXWC9_HBmRh},
}

Loading related content...

Figure