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

We show that if the Generalized Riemann Hypothesis is true, the problem of deciding whether a system of polynomial equations in several complex variables has a solution is in the second level of the polynomial hierarchy. In fact, this problem is in AM, the ``Arthur-Merlin'''' class (recall that $\np \subseteq \am \subseteq \rp^{\tiny \np} \subseteq \Pi_2$). The best previous bound was PSPACE. An earlier version of this paper was distributed as NeuroCOLT Technical Report~96-44. The present paper includes in particular a new lower bound for unsatisfiable systems, and remarks on the Arthur-Merlin class.

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.

It is well-known that classical integration schemes designed for regular systems of IVPs become inefficient for piecewise regular problems. To avoid a significant increase of the cost of obtaining an e -approximation for piecewise regular problems, special adaptive algorithms are usually designed. Constructing such algorithms is often based on the knowledge of a 'switching function' whose zeros define the singularity hypersurface, or it relies on certain heuristic arguments. In this paper we analyze the worst-case e -complexity of globally continuous and piecewise regular problems with unknown smooth switching function. We consider problems with right-hand side functions from the class F r , ? which consists of piecewise r -smooth functions with Holder r -th partial derivatives with the exponent ? ? ( 0 , 1 . In contrast to our previous work, we restrict ourselves to information defined only by values of the right-hand side function (computation of partial derivatives is not allowed). We design an algorithm that is based on the computation of Lagrange interpolation polynomials to locate singularity points and to approximate a function of a single variable at intermediate stages. A rigorous analysis (independent of heuristic arguments) of its error and cost is given. It turns out that both the error and the cost of the algorithm are of the same order as for regular problems. That is, no reduction of the order is observed when passing through singularities, and the cost of the algorithm remains at the same level as for regular problems. In the class F r , ? the algorithm has the worst-case error O ( m - ( r + ? ) ) (in the Chebyshev norm) and the total cost O ( m ) , where m is the number of discretization points. This leads to the conclusion that the worst-case e -complexity of the considered problem in F r , ? is ? ( e - 1 / ( r + ? ) ) , and the minimal cost is achieved by the defined algorithm that only needs function evaluations. The auxiliary algorithm that locates singularities and approximates a piecewise regular function of a single variable is also original, and it may be of interest per se.

In this paper we study the convergence of the famous Weierstrass method for simultaneous approximation of polynomial zeros over a complete normed field. We present a new semilocal convergence theorem for the Weierstrass method under a new type of initial conditions. Our result is obtained by combining ideas of Weierstrass (1891) and Proinov (2010). A priori and a posteriori error estimates are also provided under the new initial conditions.

Given a graph G=(V,E) with a cost function c:E->R^+ and a vertex subset [email protected]?V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost @?"("u","v")"@?"E"("T")c(u,v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a ([email protected]+1)-approximation algorithm for solving the problem on complete graphs, where @r is an approximation ratio for the Steiner tree problem. Currently, the best-known @r is [email protected]

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.

It is a well-known fact that the Halton sequence exhibits poor uniformity in high dimensions. Starting with Braaten and Weller in 1979, several researchers introduced permutations to scramble the digits of the van der Corput sequences that make up the Halton sequence, in order to improve the uniformity of the Halton sequence. These sequences are called scrambled Halton, or generalized Halton sequences. Another significant result on the Halton sequence was the fact that it could be represented as the orbit of the von Neumann–Kakutani transformation, as observed by Lambert in 1982. In this paper, I will show that a scrambled Halton sequence can be represented as the orbit of an appropriately generalized von Neumann–Kakutani transformation. A practical implication of this result is that it gives a new family of randomized quasi-Monte Carlo sequences: random-start scrambled Halton sequences. This work generalizes random-start Halton sequences of Wang and Hickernell. Numerical results show that random-start scrambled Halton sequences can improve on the sample variance of random-start Halton sequences by factors as high as 7000.

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 study the complexity of Fredholm problems (I − Tk)u = f of the second kind on the I d = [0, 1]d, where Tk is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that f ∈ Wr,p(I d ) with r > d/p and that k ∈ Ws,∞(I 2d ) with s > 0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is 2(n−µ + δ), where µ = min{r/d, s/(2d)} and δ is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the ε-complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ−t , then the ε-complexity is roughly (1/ε)t+1/µ.

We study the multivariate Feynman–Kac path integration problem. This problem was studied in Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case. We describe an algorithm based on uniform approximation, instead of the L2-approximation used in Plaskota et al. (2000). Similarly to Plaskota et al. (2000), our algorithm requires extensive precomputing. We also present bounds on the complexity of our problem. The lower bound is provided by the complexity of a certain integration problem, and the upper bound by the complexity of the uniform approximation problem. The algorithm presented in this paper is almost optimal for the classes of functions for which uniform approximation and integration have roughly the same complexities.

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.

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m , s )-nets in base b produce unbiased estimates of the integral, have a variance that tends to zero faster than 1/ n for any square integrable integrand and have a variance that for finite n is never more than e ≐2.718 times as large as the Monte Carlo variance. Lower bounds than e are known for special cases. Some very important ( t , m , s )-nets have t >0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially in s >1 dimensions. This paper shows that scrambled ( t , m , s )-nets enjoy the same properties as scrambled (0, m , s )-nets, except the sampling variance is guaranteed only to be below b t [( b +1)/( b −1)] s times the Monte Carlo variance for a least-favorable integrand and finite n .

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.

Let F be a class of functions defined on a d-dimensional domain. Our task is to compute Hm-norm ϵ-approximations to solutions of 2mth-order elliptic boundary-value problems Lu = f for a fixed L and for f ∈ F. We assume that the only information we can compute about f ∈ F is the value of a finite number of continuous linear functionals of f, each evaluation having cost c(d). Previous work has assumed that F was the unit ball of a Sobolev space Hr of fixed smoothness r, and it was found that the complexity of computing an ϵ-approximation was comp(ϵ, d) = Θ(c(d)(1/ϵ)d/(r+m)). Since the exponent of 1/ϵ depends on d, we see that the problem is intractable in 1/ϵ for any such F of fixed smoothness r. In this paper, we ask whether we can break intractability by letting F be the unit ball of a space of infinite smoothness. To be specific, we let F be the unit ball of a Hardy space of analytic functions defined over a complex d-dimensional ball of radius greater than one. We then show that the problem is tractable in 1/ϵ. More precisely, we prove that comp(ϵ, d) = Θ(c(d)(ln 1/ϵ)d), where the Θ-constant depends on d. Since for any p > 0, there is a function K (·) such that comp(ϵ, d) ≤ c(d) K (d)(1/ϵ)p for sufficiently small ϵ, we see that the problem is tractable, with (minimal) exponent 0. Furthermore, we show how to construct a finite element p-method (in the sense of Babuška) that can compute an ϵ-approximation with cost Θ(c(d)(ln 1/ϵ)d). Hence this finite element method is a nearly optimal complexity algorithm for d-dimensional elliptic problems with analytic data.

Let O be an order of any quadratic number field. In this paper we show that under the assumption of the generalized Riemann hypothesis the following decision problems are in NP ⊃ co-NP: 1. 1. Is a given ideal A of O principal? 2. 2. Given ideals A 1 , … , Aκ of O , do their equivalence classes generate the class group of O ? 3. 3. Given ideals A 1 , … , Aκ of O , is the class group of O the direct product of the cyclic subgroups generated by the equivalence classes of the A 1 ?

n random matrix with independent Gaussian entries gij (real or complex), defined on some probability space (a, P’) and distributed according to the N(0, 1) law. In the theory of computational complexity it is of interest to consider the “random condition number” IIG;‘jl . \IGnll; in particular a question about the exact order of where 11.11 denotes the operator norm on the Euclidean space and [E the expected value, was asked in (Smale, 1985) (this quantity may be inter- preted as the average “loss of precision” when solving large systems of linear equations). It is very well known that n-“*IE((G,,(J + 2 as n -+ 03; moreover, lE/G,,ll pr~~‘~) 5 C exp(-cp*n), P((lG,(j < an”*) 5 (cay2 etc. Consequently, as far as the condition numbers are concerned, esskntially the only unknown is the behavior of G;‘. Above and in what follows, C, c, etc., denote uniuersa/ (effectively computable) numerical constants, most notably independent of n; however, identical symbols may represent different numbers in different places. In this paper we deal with a more general setup, which covers, e.g., the case when 5P is endowed with the 1; - norm ~~~~~, (for some p E [ 1, ~1); we denote the corresponding operator norm by ll’llp+P (in fact our methods allow us to handle arbitrary norms, on both the domain and the range of G; see Remark 4.1). We then have the following