We extend compressive sensing results concerning the recovery of sparse trigonometric polynomials from few point samples to the recovery of polynomials having a sparse expansion in  Legendre basis.  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 measure.  As an efficient recovery method, l1 minimization can be used.

This is joint work with Holger Rauhut.