Henryk Woźniakowski

Josef Dick, Peter Kritzer, Friedrich Pillichshammer et al.

We study multivariate $L_2$-approximation for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences $\boldsymbol{a} =\{a_j\}$ and $\boldsymbol{b} =\{b_j\}$ of numbers no less than one. Let $e^{L_2-\mathrm{app},Λ}(n,s)$ be the minimal worst-case error of all algorithms that use $n$ information functionals from the class $Λ$ in the $s$-variate case. We consider two classes $Λ$: the class $Λ^{\rm all}$ consists of all linear functionals and the class $Λ^{\rm std}$ consists of only function valuations. We study (EXP) exponential convergence. This means that $$ e^{L_2-\mathrm{app},Λ}(n,s) \le C(s)\,q^{\,(n/C_1(s))^{p(s)}}\quad{for all}\quad n, s \in \mathbb{N} $$ where $q\in(0,1)$, and $C,C_1,p:\mathbb{N} \rightarrow (0,\infty)$. If we can take $p(s)=p>0$ for all $s$ then we speak of (UEXP) uniform exponential convergence. We also study EXP and UEXP with (WT) weak, (PT) polynomial and (SPT) strong polynomial tractability. These concepts are defined as follows. Let $n(\e,s)$ be the minimal $n$ for which $e^{L_2-\mathrm{app},Λ}(n,s)\le \e$. Then WT holds iff $\lim_{s+\log\,\e^{-1}\to\infty}(\log n(\e,s))/(s+\log\,\e^{-1})=0$, PT holds iff there are $c,τ_1,τ_2$ such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all $s$ and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for $τ_1=0$. The infimum of $τ_2$ for which SPT holds is called the exponent $τ^*$ of SPT. We prove that the results are the same for both classes $Λ$, and obtain conditions for WT, PT, SPT with and without EXP and UEXP.

Erich Novak, Henryk Woźniakowski

This is an expository paper on approximating functions from general Hilbert or Banach spaces in the worst case, average case and randomized settings with error measured in the $L_p$ sense. We define the power function as the ratio between the best rate of convergence of algorithms that use function values over the best rate of convergence of algorithms that use arbitrary linear functionals for a worst possible Hilbert or Banach space for which the problem of approximating functions is well defined. Obviously, the power function takes values at most one. If these values are one or close to one than the power of function values is the same or almost the same as the power of arbitrary linear functionals. We summarize and supply a few new estimates on the power function. We also indicate eight open problems related to the power function since this function has not yet been studied for many cases. We believe that the open problems will be of interest to a general audience of mathematicians.

Aicke Hinrichs, Erich Novak, Henryk Woźniakowski

We study the integration and approximation problems for monotone and convex bounded functions that depend on $d$ variables, where $d$ can be arbitrarily large. We consider the worst case error for algorithms that use finitely many function values. We prove that these problems suffer from the curse of dimensionality. That is, one needs exponentially many (in $d$) function values to achieve an error $ε$.

Gregory E. Fasshauer, Fred J. Hickernell, Henryk Woźniakowski

This article studies the problem of approximating functions belonging to a Hilbert space $H_d$ with an isotropic or anisotropic Gaussian reproducing kernel, $$ K_d(\bx,\bt) = \exp\left(-\sum_{\ell=1}^dγ_\ell^2(x_\ell-t_\ell)^2\right) \ \ \ \mbox{for all}\ \ \bx,\bt\in\reals^d. $$ The isotropic case corresponds to using the same shape parameters for all coordinates, namely $γ_\ell=γ>0$ for all $\ell$, whereas the anisotropic case corresponds to varying shape parameters $γ_\ell$. We are especially interested in moderate to large $d$.

Erich Novak, Mario Ullrich, Henryk Woźniakowski et al.

We analyze univariate oscillatory integrals defined on the real line for functions from the standard Sobolev space $H^s({\mathbb{R}})$ and from the space $C^s({\mathbb{R}})$ with an arbitrary integer $s\ge1$. We find tight upper and lower bounds for the worst case error of optimal algorithms that use $n$ function values. More specifically, we study integrals of the form \[ I_k^ρ(f) = \int_{ {\mathbb{R}}} f(x) \,e^{-i\,kx} ρ(x) \, {\rm d} x\ \ \ \mbox{for}\ \ f\in H^s({\mathbb{R}})\ \ \mbox{or}\ \ f\in C^s({\mathbb{R}}) \] with $k\in {\mathbb{R}}$ and a smooth density function $ρ$ such as $ ρ(x) = \frac{1}{\sqrt{2 π}} \exp( -x^2/2) $. The optimal error bounds are $Θ((n+\max(1,|k|))^{-s})$ with the factors in the $Θ$ notation dependent only on $s$ and $ρ$.

Erich Novak, Mario Ullrich, Henryk Woźniakowski et al.

The standard Sobolev space $W^s_2(\mathbb{R}^d)$, with arbitrary positive integers $s$ and $d$ for which $s>d/2$, has the reproducing kernel $$ K_{d,s}(x,t)=\int_{\mathbb{R}^d}\frac{\prod_{j=1}^d\cos\left(2π\,(x_j-t_j)u_j\right)} {1+\sum_{0<|α|_1\le s}\prod_{j=1}^d(2π\,u_j)^{2α_j}}\,{\rm d}u $$ for all $x,t\in\mathbb{R}^d$, where $x_j,t_j,u_j,α_j$ are components of $d$-variate $x,t,u,α$, and $|α|_1=\sum_{j=1}^dα_j$ with non-negative integers $α_j$. We obtain a more explicit form for the reproducing kernel $K_{1,s}$ and find a closed form for the kernel $K_{d, \infty}$. Knowing the form of $K_{d,s}$, we present applications on the best embedding constants between the Sobolev space $W^s_2(\mathbb{R}^d)$ and $L_\infty(\mathbb{R}^d)$, and on strong polynomial tractability of integration with an arbitrary probability density. We prove that the best embedding constants are exponentially small in $d$, whereas worst case integration errors of algorithms using $n$ function values are also exponentially small in $d$ and decay at least like $n^{-1/2}$. This yields strong polynomial tractability in the worst case setting for the absolute error criterion.

Henryk Woźniakowski, Erich Novak

We study QPT (quasi-polynomial tractability) in the worst case setting for linear tensor product problems defined over Hilbert spaces. We assume that the domain space is a reproducing kernel Hilbert space so that function values are well defined. We prove QPT for algorithms that use only function values under the three assumptions: 1) the minimal errors for the univariate case decay polynomially fast to zero, 2) the largest singular value for the univariate case is simple and 3) the eigenfunction corresponding to the largest singular value is a multiple of the function value at some point. The first two assumptions are necessary for QPT. The third assumption is necessary for QPT for some Hilbert spaces.

Erich Novak, Mario Ullrich, Henryk Woźniakowski

We analyze univariate oscillatory integrals for the standard Sobolev spaces $H^s$ of periodic and non-periodic functions with an arbitrary integer $s\ge1$. We find matching lower and upper bounds on the minimal worst case error of algorithms that use $n$ function or derivative values. We also find sharp bounds on the information complexity which is the minimal $n$ for which the absolute or normalized error is at most $\varepsilon$. We show surprising relations between the information complexity and the oscillatory weight. We also briefly consider the case of $s=\infty$.

J. F. Traub, Henryk Woźniakowski

The authors discuss information-based complexity theory, which is a model of finite-precision computations with real numbers, and its applications to numerical analysis.