7. Adaptive approximation for multivariate linear problems with inputs lying in a cone

7. 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 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.

我们研究一般多元线性问题的自适应逼近算法，其中输入函数集为非凸锥。虽然已知对于凸输入集，自适应算法的性能实质上并不比非自适应算法好，但对于非凸集情况可能不同。这里考虑的一个典型例子是基于级数展开的函数逼近。给定一个误差容限，我们利用输入的级数系数来构造一个近似解，使得误差不超过这个容限。我们研究了基于先导样本能够界定输入范数的情况，以及跟踪输入级数系数衰减率的情况。此外，我们考虑了推断坐标和平滑度重要性有意义的情况。除了进行误差分析，我们还研究了算法的信息成本和问题的计算复杂度，并确定了可以避免维数灾难的条件。