Nonlinear function approximation: computing smooth solutions with an adaptive greedy algorithm (Q863343)

Let \(G\) be a set contained in the unit ball of the Hilbert space \(H\). Given an \(f \in H\) and a natural number \(n\), one has to find a good approximation to \(f\) by a linear combination of \(\leq n\) elements of \(G\) in a computationally effective way. The starting point of the paper is a version of the well-known greedy approximation algorithm. It is assumed that \(f \in \overline {\text{co}}( b G) \) for some \(b \in {\mathbb R}\). In the algorithm, elements \(g_k \in bG\) are chosen one after another and approximating elements \(f_k\) are built iteratively, starting with \(f_0=0\), as convex combinations of \(f_{k-1}\) and \(g_k\). To apply the algorithm, one needs to choose some number \(M\) satisfying \(M>b^2-\| f\| ^2\). It can then be proved that \(\| f-f_k\| ^2 \leq M/k\). For practical applications the author suggests a modification of the algorithm which deals with perturbed data \(f^\delta\), \(\| f -f^\delta\| \leq \delta\). Another problem is that the constant \(b\) is usually unknown apriori. To address this issue, an heuristic adaptive greedy algorithm is proposed which does not need \(b\) but rather recovers it iteratively from the available data. The applicability of this algorithm is demonstrated by numerical experiments.