Sparse Legendre expansions via $\ell_1$ minimization
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- A note on guaranteed sparse recovery via -minimizationApplied and Computational Harmonic Analysis, 2010
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Sparsest solutions of underdetermined linear systems via -minimization forApplied and Computational Harmonic Analysis, 2009
- 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
- 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