Tractability and Strong Tractability of Linear Multivariate Problems

Linear multivariate problems are defined as the approximation of linear operators on functions of d variables. We study the complexity of computing an ϵ-approximation in different settings. We are particularly interested in large d and/or large ϵ⁻¹. Tractability means that the complexity is bounded by c(d) K(d, ϵ), where c(d) is the cost of one information operation and K(d, ϵ) is a polynomial in d and/or in ϵ⁻¹. Strong tractability means that K(d, ϵ) is a polynomial in ϵ⁻¹, independent of d. We provide necessary and sufficient conditions for linear multivariate problems to be tractable or strongly tractable in the worst case, average case, randomized, and probabilistic settings. This is done for the class Λ^all where an information operation is defined as the computation of any continuous linear functional. We also consider the class Λ^std where an information operation is defined as the computation of a function value. We show under mild assumptions that tractability in the class Λ^all is equivalent to tractability in the class Λ^std. The proof is, however, not constructive. Finally, we consider linear multivariate problems over reproducing kernel Hilbert spaces, showing that such problems are strongly tractable even in the worst case setting.     

Average case complexity of linear multivariate problems I. Theory

We study the average case complexity of linear multivariate problems, that is, the approximation of continuous linear operators on functions of d variables. The function spaces are equipped with Gaussian measures. We consider two classes of information. The first class Λ^std consists of function values, and the second class Λ^all consists of all continuous linear functionals. Tractability of a linear multivariate problem means that the average case complexity of computing an ε-approximation is O((1/)^p) with p independent of d. The smallest such p is called the exponent of the problem. Under mild assumptions, we prove that tractability in Λ^all is equivalent to tractability in Λ^std and that the difference of the exponents is at most 2. The proof of this result is not constructive. We provide a simple condition to check tractability in Λ^all. We also address the issue of how to construct optimal (or nearly optimal) sample points for linear multivariate problems. We use relations between average case and worst case settings. These relations reduce the study of the average case to the worst case for a different class of functions. In this way we show how optimal sample points from the worst case setting can be used in the average case. In Part II we shall apply the theoretical results to obtain optimal or almost optimal sample points, optimal algorithms, and average case complexity functions for linear multivariate problems equipped with the folded Wiener sheet measure. Of particular interest will be the multivariate function approximation problem.     

Tractability of Multivariate Integration for Periodic Functions

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor ε for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ε⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ε⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Tractability through increasing smoothness

We prove that some multivariate linear tensor product problems are tractable in the worst case setting if they are defined as tensor products of univariate problems with logarithmically increasing smoothness. This is demonstrated for the approximation problem defined over Korobov spaces and for the approximation problem of certain diagonal operators. For these two problems we show necessary and sufficient conditions on the smoothness parameters of the univariate problems to obtain strong polynomial tractability. We prove that polynomial tractability is equivalent to strong polynomial tractability, and that weak tractability always holds for these problems. Under a mild assumption, the Korobov space consists of periodic functions. Periodicity is crucial since the approximation problem defined over Sobolev spaces of non-periodic functions with a special choice of the norm is not polynomially tractable for all smoothness parameters no matter how fast they go to infinity. Furthermore, depending on the choice of the norm we can even lose weak tractability.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the power of standard information for tractability for L∞ approximation of periodic functions in the worst case setting

We study multivariate approximation of periodic functions in the worst case setting with the error measured in the $L_{\infty }$ norm. We consider algorithms that use standard information ${\mathrm{\Lambda }}^{\mathrm{std}}$ consisting of function values or general linear information ${\mathrm{\Lambda }}^{\mathrm{all}}$ consisting of arbitrary continuous linear functionals. We investigate equivalences of various notions of algebraic and exponential tractability for ${\mathrm{\Lambda }}^{\mathrm{std}}$ and ${\mathrm{\Lambda }}^{\mathrm{all}}$ under the absolute or normalized error criterion, and show that the power of ${\mathrm{\Lambda }}^{\mathrm{std}}$ is the same as the one of ${\mathrm{\Lambda }}^{\mathrm{all}}$ for various notions of algebraic and exponential tractability. Our results can be applied to weighted Korobov spaces and Korobov spaces with exponential weights. This gives a special solution to Open Problem 145 as posed by Novak and Woźniakowski (2012) [40].     

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L _∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n ^?1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n ^?1 and stress that we do not know if these exponents can be improved.     

A Constructive Approach to Strong Tractability Using Quasi-Monte Carlo Algorithms

We prove in a constructive way that multivariate integration in appropriate weighted Sobolev classes is strongly tractable and the ε-exponent of strong tractability is 1 (which is the best-possible value) under a stronger assumption than Sloan and Woźniakowski's assumption. We show that quasi-Monte Carlo algorithms based on the Sobol sequence and Halton sequence achieve the convergence order O(n^−1+δ) for any δ>0 independent of the dimension with a worst-case deterministic guarantee (where n is the number of function evaluations). This implies that quasi-Monte Carlo algorithms based on the Sobol and Halton sequences converge faster and therefore are superior to Monte Carlo methods independent of the dimension for integrands in suitable weighted Sobolev classes.     

The Price of Pessimism for Multidimensional Quadrature

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Worst Case Setting

