Compressive sensing has triggered significant research activity in recent years. It predicts that sparse signals can be recovered from what was previously believed to be highly incomplete information. One of the main results in compressed sensing can be interpreted as follows: any trigonometric polynomial of degree N which is s-sparse, or has at most s nonzero coefficients, may be efficiently recovered from O(s log4(N)) uniformly distributed point samples on the domain. In this talk, we extend the scope of compressive sensing to the recovery of polynomials with a sparse expansion in Legendre basis. In particular, we show that a Legendre s-sparse polynomial of maximal degree N can be recovered from O(s log4(N)) random samples that are chosen independently according to the Chebyshev probability measure. As a byproduct, we obtain condition number estimates for preconditioned random Legendre matrices that should be of interest on their own. Finally, we discuss generalizations of our results to the recovery of sparse spherical harmonic expansions from randomly located samples on the sphere. Sparse spherical harmonic expansions were recently exploited with good numerical success in the spherical inpainting problem for the cosmic microwave background, but so far this problem had lacked a theoretical understanding.
This is joint work with Holger Rauhut.