Search

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals needed to obtain an e -approximation for the d -variate problem which is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function that depends polynomially on d and logarithmically on e − 1 . The corresponding unweighted problem was studied in Hickernell et al. (2020) with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on d and logarithmic dependence on e − 1 , we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential ( s , t ) -weak tractability with max ( s , t ) ≥ 1 . For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential ( s , t ) -weak tractability with max ( s , t ) 1 is left for future study. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019).

An optimal convergence condition for Newton iteration is presented which is at least as weak as the one obtained by Traub and Woźniakowski leading also to an at least as precise complexity. The novelty of the paper is the introduction of a restricted convergence domain. That is we find a more precise location where the Newton iterates lie than in earlier studies. Consequently the Lipschitz constants are at least as small as the ones used before. This way and under the same computational cost, we extend the local convergence as well as the complexity of Newton iteration. Numerical examples further justify the theoretical results.

Siedlecki and Weimar (2015) defined the notion of ( s , t ) -weak tractability for linear multivariate problems, which holds if the information complexity of the multivariate problem is not exponential in d t and e − s , where d is the number of variables and e is the error threshold with positive s and t . For Hilbert spaces, they were able to characterize ( s , t ) -weak tractability in terms of how quickly the corresponding ordered singular values decay. Using this result, they studied the embedding of H r ( T d ) into L 2 ( T d ) , where T d is the d -dimensional torus, determining precisely when this problem is ( s , t ) -tractable for a given d and r . Their proof is based on deep results of Kuhn et al. (2014), which are complicated by the difficulty of ordering the singular values. In this paper, we provide a new characterization of ( s , t ) -weak tractability of multivariate problems over Hilbert spaces, which does not require us to order the singular values. This allows us to obtain a new, and somewhat simpler, proof of the Siedlecki and Weimar (2015) result that does not need to use the results of Kuhn et al. (2014).

We study approximation properties of sequences of centered random elements X d , d ? N , with values in separable Hilbert spaces. We focus on sequences of tensor product-type random elements, which have covariance operators of corresponding tensor product form. The average case approximation complexity n X d ( e ) is defined as the minimal number of evaluations of arbitrary linear functionals that is needed to approximate X d with relative 2 -average error not exceeding a given threshold e ? ( 0 , 1 ) . The growth of n X d ( e ) as a function of e - 1 and d determines whether a sequence of corresponding approximation problems for X d , d ? N , is tractable or not. Different types of tractability were studied in the paper by Lifshits et?al. (J. Complexity, 2012), where for each type the necessary and sufficient conditions were found in terms of the eigenvalues of the marginal covariance operators. We revise the criterion of quasi-polynomial tractability and provide a simplified version. We illustrate our result by applying it to random elements corresponding to tensor products of squared exponential kernels. We also extend a recent result of Xu (2014) concerning weighted Korobov kernels.

In this paper we study quasi-Monte Carlo integration of smooth functions using digital nets. We fold digital nets over $\mathbb{Z}_{b}$ by means of the $b$-adic tent transformation, which has recently been introduced by the authors, and employ such \emph{folded digital nets} as quadrature points. We first analyze the worst-case error of quasi-Monte Carlo rules using folded digital nets in reproducing kernel Hilbert spaces. Here we need to permit digital nets with "infinite digit expansions," which are beyond the scope of the classical definition of digital nets. We overcome this issue by considering the infinite product of cyclic groups and the characters on it. We then give an explicit means of constructing good folded digital nets as follows: we use higher order polynomial lattice point sets for digital nets and show that the component-by-component construction can find good \emph{folded higher order polynomial lattice rules} that achieve the optimal convergence rate of the worst-case error in certain Sobolev spaces of smoothness of arbitrarily high order.

The paper is concerned with recovery problems of linear multiplier-type operators from noisy information on weighted classes of functions. Optimal methods of recovery are constructed. The dual extremal problem is closely connected with Carlson type inequalities.

The paper deals with linear problems defined on γ -weighted Hilbert spaces of functions with infinitely many variables. The spaces are endowed with zero-mean Gaussian measures which allows to define and study e -truncation and e -superposition dimensions in the average case and probabilistic settings. Roughly speaking, these e -dimensions quantify the smallest number k = k ( e ) of variables that allow to approximate the ∞ -variate functions by special ones that depend on at most k -variables with the average error bounded by e . In the probabilistic setting, given δ ∈ ( 0 , 1 ) , we want the error ≤ e with probability ≥ 1 − δ . We show that the e -dimensions are surprisingly small which, for anchored spaces, leads to very efficient algorithms, including the Multivariate Decomposition Methods.

We study EC- ( s , t ) -weak tractability of multivariate linear problems in the average case setting. This paper extends earlier work in the worst case setting. The parameters s ≥ 0 and t ≥ 0 allow us to study the information complexity n ( e , d ) of a d -variate problem with respect to different powers of ln e − 1 , corresponding to the bits of accuracy, and d . We consider the absolute and normalized error criteria. In particular, a multivariate problem is EC- ( s , t ) -weakly tractable iff lim d + e − 1 → ∞ ln n ( e , d ) ∕ [ d t + ln s e − 1 ] = 0 . We deal with general linear problems and linear tensor product problems. We show necessary and sufficient conditions for EC- ( s , t ) -weak tractability. In the case of general linear problem these conditions are matching. For linear tensor product problems, we also show matching conditions with the exception of some cases where s > 1 , in general.

We mainly study multivariate (uniform or Gaussian) integration defined for integrand spaces Fd such as weighted Sobolev spaces of functions of d variables with smooth mixed derivatives. The weight γj moderates the behavior of functions with respect to the jth variable. For γj≡1, we obtain the classical Sobolev spaces whereas for decreasing γj's the weighted Sobolev spaces consist of functions with diminishing dependence on the jth variables. We study the minimal errors of quadratures that use n function values for the unit ball of the space Fd. It is known that if the smoothness parameter of the Sobolev space is one, then the minimal error is the same as the discrepancy. Let n(ε, Fd) be the smallest n for which we reduce the initial error, i.e., the error with n=0, by a factor ε. The main problem studied in this paper is to determine whether the problem is intractable, i.e., whether n(ε, Fd) grows faster than polynomially in ε−1 or d. In particular, we prove intractability of integration (and discrepancy) if limsupd∑dj=1γj/lnd=∞. Previously, such results were known only for restricted classes of quadratures. For γj≡1, the, following bounds hold for discrepancy •with boundary conditions1.0628d(1+o(1))⩽n(ε, Fd)⩽1.5dε−2,asd→∞,•without boundary conditions1.0463d(1+o(1))⩽n(ε, Fd)⩽1.125dε−2,asd→∞. These results are obtained by analyzing arbitrary linear tensor product functionals Id defined over weighted tensor product reproducing kernel Hilbert spaces Fd of functions of d variables. We introduce the notion of a decomposable kernel. For reproducing kernels that have a decomposable part we prove intractability of all Id with non-zero subproblems with respect to the decomposable part of the kernel, as long as the weights satisfy the condition mentioned above.