We consider approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces with finite-order weights. This means we consider functions of d variables that can be represented as sums of functions of at most q^* variables. Here, q^* is fixed (and presumably small) and d may be arbitrarily large. For the univariate problem, d = 1, we assume we know algorithms A1,ε that use O(ε−p) function or linear functional evaluations to achieve an error ε in the worst case setting. Based on these algorithms A_1,ε, we provide a construction of polynomial-time algorithms A_d,ε for the general d-variate problem with the number of evaluations bounded roughly by ε^−pd^q* to achieve an error ε in the worst case setting.     

Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

On the decomposition of cyclic algebras

A cyclic algebra (K/F, σ, a) of degreen hasproperty D(f) if it decomposes as a tensor product of a cyclic algebra of degreee=n/f containingL (the fixed subfield underσ ^e) and a cyclic subalgebra of degreef containing af-th root ofa. AlthoughD(2) holds for every cyclic algebra of degree 4 and exponent 2,D(p) fails for Brauer algebras of degreep ² and exponentp, andD(2) fails for Brauer algebras of degree 8 and exponent 2. Using this, one fills the gap in [6, Theorem 4] and [7, Theorem 7.3.28], to show that the example given there is indeed tensor indecomposable of degreep ² and exponentp. An easy ultraproduct argument provides an example containing allp ^k roots of 1, for allk.     

Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [???1,1[ ^d ?? spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m?≥?n point evaluations of a function in this space with computational cost O(mlog ^d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog ^d???1 n).     

What Is the Complexity of Stieltjes Integration?

We study the complexity of approximating the Stieltjes integral ∫¹₀ f(x) dg(x) for functions f having r continuous derivatives and functions g whose sth derivative has bounded variation. Let r(n) denote the nth minimal error attainable by approximations using at most n evaluations of f and g, and let comp(ε) denote the ε-complexity (the minimal cost of computing an ε-approximation). We show that r(n)≍n^{−min{r, s+1}} and that comp(ε)≍ε^{−1/min{r, s+1}}. We also present an algorithm that computes an ε-approximation at nearly minimal cost.     

A Note on the Complexity of Solving Poisson's Equation for Spaces of Bounded Mixed Derivatives

We study the complexity of solving the d-dimensional Poisson equation on ]0, 1[^d. We restrict ourselves to cases where the solution u lies in some space of functions of bounded mixed derivatives (with respect to the L_∞- or the L₂-norm) up to ∂^2d/∏^d_j=1 ∂x²_j. An upper bound for the complexity of computing a solution of some prescribed accuracy ε with respect to the energy norm is given, which is proportional to ε⁻¹. We show this result in a constructive manner by proposing a finite element method in a special sparse grid space, which is obtained by an a priori grid optimization process based on the energy norm. Thus, the result of this paper is twofold: First, from a theoretical point of view concerning the complexity of solving elliptic PDEs, a strong tractability result of the order O(ε⁻¹) is given, and, second, we provide a practically usable hierarchical basis finite element method of this complexity O(ε⁻¹), i.e., without logarithmic terms growing exponentially in d, at least for our sparse grid setting with its underlying smoothness requirements.     

The Exponent of Discrepancy Is at Least 1.0669

LetP⊂[0, 1]^dbe ann-point set and letw: P→[0, ∞) be a weight function withw(P)=∑_z∈P w(z)=1. TheL₂-discrepancy of the weighted set (P, w) is defined as theL₂-average ofD(x)=vol(B_x)−w(P∩B_x) overx∈[0, 1]^d, where vol(B_x) is the volume of thed-dimensional intervalB_x=∏^d_k=1 [0, x_k). The exponent of discrepancyp* is defined as the infimum of numberspsuch that for all dimensionsd⩾1 and allε>0 there exists a weighted set of at mostKε^−ppoints in [0, 1]^dwithL₂-discrepancy at mostε, whereK=K(p) is a suitable number independent ofεandd. Wasilkowski and Woźniakowski proved thatp*⩽1.4779, by combining known bounds for the error of numerical integration and using their relation toL₂-discrepancy. In this note we observe that a careful treatment of a classical lower- bound proof of Roth yieldsp*⩾1.04882, and by a slight modification of the proof we getp*⩾1.0669. Determiningp* exactly seems to be quite a difficult problem.     

A recursive method for computing interpolants

In this paper, we describe a recursive method for computing interpolants defined in a space spanned by a finite number of continuous functions in R^d${\mathbb{R}}^d$. We apply this method to construct several interpolants such as spline interpolants, tensor product interpolants and multivariate polynomial interpolants. We also give a simple algorithm for solving a multivariate polynomial interpolation problem and constructing the minimal interpolation space for a given finite set of interpolation points.     

Tractability results for weighted Banach spaces of smooth functions

We study the L_∞-approximation problem for weighted Banach spaces of smooth d-variate functions, where d can be arbitrarily large. We consider the worst case error for algorithms that use finitely many pieces of information from different classes. Adaptive algorithms are also allowed. For a scale of Banach spaces we prove necessary and sufficient conditions for tractability in the case of product weights. Furthermore, we show the equivalence of weak tractability with the fact that the problem does not suffer from the curse of dimensionality.