Sparse Legendre expansions via $\ell_1$ minimization
Preprint
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.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Sparsity in Time-Frequency RepresentationsJournal of Fourier Analysis and Applications, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching PursuitFoundations of Computational Mathematics, 2008
- On the Impossibility of Uniform Sparse Reconstruction using Greedy MethodsSampling Theory in Signal and Image Processing, 2008
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 2008
- On sparse reconstruction from Fourier and Gaussian measurementsCommunications on Pure and Applied Mathematics, 2007
- On the Erdelyi-Magnus-Nevai Conjecture for Jacobi PolynomialsConstructive Approximation, 2007
- Random sampling of sparse trigonometric polynomialsApplied and Computational Harmonic Analysis, 2007
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- FFTs for the 2-Sphere-Improvements and VariationsJournal of Fourier Analysis and Applications, 2003