Analysis of sparse recovery for Legendre expansions using envelope bound
For researchers working on sparse recovery with Legendre polynomials, this work removes a key limitation of existing theory by providing meaningful guarantees where previous conditions failed.
The paper provides new sufficient conditions for the uniform recovery of sparse Legendre expansions using ℓ1 minimization, achieving a sample complexity of m ≳ s² × log factors that is independent of the uniform bound Θ, which previously made such guarantees meaningless. This is the first recovery condition for orthonormal systems without assuming uniform boundedness of the sampling matrix.
We provide novel sufficient conditions for the uniform recovery of sparse Legendre expansions using $\ell_1$ minimization, where the sampling points are drawn according to orthogonalization (uniform) measure. So far, conditions of the form $m \gtrsim Θ^2 s \times \textit{log factors}$ have been relied on to determine the minimum number of samples $m$ that guarantees successful reconstruction of $s$-sparse vectors when the measurement matrix is associated to an orthonormal system. However, in case of sparse Legendre expansions, the uniform bound $Θ$ of Legendre systems is so high that these conditions are unable to provide meaningful guarantees. In this paper, we present an analysis which employs the envelop bound of all Legendre polynomials instead, and prove a new recovery guarantee for $s$-sparse Legendre expansions, $$ m \gtrsim {s^2} \times \textit{log factors}, $$ which is independent of $Θ$. Arguably, this is the first recovery condition established for orthonormal systems without assuming the uniform boundedness of the sampling matrix. The key ingredient of our analysis is an extension of chaining arguments, recently developed in [Bou14,CDTW15], to handle the envelope bound. Furthermore, our recovery condition is proved via restricted eigenvalue property, a less demanding replacement of restricted isometry property which is perfectly suited to the considered scenario. Along the way, we derive simple criteria to detect good sample sets. Our numerical tests show that sets of uniformly sampled points that meet these criteria will perform better recovery on average.