Search

Abstract In this paper, we investigate optimal linear approximations (n -approximation numbers) of the embeddings from the Sobolev spaces H r (r > 0) for various equivalent norms and the Gevrey type spaces G α , β (α , β > 0) on the sphere S d and on the ball B d , where the approximation error is measured in the L 2 -norm. We obtain preasymptotics, asymptotics, and strong equivalences of the above approximation numbers as a function in n and the dimension d. We emphasize that all equivalence constants in the above preasymptotics and asymptotics are independent of the dimension d and n. As a consequence we obtain that for the absolute error criterion the approximation problems I d : H r → L 2 are weakly tractable if and only if r > 1 , not uniformly weakly tractable, and do not suffer from the curse of dimensionality. We also prove that for any α , β > 0 , the approximation problems I d : G α , β → L 2 are uniformly weakly tractable, not polynomially tractable, and quasi-polynomially tractable if and only if α ≥ 1. [ABSTRACT FROM AUTHOR]

In this paper we study tractability properties of the weighted star discrepancy with general coefficients of centered regular grids with different mesh-sizes. We give exact characterizations of the weight sequences ( γ j ) j ≥ 1 such that the regular grid with different mesh-sizes achieves weak, uniform weak, quasi polynomial, polynomial or strong polynomial tractability for the γ -weighted star discrepancy. For example, a necessary and sufficient condition such that the regular grid with different mesh-sizes achieves weak tractability for the γ -weighted star discrepancy is lim j → ∞ j γ j = 0 . [ABSTRACT FROM AUTHOR]

Abstract: This is a follow-up paper of “Liberating the dimension for function approximation”, where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak’s construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information. [Copyright &y& Elsevier]

Abstract: Many papers study polynomial tractability for multivariate problems. Let be the minimal number of information evaluations needed to reduce the initial error by a factor of for a multivariate problem defined on a space of -variate functions. Here, the initial error is the minimal error that can be achieved without sampling the function. Polynomial tractability means that is bounded by a polynomial in and and this holds for all . In this paper we study generalized tractability by verifying when can be bounded by a power of for all , where can be a proper subset of . Here is a tractability function, which is non-decreasing in both variables and grows slower than exponentially to infinity. In this article we consider the set for some and . We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does. [Copyright &y& Elsevier]

In this paper, we study tractability of L 2 -approximation of one-periodic functions from weighted Korobov spaces in the worst-case setting. The considered weights are of product form. For the algorithms we allow information from the class Λ all consisting of all continuous linear functionals and from the class Λ std , which only consists of function evaluations. We provide necessary and sufficient conditions on the weights of the function space for quasi-polynomial tractability, uniform weak tractability, weak tractability and (σ , τ) -weak tractability. Together with the already known results for strong polynomial and polynomial tractability, our findings provide a complete picture of the weight conditions for all current standard notions of tractability. [ABSTRACT FROM AUTHOR]

Abstract: We want to compute a worst case -approximation to the solution of the Helmholtz equation over the unit -cube , subject to Neumann boundary conditions on . We measure error in the -norm. Let denote the minimal number of evaluations of , , and needed to compute an absolute or normalized -approximation, assuming that , , and vary over balls of weighted reproducing kernel Hilbert spaces. This problem is said to be weakly tractable if grows subexponentially in and . It is said to be polynomially tractable if is polynomial in and , and strongly polynomially tractable if this polynomial is independent of . We have previously studied tractability for the homogeneous version of this problem. In this paper, we investigate the tractability of the non-homogeneous problem, with general . Using new perturbation estimates having explicit constants, we are able to relate the tractability of this problem to that of the -approximation problem. First, suppose that we use product weights, in which the role of any variable is moderated by its particular weight. We then find that if the sum of the weights is sublinearly bounded, then the problem is weakly tractable; moreover, this condition is more or less necessary. We then show that the problem is polynomially tractable if the sum of the weights is logarithmically or uniformly bounded, and we estimate the exponents of tractability for these two cases. Next, we turn to finite-order weights of fixed order , in which a -variate function can be decomposed as a sum, each term depending on at most variables. We show that the problem is always polynomially tractable for finite-order weights, and we give estimates for the exponents of tractability. Since our results so far have established nothing stronger than polynomial tractability, we look more closely at whether strong polynomial tractability is possible. We show that our problem is never strongly polynomially tractable for the absolute error criterion. Moreover, we believe that the same is true for the normalized error criterion, but we have been able to prove this lack of strong tractability only when certain conditions hold on the weights. Finally, we use the Korobov and min kernels, along with product weights, to illustrate our results. [Copyright &y& Elsevier]

Multivariate integration of high dimension s occurs in many applications. In many such applications, for example in finance, integrands can be well approximated by sums of functions of just a few variables. In this situation the superposition (or effective) dimension is small, and we can model the problem with finite-order weights, where the weights describe the relative importance of each distinct group of variables up to a given order (where the order is the number of variables in a group), and ignore all groups of variables of higher order.In this paper we consider multivariate integration for the anchored and unanchored (non-periodic) Sobolev spaces equipped with finite-order weights. Our main interest is tractability and strong tractability of QMC algorithms in the worst-case setting. That is, we want to find how the minimal number of function values needed to reduce the initial error by a factor ϵ depends on s and ϵ−1. If there is no dependence on s, and only polynomial dependence on ϵ−1, we have strong tractability, whereas with polynomial dependence on both s and ϵ−1 we have tractability.We show that for the anchored Sobolev space we have strong tractability for arbitrary finite-order weights, whereas for the unanchored Sobolev space we have tractability for all bounded finite-order weights. In both cases, the dependence on ϵ−1 is quadratic. We can improve the dependence on ϵ−1 at the expense of polynomial dependence on s. For finite-order weights, we may achieve almost linear dependence on ϵ−1 with a polynomial dependence on s whose degree is proportional to the order of the weights.We show that these tractability bounds can be achieved by shifted lattice rules with generators computed by the component-by-component (CBC) algorithm. The computed lattice rules depend on the weights. Similar bounds can also be achieved by well-known low discrepancy sequences such as Halton, Sobol and Niederreiter sequences which do not depend on the weights. We prove that these classical low discrepancy sequences lead to error bounds with almost linear dependence on n−1 and polynomial dependence on d. We present explicit worst-case error bounds for shifted lattice rules and for the Niederreiter sequence. Better tractability and error bounds are possible for finite-order weights, and even for general weights if they satisfy certain conditions. We present conditions on general weights that guarantee tractability and strong tractability of multivariate integration. [Copyright &y& Elsevier]