2019/03/26 by Yuhan Ding, Ding, Yuhan, Fred J. Hickernell +5
Mathematics · #FOS: Mathematics #Mathematical Approximation and Integration #Numerical Analysis (math.NA) #Numerical methods in inverse problems #Statistical and numerical algorithms
paper · pdf · doi:10.48550/arxiv.1903.10738
openalex publication_date 2019/03/26 · openalex created_date 2019/04/01 · openalex updated_date 2026/08/01
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.