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

In this paper we define a notion of uniform distribution and discrepancy of sequences in an abstract set E through reproducing kernel Hilbert spaces of functions on E. In the case of the finite-dimensional unit cube these discrepancies are very closely related to the worst case error obtained for numerical integration of functions in a reproducing kernel Hilbert space. In the compact case we show that the discrepancy tends to zero if and only if the sequence is uniformly distributed in our sense. Next we prove an existence theorem for such uniformly distributed sequences and investigate the relation to the classical notion of uniform distribution. Some examples conclude this paper.

Regression problems with multiple functional predictors have been studied previously. In this paper, we investigate functional quantile linear regression with multiple functional predictors within the framework of reproducing kernel Hilbert spaces. The estimation procedure is based on an l 1 -mixed-norm penalty. The learning rate of the estimator in prediction loss is established and a lower bound on the learning rate is also presented that matches the upper bound up to a logarithmic term.

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.

We study approximation properties of sequences of centered random elements $X_d$, $d\in\mathbb N$, with values in separable Hilbert spaces. We focus on sequences of tensor product-type and, in particular, degree-type random elements, which have covariance operators of corresponding tensor form. The average case approximation complexity $n^{X_d}(\varepsilon)$ is defined as the minimal number of continuous linear functionals that is needed to approximate $X_d$ with relative $2$-average error not exceeding a given threshold $\varepsilon\in(0,1)$. In the paper we investigate $n^{X_d}(\varepsilon)$ for arbitrary fixed $\varepsilon\in(0,1)$ and $d\to\infty$. Namely, we find criteria of (un)boundedness for $n^{X_d}(\varepsilon)$ on $d$ and of tending $n^{X_d}(\varepsilon)\to\infty$, $d\to\infty$, for any fixed $\varepsilon\in(0,1)$. In the latter case we obtain necessary and sufficient conditions for the following logarithmic asymptotics \begin{eqnarray*} \ln n^{X_d}(\varepsilon)= a_d+q(\varepsilon)b_d+o(b_d),\quad d\to\infty, \end{eqnarray*} at continuity points of a non-decreasing function $q\colon (0,1)\to\mathbb R$. Here $(a_d)_{d\in\mathbb N}$ is a sequence and $(b_d)_{d\in\mathbb N}$ is a positive sequence such that $b_d\to\infty$, $d\to\infty$. Under rather weak assumptions, we show that for tensor product-type random elements only special quantiles of self-decomposable or, in particular, stable (for tensor degrees) probability distributions appear as functions $q$ in the asymptotics. We apply our results to the tensor products of the Euler integrated processes with a given variation of smoothness parameters and to the tensor degrees of random elements with regularly varying eigenvalues of covariance operator., Comment: 39 pages, 0 figures

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.

Hinrichs (2009) [3] recently studied multivariate integration defined over reproducing kernel Hilbert spaces in the randomized setting and for the normalized error criterion. In particular, he showed that such problems are strongly polynomially tractable if the reproducing kernels are pointwise nonnegative and integrable. More specifically, let n^r^a^n(@e,INT"d) be the minimal number of randomized function samples that is needed to compute [email protected] for the d-variate case of multivariate integration. Hinrichs proved that n^r^a^n(@e,INT"d)@[email protected][email protected]([email protected])^[email protected]?for [email protected]@?(0,1) and [email protected]?N. In this paper we prove that the exponent 2 of @e^-^1 is sharp for tensor product Hilbert spaces whose univariate reproducing kernel is decomposable and univariate integration is not trivial for the two parts of the decomposition. More specifically we have n^r^a^n(@e,INT"d)>[email protected]?18([email protected])^[email protected]?for [email protected]@?(0,1) and d>[email protected]^-^[email protected]^-^1, where @[email protected]?[1/2,1) depends on the particular space. We stress that these estimates hold independently of the smoothness of functions in a Hilbert space. Hence, even for spaces of very smooth functions the exponent of strong polynomial tractability must be 2. Our lower bounds hold not only for multivariate integration but for all linear tensor product functionals defined over a Hilbert space with a decomposable reproducing kernel and with a non-trivial univariate functional for the two spaces corresponding to decomposable parts. We also present lower bounds for reproducing kernels that are not decomposable but have a decomposable part. However, in this case it is not clear if the lower bounds are sharp.

This paper investigates some properties of multi-scale kernels, mainly those which are related to their native spaces and make the corresponding integral operators well defined in the Lp context. In the case p=2, we derive results related to the range of the operators, alternative representations, computation of their norms, basic spectral analysis and isolated properties involving the native spaces of the kernels. Even being not compact, the integral operators possess interesting properties which are peculiar to compact operators.

We want to compute a worst case @e-approximation to the solution of the Helmholtz equation [email protected]+qu=f over the unit d-cube I^d, subject to Neumann boundary conditions @?"@nu=g on @?I^d. We measure error in the H^1(I^d)-norm. Let card(@e,d) denote the minimal number of evaluations of f, g, and q needed to compute an absolute or normalized @e-approximation, assuming that f, g, and q vary over balls of weighted reproducing kernel Hilbert spaces. This problem is said to be weakly tractable if card(@e,d) grows subexponentially in @e^-^1 and d. It is said to be polynomially tractable if card(@e,d) is polynomial in @e^-^1 and d, and strongly polynomially tractable if this polynomial is independent of d. We have previously studied tractability for the homogeneous version g=0 of this problem. In this paper, we investigate the tractability of the non-homogeneous problem, with general g. Using new perturbation estimates having explicit constants, we are able to relate the tractability of this problem to that of the L"2(I^d)-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 @w, in which a d-variate function can be decomposed as a sum, each term depending on at most @w 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.

In this paper, we present a new technique for bounding local Rademacher averages of function classes induced by a loss function and a reproducing kernel Hilbert space (RKHS). At the heart of this technique lies the observation that certain expectations of random entropy numbers can be bounded by the eigenvalues of the integral operator associated with the RKHS. We then work out the details of the new technique by establishing two new oracle inequalities for support vector machines, which complement and generalize previous results.

Recently, a new iterative method, called Newton–Lavrentiev regularization (NLR) method, was considered by George (2006) for regularizing a nonlinear ill-posed Hammerstein-type operator equation in Hilbert spaces. In this paper we introduce a modified form of the NLR method and derive order optimal error bounds by choosing the regularization parameter according to the adaptive scheme considered by Pereverzev and Schock (2005).

In the present paper, we investigate the estimates for the covering number of a ball in a Mercer kernel Hilbert space on [0,1]. Let P"l(x) be the Legendre orthogonal polynomial of order l, a"l>0 be real numbers satisfying @?"l"="0^+^~la"l

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.

This paper deals with the worst case setting for approximating multivariate tensor product linear operators defined over Hilbert spaces. Approximations are obtained by using a number of linear functionals from a given class of information. We consider the three classes of information: the class of all linear functionals, the Fourier class of inner products with respect to given orthonormal elements, and the standard class of function values. We wish to determine which problems are tractable and which are strongly tractable. The complete analysis is provided for approximating operators of rank two or more. The problem of approximating linear functionals is fully analyzed in the first two classes of information. For the third class of standard information we show that the possibilities are very rich. We prove that tractability of linear functionals depends on the given space of functions. For some spaces all nontrivial normed linear functionals are intractable, whereas for other spaces all linear functionals are tractable. In “typical” function spaces, some linear functionals are tractable and some others are not.