Sparse approximation and recovery by greedy algorithms in Banach spaces (Q2879425)

Let \(X\) be a real Banach space with dual \(X^*\) and unit sphere \(S_X.\) For \(g\in X,\, g\neq 0,\) one denotes by \(F_g\) the element of \(S_{X^*}\) satisfying \(F_g(g)=\|g\|\).NEWLINENEWLINEA subset \(\mathcal D\) of \(S_X\) is called a dictionary if the linear subspace generated by \(\mathcal D\) is dense in \(X\). An element \(f\in X\) is called \(m\)-sparse if it has a representation \(f=\sum_{i=1}^mx_ig_i\) with \(g_i\in \mathcal D,\, i=1,\dots,m\). The set of all \(m\)-sparse elements is denoted by \(\Sigma_m(\mathcal D)\) and, for \(f_0\in X,\) let \(\sigma_m(f_0,\mathcal D)=\inf \{\|f-f_0\| : f\in\Sigma_m(\mathcal D)\). The main problem considered in the paper is to design a practical algorithm that builds sparse approximations comparable to the best \(m\)-term approximations. The author studies the weak Chebyshev greedy algorithm (WCGA), which in the Hilbert space case coincides with the weak orthogonal matching pursuit (WOMP). The WCGA is defined in the following way. For fixed \(t\in (0,1)\) and \(f_0\in X\) one follows the following steps: (1) choose \(\varphi_m\in \mathcal D\) such that \(|F_{f_{m-1}}(\varphi_m)|\geq t\sup\{|F_{f_{m-1}}(g)| : g\in \mathcal D\}\); (2) define \(\Phi_m=\) span\(\{\varphi_j\}_{j=1}^m\) and let \(G_m\) be the best approximant of \(f_0\) in \(\Phi_m\); (3) put \(f_m=f_0-G_m\). The author proves Lebesgue-type inequalities and gives evaluations of \(\|f_m\|\) in the case when the Banach space is uniformly smooth with order of smoothness of power \(p\). As application one considers the sparse approximation with respect to the real trigonometric system \(1,\sin2\pi x,\cos2\pi x,\dots,\) normalized in \(L_p[0,1].\) One shows that the WCGA provides almost optimal sparse approximation for the trigonometric system in \(L_p[0,1]\), \(1\leq p<\infty\).NEWLINENEWLINEA good presentation of greedy algorithms and their applications is given in the book by \textit{V. Temlyakov}, [Greedy approximation, Cambridge Monographs on Applied and Computational Mathematics 20. Cambridge: Cambridge University Press (2011; Zbl 1279.41001)].