Tractability of multivariate problems for standard and linear information in the worst case setting: part II
For researchers in multivariate approximation and information-based complexity, this work clarifies necessary and sufficient conditions for QPT with standard information, extending previous results.
The paper proves quasi-polynomial tractability (QPT) for linear tensor product problems in the worst case setting using only function values, under three specific assumptions about the univariate case. The first two assumptions are necessary for QPT, and the third is necessary for some Hilbert spaces.
We study QPT (quasi-polynomial tractability) in the worst case setting for linear tensor product problems defined over Hilbert spaces. We assume that the domain space is a reproducing kernel Hilbert space so that function values are well defined. We prove QPT for algorithms that use only function values under the three assumptions: 1) the minimal errors for the univariate case decay polynomially fast to zero, 2) the largest singular value for the univariate case is simple and 3) the eigenfunction corresponding to the largest singular value is a multiple of the function value at some point. The first two assumptions are necessary for QPT. The third assumption is necessary for QPT for some Hilbert spaces.