Sparse Legendre expansions via \(\ell_1\)-minimization (Q420755)

If \(L_n\) are the Legendre polynomials, a real-valued polynomial \[ g(x) = \sum_{n=0}^{N-1} c_n\, L_n(x)\,,\quad (x\in [-1,\,1]) \] is called \textit{Legendre \(s\)-sparse}, if only \(s\) coefficients \(c_n\) do not vanish. In this interesting paper, the authors show that a Legendre \(s\)-sparse polynomial \(g\) of maximal degree \(N-1\) can be recovered from \(m \asymp s\,(\log s)^3\,\log N\) random samples \(x_j \in [-1,\,1]\) that are chosen independently according to the Chebyshev measure \(d\nu (x) = \pi^{-1} \,(1-x^2)^{-1/2}\,dx\). The reconstruction is robust, if the sampled data \(g(x_j)\) are corrupted by noise. This result is based on the restricted isometry property of the preconditioned Legendre matrix \[ \mathrm{diag}\,(a_j)_{j=1}^m\, \big(L_{k-1}(x_j)\big)_{j,k=1}^{m,N} \] with \(a_j = (\pi/2)^{1/2}\,(1-x_j^2)^{1/4}\). As an efficient recovery method, \(\ell_1\)-minimization can be used. Further, these results are extended to a large class of orthogonal polynomials (including Jacobi polynomials). Finally, it is shown that a continuous function of a weighted Wiener type space can be approximated by a Legendre \(s\)-sparse polynomial.