Adaptive Approximation for Multivariate Linear Problems with Inputs Lying in a Cone
For researchers in approximation theory and numerical analysis, this work extends adaptive approximation theory to non-convex input cones, a previously underexplored area.
This paper studies adaptive approximation algorithms for multivariate linear problems with non-convex input sets, showing that adaptivity can outperform non-adaptive methods in this setting. The authors propose algorithms that adapt based on series coefficients and pilot samples, and identify conditions to avoid the curse of dimensionality.
We study adaptive approximation algorithms for general multivariate linear problems where the sets of input functions are non-convex cones. While it is known that adaptive algorithms perform essentially no better than non-adaptive algorithms for convex input sets, the situation may be different for non-convex sets. A typical example considered here is function approximation based on series expansions. Given an error tolerance, we use series coefficients of the input to construct an approximate solution such that the error does not exceed this tolerance. We study the situation where we can bound the norm of the input based on a pilot sample, and the situation where we keep track of the decay rate of the series coefficients of the input. Moreover, we consider situations where it makes sense to infer coordinate and smoothness importance. Besides performing an error analysis, we also study the information cost of our algorithms and the computational complexity of our problems, and we identify conditions under which we can avoid a curse of dimensionality.