Adaptive approximation for multivariate linear problems with inputs lying in a cone
We study adaptive approximation algorithms for general multivariate linear problems, where the sets of input functions are nonconvex cones. Whereas it is known that adaptive algorithms perform essentially no better than nonadaptive algorithms for convex and symmetric input sets, the situation may be different for nonconvex sets. The setting 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 derive upper bounds on the information cost of our algorithms and lower bounds on the computational complexity of our problems, and we identify conditions, under which we can avoid a curse of dimensionality.
