Nonlinear function approximation: Computing smooth solutions with an adaptive greedy algorithm

In contrast to linear schemes, nonlinear approximation techniques allow for dimension independent rates of convergence. Unfortunately, typical algorithms (such as, e.g., backpropagation) are not only computationally demanding, but also unstable in the presence of data noise. While we can show stability for a weak relaxed greedy algorithm, the resulting method has the drawback that it requires in practise unavailable smoothness information about the data.In this work we propose an adaptive greedy algorithm which does not need this information but rather recovers it iteratively from the available data. We show that the generated approximations are always at least as smooth as the original function and that the algorithm also remains stable, when it is applied to noisy data. Finally, the applicability of this algorithm is demonstrated by numerical experiments.