Sparse Legendre expansions via ${\ell }_1$ minimization

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.

20 pages, 4 figures

References in corpus (5)

• Sparsity and Incoherence in Compressive Sampling
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Sparse recovery for spherical harmonic expansions
• On the complexity of Mumford-Shah type regularization, viewed as a relaxed sparsity constraint

Cited by in corpus (2)

• The restricted isometry property for time-frequency structured random matrices
• Restricted Isometries for Partial Random Circulant Matrices