Analysis of sparse recovery for Legendre expansions using envelope bound. Issue 6 (10th March 2022)

• Record Type: Journal Article
• Authors: Tran, Hoang; Webster, Clayton
• Other Names: Bochev Pavel guestEditor.; D'Elia Marta guestEditor.; Du Qiang guestEditor.; Hou Steve guestEditor.; Webster Clayton guestEditor.; Zhang Guannan guestEditor.
• Is Part Of: Numerical methods for partial differential equations. Volume 38:Issue 6(2022)
• Page Start: 2163
• Page End: 2198
• Publication Date: 2022-03-10
• Subjects: approximation theory -- compressed sensing -- Legendre expansions; Differential equations, Partial -- Numerical solutions -- Periodicals; 515.353
• DOI: 10.1002/num.22877
• Languages: English
• ISSNs: 0749-159X

Abstract

Abstract: We provide novel sufficient conditions for the uniform recovery of sparse Legendre expansions using ℓ 1 minimization, where the sampling points are drawn according to orthogonalization (uniform) measure. So far, conditions of the form m ≳ Θ 2 s × 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 ≳ s 2 × 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 Bourgain and Chkifa et al., 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.