  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 = O(s log^4(N)) random samples that are chosen
independently according to the Chebyshev probability measure. As an efficient
recovery method, l1-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.
