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, l1-minimization can be used. We establish these results by showing the restricted isometry property of a preconditioned random Legendre matrix. We further consider approximate recovery of functions in certain infinite-dimensional function spaces associated to the Legendre polynomial system. 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.

This publication has 32 references indexed in Scilit: