betaFeedback

WorksMathematics

Optimal Quadrature and the Curse of Dimensionality for a Veronese Class

Abstract

We study integration on a 3d3^d-dimensional trigonometric space whose unit ball has all coordinate mixed partial derivatives bounded by one. With evaluations anywhere in Rd\mathbb{R}^d, we determine the exact minimal worst-case error among all deterministic algorithms using at most nn function values. An optimal quadrature formula is obtained by truncating an exact product quadrature formula on {1/2,1/2+π}d\{1/2, 1/2+π\}^d. All weights are positive. For each error tolerance 0<ε<10<\varepsilon<1, the information complexity grows exponentially in dd with the common base Λ≈1.10546546Λ\approx 1.10546546. The correction of order d\sqrt{d} to the logarithm of the information complexity and the corresponding error limit are determined by the standard normal distribution function. For b≥1b\ge 1 and n=⌈bd⌉n=\lceil b^d\rceil, the error tends to one, one half, or zero according as b<Λb<Λ, b=Λb=Λ, or b>Λb>Λ.

Introduction and Main Results

We study worst-case integration on a finite-dimensional trigonometric class. The integral is taken over the unit cube, while function values may be taken either in the cube or anywhere in Rd\mathbb{R}^d.

For d∈Nd\in\mathbb{N}, define

Fd∞={f∈C∞([0,1]d;R):∥Dαf∥∞≤1 for every α∈N0d}.F_d^\infty=\left\{f\in C^\infty([0,1]^d;\mathbb{R}):\|D^\alpha f\|_\infty\leq1\text{ for every }\alpha\in\mathbb{N}_0^d\right\}.

The supremum norm on [0,1]d[0,1]^d is denoted by ∥⋅∥∞\|\cdot\|_\infty, and D0f=fD^0f=f. The sets of positive and nonnegative integers are N={1,2,…}\mathbb{N}=\{1,2,\ldots\} and N0={0,1,2,…}\mathbb{N}_0=\{0,1,2,\ldots\}. All logarithms are natural, empty sums equal zero, and empty products equal one.

Woźniakowski [20] posed the tractability question for Fd∞F_d^\infty. Wojtaszczyk [19] proved that the problem is not strongly polynomially tractable. Sengelen Sevim [14] proved the curse of dimensionality, with asymptotic exponential base approximately 1.105465461.10546546 in the lower bound for the information complexity. Matrix methods for quadrature in Hilbert spaces were developed in [2].

Here we show that the spectral lower bound from [14] is attained on the Veronese class when exterior nodes are allowed. We determine optimal quadrature formulas for every nn and derive Gaussian asymptotics for their error and information complexity.

For x∈Rx \in\mathbb{R}, define

z(x)=(cos⁡((x−1/2)/2)sin⁡((x−1/2)/2)),zd(x1,…,xd)=⨂j=1dz(xj).z(x)=\begin{pmatrix}\cos((x-1/2)/2)\\ \sin((x-1/2)/2)\end{pmatrix}, \qquad z_d(x_1,\ldots,x_d)=\bigotimes_{j=1}^{d}z(x_j).

For N∈NN \in\mathbb{N}, let Sym⁡N\operatorname{Sym}_N denote the real symmetric N×NN \times N matrices, and let ∥M∥op\lVert M\rVert_{\mathrm{op}} be the operator norm induced by the Euclidean norm. The Veronese class is

BV,d={fM:M∈Sym⁡2d, ∥M∥op≤1},fM(x)=zd(x)TMzd(x).\mathcal{B}_{V,d}=\{f_M:M\in\operatorname{Sym}_{2^d},\ \lVert M\rVert_{\mathrm{op}}\le1\}, \qquad f_M(x)=z_d(x)^{\mathsf T}Mz_d(x).

The linear span has dimension 3d3^d. Define

Sd(f)=∫[0,1]df(x) dx,Ddext=Rd,Dd□=[0,1]d.S_d(f)=\int_{[0,1]^d}f(x)\,\mathrm{d}x,\qquad D_d^{\mathrm{ext}}=\mathbb{R}^d,\qquad D_d^{\square}=[0,1]^d.

For σ∈{ext,□}\sigma\in\{\mathrm{ext},\square\} and n∈N0n\in\mathbb{N}_0, e~Vσ(n,d)\widetilde e_V^\sigma(n,d) denotes the minimal deterministic worst-case error among all algorithms based on at most nn function values in DdσD_d^\sigma. Adaptive nodes, input-dependent stopping, and nonlinear return maps are included. Thus

e~Vσ(n,d)=inf⁡Asup⁡f∈BV,d∣Sd(f)−A(f)∣.\widetilde e_V^\sigma(n,d)=\inf_A\sup_{f\in\mathcal{B}_{V,d}}\lvert S_d(f)-A(f)\rvert.

By Proposition 2.2, the initial errors satisfy

eVext(0,d)=eV□(0,d)=1.e_V^{\mathrm{ext}}(0,d)=e_V^{\square}(0,d)=1.

For 0<ε<10<\varepsilon<1, define

nVσ(ε,d)=min⁡{n∈N0:e~Vσ(n,d)≤ε}.n_V^\sigma(\varepsilon,d)=\min\{n\in\mathbb{N}_0:\widetilde e_V^\sigma(n,d)\le\varepsilon\}.

The absolute and normalized error criteria coincide. Exponential growth of nVσ(ε,d)n_V^\sigma(\varepsilon,d) in dd for a fixed ε∈(0,1)\varepsilon\in(0,1) is called the curse of dimensionality.

Set

q=12+sin⁡12,p=12−sin⁡12,H(p)=−plog⁡p−qlog⁡q,Λ=exp⁡(H(p)),q=\frac{1}{2}+\sin\frac{1}{2},\qquad p=\frac{1}{2}-\sin\frac{1}{2},\qquad H(p)=-p\log p-q\log q,\qquad\Lambda=\exp(H(p)),

and

V=pq[log⁡(q/p)]2.V=pq\left[\log(q/p)\right]^2.

Numerically,

q≈0.97942554,p≈0.02057446,q\approx0.97942554,\qquad p\approx0.02057446,
H(p)≈0.10026647,Λ≈1.10546546,V≈0.54835925.H(p)\approx0.10026647,\qquad\Lambda\approx1.10546546,\qquad\sqrt{V}\approx0.54835925.

Let Φ\Phi be the standard normal distribution function, and let Φ−1\Phi^{-1} denote the inverse function. For d∈Nd\in\mathbb{N}, arrange the numbers qd−kpkq^{d-k}p^k, with multiplicity (dk)\binom{d}{k} for k=0,…,dk=0,\ldots,d, in decreasing order as

λ1(d)≥⋯≥λ2d(d)>0.\lambda_1^{(d)}\ge\cdots\ge\lambda_{2^d}^{(d)}>0.

For n∈N0n\in\mathbb{N}_0, define

τn,d={∑j=n+12dλj(d),0≤n<2d,0,n≥2d.\tau_{n,d}= \begin{cases} \sum_{j=n+1}^{2^d}\lambda_j^{(d)}, & 0\le n<2^d,\\ 0, & n\ge2^d. \end{cases}

Theorem 1.1. Let d∈Nd \in\mathbb{N} and n∈N0n \in\mathbb{N}_0. Then

eV(n,d)≥eVext(n,d)=τn,d.e_V(n,d) \ge e_V^{\mathrm{ext}}(n,d) = \tau_{n,d}.

For n≤2dn \le2^d, eVext(n,d)e_V^{\mathrm{ext}}(n,d) is attained by a nonadaptive quadrature formula with nn nodes from {1/2,1/2+π}d\{1/2,1/2+\pi\}^d. The weights are positive and equal to the nn largest eigenvalues. For n≥2dn \ge2^d, the complete grid attains zero error with 2d2^d evaluations.

Theorem 1.2. Let s∈Rs \in\mathbb{R}, and let (nd)d≥1⊂N(n_d)_{d\ge1} \subset\mathbb{N} satisfy

log⁡nd−dH(p)d⟶s.\frac{\log n_d-dH(p)}{\sqrt{d}} \longrightarrow s.

Then

lim⁡d→∞eVext(nd,d)=1−Φ(sV).(1)\lim_{d\to\infty} e_V^{\mathrm{ext}}(n_d,d) = 1-\Phi\left(\frac{s}{\sqrt{V}}\right). \tag*{(1)}

For every fixed 0<ε<10<\varepsilon<1,

lim⁡d→∞log⁡nVext(ε,d)−dH(p)d=VΦ−1(1−ε).(2)\lim_{d\to\infty}\frac{\log n_V^{\mathrm{ext}}(\varepsilon,d)-dH(p)}{\sqrt{d}}=\sqrt{V}\Phi^{-1}(1-\varepsilon). \tag*{(2)}

Consequently,

lim⁡d→∞nVext(ε,d)1/d=Λ.(3)\lim_{d\to\infty} n_V^{\mathrm{ext}}(\varepsilon,d)^{1/d}=\Lambda. \tag*{(3)}

Remark 1.3 (Monte Carlo). For n∈Nn \in\mathbb{N} and independent uniform points Ξ1,…,Ξn\Xi_1,\ldots,\Xi_n in [0,1]d[0,1]^d, put Qn,dMC(f)=n−1∑i=1nf(Ξi)Q_{n,d}^{\mathrm{MC}}(f)=n^{-1}\sum_{i=1}^n f(\Xi_i). Independence and ∣f∣≤1|f|\le1 give E∣Sd(f)−Qn,dMC(f)∣2=Var⁡(f(Ξ1))/n≤1/n\mathbb{E}|S_d(f)-Q_{n,d}^{\mathrm{MC}}(f)|^2=\operatorname{Var}(f(\Xi_1))/n\le1/n for f∈Fd∞f\in F_d^\infty. Thus

sup⁡f∈Fd∞(E∣Sd(f)−Qn,dMC(f)∣2)1/2≤n−1/2.(4)\sup_{f\in F_d^\infty}\left(\mathbb{E}|S_d(f)-Q_{n,d}^{\mathrm{MC}}(f)|^2\right)^{1/2}\le n^{-1/2}. \tag*{(4)}

The same bound applies to BV,dB_{V,d}.

Remark 1.4 (Optimal Quadrature Formulas by Deletion). The optimal exterior formulas are obtained from one exact product formula by retaining its largest weights. A related deletion property holds for the periodic trigonometric problem [8, 18]; see § 4.4.

Remark 1.5 (Approximation, Integration, and Widths). For Fd∞F_d^\infty, let eapp(n,d)e^{\mathrm{app}}(n,d) denote the minimal deterministic worst-case error for uniform approximation by algorithms based on at most nn continuous linear functionals, selected adaptively, and an arbitrary return map. Novak and Woźniakowski [11], Theorem 1 proved

eapp(n,d)=1(0≤n<2⌊d/2⌋).e^{\mathrm{app}}(n,d)=1 \qquad(0\le n<2^{\lfloor d/2\rfloor}).

The corresponding integration question is resolved for Fd∞F_d^\infty by the exponential lower bound in [14].

For widths of smooth function classes and related numbers, see Kashin [5] and Pietsch [13]; for multivariate approximation and optimal sampling, see Temlyakov [17] and the survey of Krieg and Ullrich [6].

Novak [7 Proposition 3(c)] constructed an infinite-dimensional linear subspace E⊂C([0,1])E \subset C([0,1]) such that, for every continuous linear functional μ\mu on C([0,1])C([0,1]), there are xμ∈[0,1]x_\mu\in[0,1] and aμ∈Ra_\mu\in\mathbb{R} with

μ(f)=aμf(xμ)(f∈E).\mu(f) = a_\mu f(x_\mu) \qquad(f \in E).

Thus every such functional can be computed exactly on EE from one function value. On the whole space EE, the Kolmogorov and Gelfand widths in the uniform norm are infinite for every finite index, and uniform approximation from finitely many function values has infinite worst-case error. Hence integration and uniform approximation can have a very different information complexity; see [12].

Matrix Representation and Optimal Quadrature

For t∈Rt \in\mathbb{R}, x∈Rdx \in\mathbb{R}^{d}, and M∈Sym⁡2dM \in\operatorname{Sym}_{2d}, define

K(t)=z(t)z(t)T,Kd(x)=zd(x)zd(x)T,(TdM)(x)=tr⁡(MKd(x)).K(t) = z(t)z(t)^{\mathsf{T}}, \qquad K_d(x) = z_d(x)z_d(x)^{\mathsf{T}}, \qquad(T_dM)(x) = \operatorname{tr}(MK_d(x)).

Set

T1=span⁡{1,cos⁡(x−12),sin⁡(x−12)},Td=⨂j=1dT1.\mathcal{T}_1 = \operatorname{span}\{1,\cos(x-\tfrac{1}{2}),\sin(x-\tfrac{1}{2})\}, \qquad\mathcal{T}_d = \bigotimes_{j=1}^{d}\mathcal{T}_1.

For f∈Tdf \in\mathcal{T}_d, define

∥f∥V,d=min⁡M∈Sym⁡2dTdM=f∥M∥op.(5)\lVert f\rVert_{V,d} = \min_{\substack{M\in\operatorname{Sym}_{2^{d}}\\ T_dM=f}} \lVert M\rVert_{\mathrm{op}}. \tag*{(5)}

The class BV,dB_{V,d} is the unit ball of the quotient norm.

Matrix Model and Derivative Bound

Let N∈NN \in\mathbb{N} and let μ1,…,μN\mu_1,\ldots,\mu_N be the eigenvalues of B∈Sym⁡NB \in\operatorname{Sym}_N. The trace norm, also called the nuclear norm, is defined by ∥B∥∗=∑j=1N∣μj∣\lVert B\rVert_* = \sum_{j=1}^{N}|\mu_j|.

The spectral theorem yields ∥B∥op=max⁡1≤j≤N∣μj∣\lVert B\rVert_{\mathrm{op}} = \max_{1\leq j\leq N}|\mu_j| and, for every M∈Sym⁡NM \in\operatorname{Sym}_N, the duality identities

∣tr⁡(MB)∣≤∥M∥op∥B∥∗,max⁡M∈Sym⁡N∥M∥op≤1∣tr⁡(MB)∣=∥B∥∗.(6)|\operatorname{tr}(MB)| \leq\lVert M\rVert_{\mathrm{op}}\lVert B\rVert_*, \qquad\max_{\substack{M\in\operatorname{Sym}_N\\ \lVert M\rVert_{\mathrm{op}}\leq1}} |\operatorname{tr}(MB)| = \lVert B\rVert_*. \tag*{(6)}

For an orthonormal eigenbasis v1,…,vNv_1,\ldots,v_N of BB, we obtain tr⁡(MB)=∑j=1NμjvjTMvj\operatorname{tr}(MB) = \sum_{j=1}^{N}\mu_j v_j^{\mathsf{T}}Mv_j and ∣vjTMvj∣≤∥M∥op|v_j^{\mathsf{T}}Mv_j| \leq\lVert M\rVert_{\mathrm{op}}. Equality in (6) follows for the symmetric matrix determined by Mvj=vjMv_j=v_j when μj≥0\mu_j\geq0 and Mvj=−vjMv_j=-v_j when μj<0\mu_j<0.

For N1,N2∈NN_1,N_2 \in\mathbb{N}, A∈Sym⁡N1A \in\operatorname{Sym}_{N_1}, and B∈Sym⁡N2B \in\operatorname{Sym}_{N_2}, every eigenvalue of A⊗BA\otimes B is a product of an eigenvalue of AA and an eigenvalue of BB. Consequently,

∥A⊗B∥op=∥A∥op∥B∥op,∥A⊗B∥∗=∥A∥∗∥B∥∗.(7)\lVert A\otimes B\rVert_{\mathrm{op}} = \lVert A\rVert_{\mathrm{op}}\lVert B\rVert_{\mathrm{op}}, \qquad\lVert A\otimes B\rVert_* = \lVert A\rVert_*\lVert B\rVert_*. \tag*{(7)}

The double-angle identities give

K(x)=12(1+cos⁡(x−12)sin⁡(x−12)sin⁡(x−12)1−cos⁡(x−12)).(8)K(x)=\frac{1}{2}\begin{pmatrix}1+\cos\left(x-\frac{1}{2}\right)&\sin\left(x-\frac{1}{2}\right)\\\sin\left(x-\frac{1}{2}\right)&1-\cos\left(x-\frac{1}{2}\right)\end{pmatrix}. \tag*{(8)}

Since ∥z(x)∥=1\lVert z(x)\rVert=1, the matrix K(x)K(x) is a rank-one orthogonal projection. The entries span T1\mathcal{T}_1. For f(x)=c0+c1cos⁡(x−12)+c2sin⁡(x−12)f(x)=c_0+c_1\cos\left(x-\frac{1}{2}\right)+c_2\sin\left(x-\frac{1}{2}\right), the identity f(x)=tr⁡(AfK(x))f(x)=\operatorname{tr}(A_fK(x)) determines a unique matrix

Af=(c0+c1c2c2c0−c1).(9)A_f=\begin{pmatrix}c_0+c_1&c_2\\c_2&c_0-c_1\end{pmatrix}. \tag*{(9)}

The eigenvalues of AfA_f are c0±c12+c22c_0\pm\sqrt{c_1^2+c_2^2}. Hence

∥f∥V,1=∥Af∥op=∣c0∣+c12+c22.(10)\lVert f\rVert_{V,1}=\lVert A_f\rVert_{\mathrm{op}}=\lvert c_0\rvert+\sqrt{c_1^2+c_2^2}. \tag*{(10)}

The name Veronese refers to the quadratic map (u,v)↦(X,Y,Z)=(u2,uv,v2)(u,v)\mapsto(X,Y,Z)=(u^2,uv,v^2). For the entries u,vu,v of z(x)z(x), the image coordinates satisfy X+Z=1X+Z=1 and Y2=XZY^2=XZ. Thus the quadratic image of zz lies on a conic in the plane X+Z=1X+Z=1. The matrix estimates depend on the rank-one property of K(x)K(x).

The tensor definition gives

Kd(x)=⨂j=1dK(xj).K_d(x)=\bigotimes_{j=1}^{d}K(x_j).

Thus Kd(x)K_d(x) is a rank-one orthogonal projection on R2d\mathbb{R}^{2^d}. Every entry of KdK_d is in Td\mathcal{T}_d. Conversely, tensor products of the matrices in (9) yield every basis tensor of Td\mathcal{T}_d, so Td(Sym⁡2d)=Td\mathcal{T}_d(\operatorname{Sym}_2^d)=\mathcal{T}_d. The functions 1,cos⁡(x−12),sin⁡(x−12)1,\cos\left(x-\frac{1}{2}\right),\sin\left(x-\frac{1}{2}\right) are linearly independent on [0,1][0,1]: the value and the derivatives of orders one and two at 1/21/2 determine all three coefficients. Tensor products therefore yield 3d3^d linearly independent functions on [0,1]d[0,1]^d.

The minimum in (5) is attained: a bounded minimizing sequence in the closed affine space {M∈Sym⁡2d:TdM=f}\{M\in\operatorname{Sym}_{2^d}:\mathcal{T}_dM=f\} has a convergent subsequence. Thus BVd={f∈Td:∥f∥V,d≤1}BV_d=\{f\in\mathcal{T}_d:\lVert f\rVert_{V,d}\leq1\}. For d≥2d\geq2, the representing matrix is not unique. Indeed, dim⁡Sym⁡4=10>9=dim⁡T2\dim\operatorname{Sym}_4=10>9=\dim\mathcal{T}_2, and tensoring a nonzero element of ker⁡T2\ker\mathcal{T}_2 with I2d−2I_{2^{d-2}} gives a nonzero element of ker⁡Td\ker\mathcal{T}_d. This explains the minimum in (5).

Linear independence of the tensor basis on the cube implies that its coefficients, and hence its extension to Rd\mathbb{R}^d, are uniquely determined. Thus exterior evaluation is well defined on the quotient space.

The univariate trace-norm identity on [0,1][0,1], the cube-node spectral lower bound, and the finite expression for τn,d\tau_{n,d} are obtained in [14]. Lemma 2.1 yields the equality on R\mathbb{R} and the tensor identity.

Lemma 2.1. Let ℓ∈N0\ell\in\mathbb{N}_0 and d∈Nd\in\mathbb{N}. For every x∈Rx\in\mathbb{R},

∥K(ℓ)(x)∥∗=1.\left\lVert K^{(\ell)}(x)\right\rVert_*=1.

Consequently, for every α∈N0d\alpha\in\mathbb{N}_0^d and x∈Rdx\in\mathbb{R}^d,

∥DαKd(x)∥∗=1.(11)\left\lVert D^\alpha K_d(x)\right\rVert_*=1. \tag*{(11)}

Proof. For ℓ=0\ell= 0, the rank-one projection K(x)K(x) has eigenvalues one and zero. For ℓ≥1\ell\ge1, differentiation of (8) yields

K(ℓ)(x)=12(cos⁡(x−12+ℓπ2)sin⁡(x−12+ℓπ2)sin⁡(x−12+ℓπ2)−cos⁡(x−12+ℓπ2)).K^{(\ell)}(x) = \frac{1}{2}\begin{pmatrix} \cos\left(x-\frac{1}{2}+\frac{\ell\pi}{2}\right) & \sin\left(x-\frac{1}{2}+\frac{\ell\pi}{2}\right) \\ \sin\left(x-\frac{1}{2}+\frac{\ell\pi}{2}\right) & -\cos\left(x-\frac{1}{2}+\frac{\ell\pi}{2}\right) \end{pmatrix}.

The characteristic polynomial equals λ2−14\lambda^2-\frac{1}{4} because cos⁡2t+sin⁡2t=1\cos^2 t+\sin^2 t=1. The eigenvalues are 1/21/2 and −1/2-1/2, and ∥K(ℓ)(x)∥∗=1\left\|K^{(\ell)}(x)\right\|_* = 1.

Each coordinate is present in one tensor factor, so

DαKd(x)=⨂j=1dK(αj)(xj).D^\alpha K_d(x)=\bigotimes_{j=1}^{d}K^{(\alpha_j)}(x_j).

The tensor identity in (7) and the univariate trace-norm identity give (11).

For f∈Tdf\in\mathcal{T}_d, define the coordinate derivative norm by

∥f∥∞,der=sup⁡α∈N0d∥Dαf∥∞.\|f\|_{\infty,\mathrm{der}}=\sup_{\alpha\in\mathbb{N}_0^d}\|D^\alpha f\|_\infty.

Proposition 2.2. Let d∈Nd\in\mathbb{N}. For every f∈Tdf\in\mathcal{T}_d,

∥f∥∞,der≤∥f∥V,d.(12)\|f\|_{\infty,\mathrm{der}}\le\|f\|_{V,d}. \tag*{(12)}

Every f∈BV,df\in B_{V,d} satisfies f∣[0,1]d∈Fd∞f|_{[0,1]^d}\in F_d^\infty, and eVext(0,d)=eV□(0,d)=1e_V^{\mathrm{ext}}(0,d)=e_V^\square(0,d)=1.

Proof. Let α∈N0d\alpha\in\mathbb{N}_0^d and x∈[0,1]dx\in[0,1]^d. For every M∈Sym⁡2dM\in\operatorname{Sym}_{2d} satisfying TdM=fT_dM=f, the trace estimate (6) and Lemma 2.1 imply

∣Dαf(x)∣=∣tr⁡(MDαKd(x))∣≤∥M∥op∥DαKd(x)∥∗=∥M∥op.|D^\alpha f(x)|=|\operatorname{tr}(M D^\alpha K_d(x))|\le\|M\|_{\mathrm{op}}\|D^\alpha K_d(x)\|_*=\|M\|_{\mathrm{op}}.

The supremum over xx and α\alpha, followed by the infimum over MM, yields (12). Since the derivative identity holds for every x∈Rdx\in\mathbb{R}^d, we also obtain

sup⁡x∈Rd∣Dαf(x)∣≤∥f∥V,d(α∈N0d).(13)\sup_{x\in\mathbb{R}^d}|D^\alpha f(x)|\le\|f\|_{V,d}\qquad(\alpha\in\mathbb{N}_0^d). \tag*{(13)}

The identity matrix I2dI_{2d} satisfies TdI2d=1T_dI_{2d}=1, since tr⁡Kd(x)=1\operatorname{tr}K_d(x)=1. Thus ±1∈BV,d\pm1\in B_{V,d}, and ∣Sd(f)∣≤1|S_d(f)|\le1 for every f∈BV,df\in B_{V,d}. An algorithm with zero evaluations returns a constant a∈Ra\in\mathbb{R}, and max⁡{∣1−a∣,∣−1−a∣}≥1\max\{|1-a|,|-1-a|\}\ge1. The constant approximation zero attains error one.

Spectral Lower Bound

The integration matrix and the spectrum are given in [14]. Integration of (8) yields

G=∫01K(x) dx=(q00p).G=\int_0^1K(x)\,dx=\begin{pmatrix}q&0\\0&p\end{pmatrix}.

Coordinatewise integration yields

Gd=∫[0,1]dKd(x) dx=G⊗d,Sd(TdM)=tr⁡(MGd).G_d=\int_{[0,1]^d}K_d(x)\,dx=G^{\otimes d},\qquad S_d(T_dM)=\operatorname{tr}(MG_d).

The eigenvalues of GdG_d are λj(d)\lambda_j^{(d)}, 1≤j≤2d1\le j\le2^d, and tr⁡(Gd)=(p+q)d=1\operatorname{tr}(G_d)=(p+q)^d=1. For a deterministic algorithm AA and a class BB, define

e(A,B)=sup⁡f∈B∣Sd(f)−A(f)∣.e(A,B)=\sup_{f\in B}|S_d(f)-A(f)|.

Proposition 2.3. Let d∈Nd\in\mathbb{N} and n∈N0n\in\mathbb{N}_0. Then

eVcube(n,d)≥eVext(n,d)≥τn,d.e^{\mathrm{cube}}_V(n,d)\ge e^{\mathrm{ext}}_V(n,d)\ge\tau_{n,d}.

Proof. Every cube-node algorithm is also an exterior-node algorithm, so the first inequality is immediate. For n≥2dn\ge2^d, the second follows from τn,d=0\tau_{n,d}=0. Let n<2dn<2^d. Run an arbitrary deterministic algorithm AA on the zero function. Let x1,…,xmx^1,\ldots,x^m, with m≤nm\le n, be the nodes it uses, and put a=A(0)a=A(0). Let Π\Pi be the orthogonal projection onto

W=span⁡{zd(x1),…,zd(xm)},r=dim⁡W≤n,W=\operatorname{span}\{z_d(x^1),\ldots,z_d(x^m)\},\qquad r=\dim W\le n,

and set P=I2d−ΠP=I_{2^d}-\Pi. Since ∥P∥op≤1\|P\|_{\mathrm{op}}\le1, the functions ±fP\pm f_P belong to BVdBV_d, where

fP(x)=zd(x)TPzd(x)=∥Pzd(x)∥22.f_P(x)=z_d(x)^{\mathsf{T}}Pz_d(x)=\|Pz_d(x)\|_2^2.

They vanish at every xix^i. By induction over the evaluations, the inputs 00, fPf_P, −fP-f_P produce the same observations, the same stopping decision and the same output aa. Therefore

e(A,BVd)≥max⁡{∣Sd(fP)−a∣, ∣−Sd(fP)−a∣}≥Sd(fP).e(A,BV_d)\ge\max\{|S_d(f_P)-a|,\ |-S_d(f_P)-a|\}\ge S_d(f_P).

Let v1,…,v2dv_1,\ldots,v_{2^d} be an orthonormal eigenbasis of GdG_d, ordered by decreasing eigenvalues, and define bj=∥Πvj∥22b_j=\|\Pi v_j\|_2^2. Then 0≤bj≤10\le b_j\le1 and ∑jbj=tr⁡Π=r\sum_j b_j=\operatorname{tr}\Pi=r. For r≥1r\ge1, we obtain

tr⁡(ΠGd)=∑jλj(d)bj=rλr(d)+∑j(λj(d)−λr(d))bj≤rλr(d)+∑j=1r(λj(d)−λr(d))=∑j=1rλj(d).\begin{aligned} \operatorname{tr}(\Pi G_d)=\sum_j\lambda_j^{(d)}b_j \\ &=r\lambda_r^{(d)}+\sum_j\left(\lambda_j^{(d)}-\lambda_r^{(d)}\right)b_j \\ &\le r\lambda_r^{(d)}+\sum_{j=1}^{r}\left(\lambda_j^{(d)}-\lambda_r^{(d)}\right)=\sum_{j=1}^{r}\lambda_j^{(d)}. \end{aligned}

The inequality follows from bj≤1b_j\le1 for j≤rj\le r and bj≥0b_j\ge0 for j>rj>r. For r=0r=0, we have Π=0\Pi=0 and tr⁡(ΠGd)=0\operatorname{tr}(\Pi G_d)=0. Therefore

Sd(fP)=tr⁡(PGd)=1−tr⁡(ΠGd)≥∑j=r+12dλj(d)≥τn,d.S_d(f_P)=\operatorname{tr}(PG_d)=1-\operatorname{tr}(\Pi G_d)\ge\sum_{j=r+1}^{2^d}\lambda_j^{(d)}\ge\tau_{n,d}.

Taking the infimum over AA proves the exterior lower bound.

Optimal Exterior Quadrature

For u=(u1,…,ud)∈{0,1}du=(u_1,\ldots,u_d)\in\{0,1\}^d, define

∣u∣=∑j=1duj,|u|=\sum_{j=1}^{d}u_j,
xu=(1/2+πu1,…,1/2+πud),x^u=(1/2+\pi u_1,\ldots,1/2+\pi u_d),
λ(u)=qd−∣u∣p∣u∣.(14)\lambda(u)=q^{d-|u|}p^{|u|}. \tag*{(14)}

Let e1=(1,0)Te_1=(1,0)^{\mathsf T} and e2=(0,1)Te_2=(0,1)^{\mathsf T}. For the nodes in (14), the identities z(1/2)=e1z(1/2)=e_1 and z(1/2+π)=e2z(1/2+\pi)=e_2 imply zd(xu)=⨂j=1de1+ujz_d(x^u)=\bigotimes_{j=1}^{d}e_{1+u_j}. Hence the vectors zd(xu)z_d(x^u) are the standard orthonormal eigenbasis of GdG_d. With Pu=Kd(xu)P_u=K_d(x^u), the spectral decomposition becomes

Gd=∑u∈{0,1}dλ(u)Pu.G_d=\sum_{u\in\{0,1\}^d}\lambda(u)P_u.

The trace pairing with a matrix satisfying TdM=fT_dM=f then yields a positive quadrature formula on TdT_d.

Sd(f)=∑u∈{0,1}dλ(u)f(xu),f∈Td.(15)S_d(f)=\sum_{u\in\{0,1\}^d}\lambda(u)f(x^u),\qquad f\in T_d. \tag*{(15)}

For d∈Nd\in\mathbb{N} and 0≤n≤2d0\le n\le2^d, let En,d⊆{0,1}dE_{n,d}\subseteq\{0,1\}^d contain nn elements satisfying

λ(u)≥λ(v)(u∈En,d, v∈{0,1}d∖En,d).\lambda(u)\ge\lambda(v)\qquad(u\in E_{n,d},\ v\in\{0,1\}^d\setminus E_{n,d}).

Define the quadrature formula

Qn,dext(f)=∑u∈En,dλ(u)f(xu),f∈Td.(16)Q^{\mathrm{ext}}_{n,d}(f)=\sum_{u\in E_{n,d}}\lambda(u)f(x^u),\qquad f\in T_d. \tag*{(16)}

Proof of Theorem 1.1. Proposition 2.3 provides eV□(n,d)≥eVext(n,d)≥τn,de^{\Box}_{V}(n,d)\ge e^{\mathrm{ext}}_{V}(n,d)\ge\tau_{n,d}. For f∈BVdf\in BV_d, choose M∈Sym⁡2dM\in\operatorname{Sym}_{2^d} with TdM=fT_dM=f and ∥M∥op≤1\lVert M\rVert_{\mathrm{op}}\le1. Then, for x∈Rdx\in\mathbb{R}^d,

∣f(x)∣≤∥M∥op∥zd(x)∥22≤1.|f(x)|\le\lVert M\rVert_{\mathrm{op}}\lVert z_d(x)\rVert_2^2\le1.

For 0≤n≤2d0\le n\le2^d, equations (15) and (16) therefore yield

∣Sd(f)−Qn,dext(f)∣≤∑u∉En,dλ(u)=τn,d.|S_d(f)-Q^{\mathrm{ext}}_{n,d}(f)|\le\sum_{u\notin E_{n,d}}\lambda(u)=\tau_{n,d}.

The function f≡1∈BVdf\equiv1\in BV_d attains equality, so

e(Qn,dext,BVd)=eVext(n,d)=τn,d.e(Q^{\mathrm{ext}}_{n,d},BV_d)=e^{\mathrm{ext}}_{V}(n,d)=\tau_{n,d}.

The nodes are nonadaptive and the weights are positive. For n=0n=0, (16) equals zero. For n≥2dn\ge2^d, the full quadrature formula in (15) has zero error and uses at most nn evaluations.

Define the cumulative multiplicities and masses by

L−1(d)=B−1(d)=0,Lr(d)=∑k=0r(dk),Br(d)=∑k=0r(dk)qd−kpk.L_{-1}(d)=B_{-1}(d)=0,\qquad L_r(d)=\sum_{k=0}^{r}\binom{d}{k},\qquad B_r(d)=\sum_{k=0}^{r}\binom{d}{k}q^{d-k}p^k.

for r=0,…,dr=0,\ldots,d. For n∈{0,…,2d−1}n\in\{0,\ldots,2^d-1\}, let r∈{0,…,d}r\in\{0,\ldots,d\} satisfy Lr−1(d)≤n<Lr(d)L_{r-1}(d)\le n<L_r(d). Since q>pq>p, the eigenvalue levels decrease strictly with kk. We obtain

τn,d=(Lr(d)−n)qd−rpr+∑k=r+1d(dk)qd−kpk.\tau_{n,d}=(L_r(d)-n)q^{d-r}p^r+\sum_{k=r+1}^{d}\binom{d}{k}q^{d-k}p^k.

Corollary 2.4. Let d∈Nd\in\mathbb{N}, 0<ε<10<\varepsilon<1, and r=min⁡{j∈{0,…,d}:Bj(d)≥1−ε}r=\min\{j\in\{0,\ldots,d\}:B_j(d)\ge1-\varepsilon\}. Then

nVext(ε,d)=Lr−1(d)+⌈1−ε−Br−1(d)qd−rpr⌉.(17)n_V^{\mathrm{ext}}(\varepsilon,d)=L_{r-1}(d)+\left\lceil\frac{1-\varepsilon-B_{r-1}(d)}{q^{d-r}p^r}\right\rceil. \tag*{(17)}

Proof. By Theorem 1.1, retain all levels below rr, giving Lr−1(d)L_{r-1}(d) nodes and total weight Br−1(d)B_{r-1}(d), and then retain the least integer number of weights qd−rprq^{d-r}p^r needed to reach total weight 1−ε1-\varepsilon. This gives (17). Since Br−1(d)<1−ε≤Br(d)B_{r-1}(d)<1-\varepsilon\le B_r(d), the ceiling lies between 11 and (dr)\binom{d}{r}.

Since q>pq>p, optimal node selection follows increasing ∣u∣|u|, with arbitrary selection among equal weights. The sum of the weights is 1−τn,d1-\tau_{n,d}, and

Qn,dext(1)=1−τn,d<1(0≤n<2d).Q_{n,d}^{\mathrm{ext}}(1)=1-\tau_{n,d}<1\qquad(0\le n<2^d).

Remark 2.5 (Trace-Norm Characterization). For Qn(f)=∑i=1naif(xi)Q_n(f)=\sum_{i=1}^{n}a_i f(x^i) with xi∈Rdx^i\in\mathbb{R}^d and ai∈Ra_i\in\mathbb{R}, the definition of BVd\mathrm{BV}_d and trace-norm duality give

e(Qn,BVd)=∥Gd−∑i=1naiKd(xi)∥∗.(18)e(Q_n,\mathrm{BV}_d)=\left\|G_d-\sum_{i=1}^{n}a_iK_d(x^i)\right\|_*. \tag*{(18)}

Indeed, the error is the maximum of ∣tr⁡(M[Gd−∑iaiKd(xi)])∣\left|\operatorname{tr}\left(M\left[G_d-\sum_i a_iK_d(x^i)\right]\right)\right| over ∥M∥op≤1\|M\|_{\mathrm{op}}\le1. This argument also covers noninjective TdT_d.

Since BVd\mathrm{BV}_d is convex and symmetric and SdS_d is a linear functional, it suffices to consider nonadaptive linear quadrature [1, 10]. Consequently,

eV□(n,d)=inf⁡x1,…,xn∈[0,1]da1,…,an∈R∥Gd−∑i=1naiKd(xi)∥∗.e_V^{\Box}(n,d)=\inf_{\substack{x^1,\ldots,x^n\in[0,1]^d\\a_1,\ldots,a_n\in\mathbb{R}}}\left\|G_d-\sum_{i=1}^{n}a_iK_d(x^i)\right\|_*.

The same identity holds for eVext(n,d)e_V^{\mathrm{ext}}(n,d) with nodes in Rd\mathbb{R}^d. For n=0n=0, the empty sum gives ∥Gd∥∗=1\|G_d\|_*=1. Formula (16) attains the exterior infimum for n≤2dn\le2^d; zero coefficients cover larger nn.

Gaussian Limit and Information Complexity

Proof of Theorem 1.2. Write

ed(n)=eVext(n,d).e_d(n)=e_{\mathrm{V}}^{\mathrm{ext}}(n,d).

By Theorem 1.1,

ed(n)=1−max⁡I⊆{0,1}d∣I∣≤n∑u∈Iλ(u).e_d(n)=1-\max_{\substack{I\subseteq\{0,1\}^d\\ |I|\le n}}\sum_{u\in I}\lambda(u).

Let UU satisfy P(U=u)=λ(u)\mathbb{P}(U=u)=\lambda(u) and define Yd=−log⁡λ(U)Y_d=-\log\lambda(U). For every n∈Nn\in\mathbb{N} and a>0a>0,

P(Yd≥log⁡n+a)−e−a≤ed(n)≤P(Yd≥log⁡n).(19)\mathbb{P}(Y_d\ge\log n+a)-e^{-a}\le e_d(n)\le\mathbb{P}(Y_d\ge\log n). \tag*{(19)}

Fewer than nn points u∈{0,1}du\in\{0,1\}^d satisfy λ(u)>1/n\lambda(u)>1/n, which yields the upper estimate. For the lower estimate, every set II with ∣I∣≤n|I|\le n satisfies

P(U∈I,Yd≥log⁡n+a)=∑u∈I−log⁡λ(u)≥log⁡n+aλ(u)≤∣I∣e−an≤e−a,\mathbb{P}(U\in I,Y_d\ge\log n+a)=\sum_{\substack{u\in I\\-\log\lambda(u)\ge\log n+a}}\lambda(u)\le|I|\frac{e^{-a}}{n}\le e^{-a},

so its omitted probability is at least P(Yd≥log⁡n+a)−e−a\mathbb{P}(Y_d\ge\log n+a)-e^{-a}.

Since Xd=∣U∣X_d=|U| is binomial with parameters dd and pp,

Yd=dH(p)+log⁡(q/p)(Xd−dp).Y_d=dH(p)+\log(q/p)(X_d-dp).

The binomial central limit theorem gives

Yd−dH(p)dV=Xd−dpdpq⇒N(0,1).\frac{Y_d-dH(p)}{\sqrt{dV}}=\frac{X_d-dp}{\sqrt{dpq}}\Rightarrow\mathcal{N}(0,1).

Suppose that (log⁡nd−dH(p))/d→s(\log n_d-dH(p))/\sqrt{d}\to s. Taking a=d1/4a=d^{1/4} in (19), both standardized thresholds converge to s/Vs/\sqrt{V}, and e−a→0e^{-a}\to0. Continuity of Φ\Phi yields (1).

Fix 0<ε<10<\varepsilon<1 and δ>0\delta>0. Define

sε=V Φ−1(1−ε),md±=⌈exp⁡(dH(p)+(sε±δ)d)⌉.s_\varepsilon=\sqrt{V}\,\Phi^{-1}(1-\varepsilon),\qquad m_d^\pm=\left\lceil\exp\left(dH(p)+(s_\varepsilon\pm\delta)\sqrt{d}\right)\right\rceil.

Since H(p)>0H(p)>0, integer rounding changes the logarithms by o(1)o(1). Equation (1) gives

ed(md−)>ε>ed(md+)e_d(m_d^-)> \varepsilon>e_d(m_d^+)

for all sufficiently large dd. Monotonicity yields md−<nVext(ε,d)≤md+m_d^-<n_{\mathrm{V}}^{\mathrm{ext}}(\varepsilon,d)\le m_d^+. Taking logarithms, subtracting dH(p)dH(p), dividing by d\sqrt{d}, and then letting δ↓0\delta\downarrow0 gives (2). It follows that log⁡nVext(ε,d)/d→H(p)\log n_{\mathrm{V}}^{\mathrm{ext}}(\varepsilon,d)/d\to H(p); exponentiation gives (3).

Corollary 3.1. Let c>0c>0 and b≥1b\ge1 be independent of dd. Then

lim⁡d→∞eVext(⌈cbd⌉,d)={1,1≤b<Λ,12,b=Λ,0,b>Λ.\lim_{d\to\infty}e_{\mathrm{V}}^{\mathrm{ext}}\left(\left\lceil cb^d\right\rceil,d\right)= \begin{cases} 1, & 1\le b<\Lambda,\\ \frac{1}{2}, & b=\Lambda,\\ 0, & b>\Lambda. \end{cases}

Proof. For s∈Rs \in\mathbb{R}, put νd(s)=⌈exp⁡(dH(p)+sd)⌉\nu_d(s)=\lceil\exp(dH(p)+s\sqrt{d})\rceil. Since H(p)>0H(p)>0, rounding changes the logarithm by o(1)o(1), so Theorem 1.2 gives

lim⁡d→∞eVext(νd(s),d)=1−Φ(s/V).(20)\lim_{d\to\infty} e^{\mathrm{ext}}_V(\nu_d(s),d)=1-\Phi(s/\sqrt{V}). \tag*{(20)}

At b=Λb=\Lambda, Theorem 1.2 applies with s=0s=0, because log⁡⌈cΛd⌉=dH(p)+O(1)\log\lceil c\Lambda^d\rceil=dH(p)+O(1). For 1≤b<Λ1\le b<\Lambda, the relation log⁡⌈cbd⌉=dlog⁡b+O(1)\log\lceil cb^d\rceil=d\log b+O(1) implies ⌈cbd⌉≤νd(s)\lceil cb^d\rceil\le\nu_d(s) eventually, for every fixed ss. Monotonicity and (20) give a lower limit at least 1−Φ(s/V)1-\Phi(s/\sqrt{V}); letting s→−∞s\to-\infty gives one. For b>Λb>\Lambda, the comparison is reversed, so the upper limit is at most 1−Φ(s/V)1-\Phi(s/\sqrt{V}); letting s→+∞s\to+\infty gives zero. Here we use 0≤eVext(n,d)≤10\le e^{\mathrm{ext}}_V(n,d)\le1.

Cube Evaluations and Further Comparisons

Cube Evaluations

Let eF∞□(n,d)e^\square_{F^\infty}(n,d) and nF∞□(ε,d)n^\square_{F^\infty}(\varepsilon,d) be defined in the same way, with F∞F^\infty in place of BV,dB_{V,d} and nodes in [0,1]d[0,1]^d. The embedding in Proposition 2.2 and Dd□⊂DdextD^\square_d\subset D^{\mathrm{ext}}_d give

eF∞□(n,d)≥eV□(n,d)≥eVext(n,d),nF∞□(ε,d)≥nV□(ε,d)≥nVext(ε,d).e^\square_{F^\infty}(n,d)\ge e^\square_V(n,d)\ge e^{\mathrm{ext}}_V(n,d),\qquad n^\square_{F^\infty}(\varepsilon,d)\ge n^\square_V(\varepsilon,d)\ge n^{\mathrm{ext}}_V(\varepsilon,d).

Consequently, for every fixed 0<ε<10<\varepsilon<1,

lim inf⁡d→∞nV□(ε,d)1/d≥Λ,lim inf⁡d→∞nF∞□(ε,d)1/d≥Λ.\liminf_{d\to\infty}n^\square_V(\varepsilon,d)^{1/d}\ge\Lambda,\qquad\liminf_{d\to\infty}n^\square_{F^\infty}(\varepsilon,d)^{1/d}\ge\Lambda.

For fixed c>0c>0 and 1≤b<Λ1\le b<\Lambda, both eV□(⌈cbd⌉,d)e^\square_V(\lceil cb^d\rceil,d) and eF∞□(⌈cbd⌉,d)e^\square_{F^\infty}(\lceil cb^d\rceil,d) tend to one. At b=Λb=\Lambda, Theorem 1.2 and the comparison of errors give

lim inf⁡d→∞eV□(⌈cΛd⌉,d)≥12,lim inf⁡d→∞eF∞□(⌈cΛd⌉,d)≥12.\liminf_{d\to\infty}e^\square_V(\lceil c\Lambda^d\rceil,d)\ge\frac{1}{2},\qquad\liminf_{d\to\infty}e^\square_{F^\infty}(\lceil c\Lambda^d\rceil,d)\ge\frac{1}{2}.

The exponential lower bound and the subcritical error limit for F∞F^\infty were proved in [14 Theorem 1.1].

Define

β=arccos⁡(2sin⁡(1/2)),ξ±=12±β.\beta=\arccos(2\sin(1/2)),\qquad\xi_\pm=\frac{1}{2}\pm\beta.

Since cos⁡(1/2)<2sin⁡(1/2)<1\cos(1/2)<2\sin(1/2)<1, we have 0<β<1/20<\beta<1/2 and 0<ξ−<ξ+<10<\xi_-<\xi_+<1. The sine terms in (8) cancel at ξ−\xi_- and ξ+\xi_+, and cos⁡β=2sin⁡(1/2)\cos\beta=2\sin(1/2). Therefore

G=12K(ξ−)+12K(ξ+).G=\frac{1}{2}K(\xi_-)+\frac{1}{2}K(\xi_+).

Tensorization gives an exact cube quadrature formula with 2d2^d nodes on Td\mathbb{T}_d. Since every eigenvalue of GdG_d is positive, Theorem 1.1 implies

eV□(n,d)=0⟺eVext(n,d)=0⟺n≥2d.e^\square_V(n,d)=0\Longleftrightarrow e^{\mathrm{ext}}_V(n,d)=0\Longleftrightarrow n\ge2^d.

Mixed and Directional Derivatives

Coordinate mixed derivative bounds and Euclidean directional derivative bounds define different classes. For v=(v1,…,vd)∈Rdv=(v_1,\ldots,v_d)\in\mathbb{R}^d, define

Dv=∑j=1dvj∂∂xjD_v=\sum_{j=1}^{d}v_j\frac{\partial}{\partial x_j}

Let FddirF_d^{\mathrm{dir}} be the class of all f∈C∞([0,1]d;R)f\in C^\infty([0,1]^d;\mathbb{R}) such that

sup⁡x∈[0,1]d sup⁡v1,…,vk∈Sd−1∣Dv1⋯Dvkf(x)∣≤1(k∈N0).\sup_{x\in[0,1]^d}\ \sup_{v_1,\ldots,v_k\in\mathbb{S}^{d-1}}\left|D_{v_1}\cdots D_{v_k}f(x)\right|\leq1\qquad(k\in\mathbb{N}_0).

Define

Pd(x)=∏j=1dxj,vd=d−1/2(1,…,1).\mathcal{P}_d(x)=\prod_{j=1}^{d}x_j,\qquad v_d=d^{-1/2}(1,\ldots,1).

Every coordinate mixed derivative of Pd\mathcal{P}_d has supremum norm at most one, so Pd∈Fd∞\mathcal{P}_d\in F_d^\infty. In contrast,

∥DvdPd∥∞=d,\left\|D_{v_d}\mathcal{P}_d\right\|_\infty=\sqrt{d},

and Pd∉Fddir\mathcal{P}_d\notin F_d^{\mathrm{dir}} for d≥2d\geq2. The comparison agrees with the weak tractability results for directional derivative classes [3, 4].

Veronese and Derivative Norms

For 1<ρ<∞1<\rho<\infty, let Lρ=Lρ([0,1])L_\rho=L_\rho([0,1]) and let ∥⋅∥ρ\|\cdot\|_\rho denote its norm. Tensor product spaces with univariate norm

(∑k=0∞∥g(k)∥ρρ)1/ρ\left(\sum_{k=0}^{\infty}\left\|g^{(k)}\right\|_\rho^\rho\right)^{1/\rho}

are studied in [9]. The corresponding multivariate endpoint derivative norm is sup⁡α∈N0d∥Dαf∥∞\sup_{\alpha\in\mathbb{N}_0^d}\|D^\alpha f\|_\infty, whose unit ball is Fd∞F_d^\infty.

Proposition 4.1. Let d∈Nd\in\mathbb{N} and let f1,…,fd∈T1f_1,\ldots,f_d\in T_1. Then

∥f1⊗⋯⊗fd∥V,d=∏j=1d∥fj∥V,1.\left\|f_1\otimes\cdots\otimes f_d\right\|_{V,d}=\prod_{j=1}^{d}\left\|f_j\right\|_{V,1}.

Proof. The tensor product of the matrices in (9), together with (7), gives

∥f1⊗⋯⊗fd∥V,d≤∏j=1d∥fj∥V,1.\left\|f_1\otimes\cdots\otimes f_d\right\|_{V,d}\leq\prod_{j=1}^{d}\left\|f_j\right\|_{V,1}.

Write

fj(x)=c0,j+rjcos⁡(x−12−θj).f_j(x)=c_{0,j}+r_j\cos\left(x-\frac{1}{2}-\theta_j\right).

(10) gives sup⁡x∈R∣fj(x)∣=∥fj∥V,1\sup_{x\in\mathbb{R}}|f_j(x)|=\|f_j\|_{V,1}. The variables vary independently, and (13) gives the reverse estimate.

We show that the Veronese norm ∥f∥V,d\lVert f\rVert_{V,d} can be much larger than the norm ∥f∥∞,der\lVert f\rVert_{\infty,\mathrm{der}}.

Define

Cd=sup⁡0≠f∈Td∥f∥V,d∥f∥∞,der.C_d=\sup_{0\ne f\in\mathcal{T}_d}\frac{\lVert f\rVert_{V,d}}{\lVert f\rVert_{\infty,\mathrm{der}}}.

Proposition 4.2. Let d∈Nd\in\mathbb{N}. Then

(2+cos⁡12)d≤Cd≤4d.(21)\left(2+\cos\frac{1}{2}\right)^d\le C_d\le4^d. \tag*{(21)}

For d=1d=1,

C1=2+cos⁡12.(22)C_1=2+\cos\frac{1}{2}. \tag*{(22)}

Proof. Put

f∗(x)=cos⁡(x−12)−(1+cos⁡(1/2)).f_*(x)=\cos\left(x-\frac{1}{2}\right)-(1+\cos(1/2)).

Then

∥f∗∥∞,der=1,∥f∗∥V,1=2+cos⁡12.\lVert f_*\rVert_{\infty,\mathrm{der}}=1,\qquad\lVert f_*\rVert_{V,1}=2+\cos\frac{1}{2}.

Since ∥f∗⊗d∥∞,der=1\lVert f_*^{\otimes d}\rVert_{\infty,\mathrm{der}}=1, Proposition 4.1 gives the lower estimate in (21).

For the upper estimate, expand

f(x)=∑ν∈{0,1,2}dcν∏j=1dχνj(xj−12),χ0=1,χ1=cos⁡,χ2=sin⁡.f(x)=\sum_{\nu\in\{0,1,2\}^d}c_\nu\prod_{j=1}^d\chi_{\nu_j}\left(x_j-\frac{1}{2}\right),\qquad\chi_0=1,\quad\chi_1=\cos,\quad\chi_2=\sin.

Each basis tensor has V-norm one. The coefficient cνc_\nu is obtained at (1/2,…,1/2)(1/2,\ldots,1/2) by applying in coordinate jj the operator Id+∂j2\mathrm{Id}+\partial_j^2, −∂j2-\partial_j^2, or ∂j\partial_j according as νj=0,1,2\nu_j=0,1,2. Hence

∥f∥V,d≤∑ν∈{0,1,2}d∣cν∣≤4d∥f∥∞,der.\lVert f\rVert_{V,d}\le\sum_{\nu\in\{0,1,2\}^d}|c_\nu|\le4^d\lVert f\rVert_{\infty,\mathrm{der}}.

Let d=1d=1 and normalize ∥f∥∞,der=1\lVert f\rVert_{\infty,\mathrm{der}}=1. Write

f(x)=c0+c1cos⁡(x−12)+c2sin⁡(x−12),a=∣c1∣,b=∣c2∣.f(x)=c_0+c_1\cos\left(x-\frac{1}{2}\right)+c_2\sin\left(x-\frac{1}{2}\right),\qquad a=|c_1|,\quad b=|c_2|.

The values of f′f' and f′′f'' at 1/21/2 give a,b≤1a,b\le1. Put c=cos⁡(1/2)c=\cos(1/2) and t=sin⁡(1/2)t=\sin(1/2). The endpoint values give

∣c0+cc1∣+tb=max⁡{∣f(0)∣,∣f(1)∣}≤1.|c_0+cc_1|+tb=\max\{|f(0)|,|f(1)|\}\le1.

Equation (10) therefore yields

∥f∥V,1≤1+ca−tb+a2+b2.\lVert f\rVert_{V,1}\le1+ca-tb+\sqrt{a^2+b^2}.

The function on the right, without the initial one, is convex on [0,1]2[0,1]^2, so the maximum is attained at a vertex. The four values are 00, c+1c+1, 1−t1-t, and c−t+2c-t+\sqrt{2}. Since t≥12−(1/2)36=2348>2−1t\ge\frac{1}{2}-\frac{(1/2)^3}{6}=\frac{23}{48}>\sqrt{2}-1, the maximum is c+1c+1. Thus ∥f∥V,1≤2+c\lVert f\rVert_{V,1}\le2+c. The function f∗f_* gives equality in (22).

On optimal quadrature formulas

For a nonempty class B⊂C([0,1]d)\mathcal{B} \subset C([0,1]^d), write

en(B)=inf⁡x1,…,xn∈[0,1]da1,…,an∈Rsup⁡f∈B∣Sd(f)−∑i=1naif(xi)∣.e_n(\mathcal{B})=\inf_{\substack{x^1,\ldots,x^n\in[0,1]^d\\a_1,\ldots,a_n\in\mathbb{R}}}\sup_{f\in\mathcal{B}}\left|S_d(f)-\sum_{i=1}^n a_i f(x^i)\right|.

We know only a few cases where optimal quadrature formulas are known, in particular in the multivariate case, d>1d>1.

  1. Let Bdper\mathcal{B}_d^{\mathrm{per}} be the unit ball of the dd-fold Hilbert tensor product of the three-dimensional space in which 1,cos⁡(2πx),sin⁡(2πx)1,\cos(2\pi x),\sin(2\pi x) are declared orthonormal. Its minimal linear error satisfies

en(Bdper)2=max⁡{1−n2−d,0}.e_n(\mathcal{B}_d^{\mathrm{per}})^2=\max\{1-n2^{-d},0\}.

Novak [8] proved the lower bound for positive weights; Vybíral [18 Section 5] extended it to arbitrary real weights. For n≤2dn\leq2^d, equality is attained by retaining any nn nodes of {0,1/2}d\{0,1/2\}^d, each with weight 2−d2^{-d}.

Thus both this periodic problem and the exterior Veronese problem admit an exact 2d2^d-point product formula whose summands can be deleted without changing the remaining nodes or weights. In the periodic case any nn summands may be retained; in the Veronese case the nn largest weights must be retained, with arbitrary choices among ties. This deletion property does not hold if we only allow nodes inside the cube.

The Korobov-type class in [15] is defined by a weighted supremum bound on Fourier coefficients and has a different norm. The Veronese ball is instead the image of an operator-norm matrix ball; these norms define distinct integration problems.

  1. For the Hölder class

Lα,d={f:[0,1]d→R:∣f(x)−f(y)∣≤∥x−y∥∞α for all x,y∈[0,1]d},\mathcal{L}_{\alpha,d}=\{f:[0,1]^d\to\mathbb{R}:|f(x)-f(y)|\leq\lVert x-y\rVert_\infty^\alpha\text{ for all }x,y\in[0,1]^d\},

where 0<α≤10<\alpha\leq1, the quantization identity [16] gives, for n≥1n\geq1,

en(Lα,d)=inf⁡X⊂[0,1]d1≤∣X∣≤n∫[0,1]ddist⁡∞(x,X)α dx.e_n(\mathcal{L}_{\alpha,d})=\inf_{\substack{X\subset[0,1]^d\\1\leq|X|\leq n}}\int_{[0,1]^d}\operatorname{dist}_\infty(x,X)^\alpha\,dx.

If n=mdn=m^d with m∈Nm\in\mathbb{N}, the centers of the mdm^d congruent subcubes and equal weights m−dm^{-d} are optimal, and

emd(Lα,d)=dd+α(2m)−α.e_{m^d}(\mathcal{L}_{\alpha,d})=\frac{d}{d+\alpha}(2m)^{-\alpha}.
  1. Optimal univariate quadrature on Sobolev classes with derivative bounds in LρL_\rho can be characterized by minimal-norm monosplines. This was a very active research direction, see the excellent survey [21].

References

  1. [1]N. S. Bakhvalov. On the optimality of linear methods for operator approximation in convex classes of functions. U.S.S.R. Comput. Math. Math. Phys. 11(4) (1971), 244–249. doi:10.1016/0041-5553(71)90017-6.DOI
  2. [2]A. Hinrichs, D. Krieg, E. Novak and J. Vybíral. Lower bounds for the error of quadrature formulas for Hilbert spaces. J. Complexity 65 (2021), 101544. doi:10.1016/j.jco.2020.101544.DOI
  3. [3]A. Hinrichs, E. Novak and M. Ullrich. On weak tractability of the Clenshaw–Curtis Smolyak algorithm. J. Approx. Theory 183 (2014), 31–44. doi:10.1016/j.jat.2014.03.012.DOI
  4. [4]A. Hinrichs, E. Novak, M. Ullrich and H. Woźniakowski. The curse of dimensionality for numerical integration of smooth functions II. J. Complexity 30 (2014), 117–143. doi:10.1016/j.jco.2013.10.007.DOI
  5. [5]B. S. Kashin. Diameters of some finite-dimensional sets and classes of smooth functions. Math. USSR-Izv. 11(2) (1977), 317–333. doi:10.1070/IM1977v011n02ABEH001719.
  6. [6]D. Krieg and M. Ullrich. Approximation of functions: Optimal sampling and complexity. Acta Numerica 35 (2026), 273–457. doi:10.1017/S0962492925100287.DOI
  7. [7]E. Novak. Quadrature and widths. J. Approx. Theory 47(3) (1986), 195–202. doi:10.1016/0021-9045(86)90027-4.DOI
  8. [8]E. Novak. Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials. J. Complexity 15 (1999), 299–316. doi:10.1006/jcom.1999.0507.DOI
  9. [9]E. Novak and F. Pillichshammer. Intractability results for integration in tensor product spaces. J. Complexity 86 (2025), 101901. doi:10.1016/j.jco.2024.101901.DOI
  10. [10]E. Novak and H. Woźniakowski. Tractability of Multivariate Problems. Volume I. Linear Information. EMS Tracts in Mathematics 6, European Mathematical Society, Zürich, 2008. doi:10.4171/026.
  11. [11]E. Novak and H. Woźniakowski. Approximation of infinitely differentiable multivariate functions is intractable. J. Complexity 25 (2009), 398–404. doi:10.1016/j.jco.2008.11.002.DOI
  12. [12]E. Novak and H. Woźniakowski. Tractability of Multivariate Problems. Volume II. Standard Information for Functionals. EMS Tracts in Mathematics 12, European Mathematical Society, Zürich, 2010. doi:10.4171/084.
  13. [13]A. Pietsch. Eigenvalues and s-numbers. Cambridge Studies in Advanced Mathematics 13, Cambridge University Press, Cambridge, 1987.
  14. [14]E. Sengelen Sevim. The curse of dimensionality for integration of infinitely differentiable functions. J. Complexity 97 (2026), 102074. doi:10.1016/j.jco.2026.102074.
  15. [15]I. H. Sloan and H. Woźniakowski. An intractability result for multiple integration. Math. Comp. 66 (1997), 1119–1124. doi:10.1090/S0025-5718-97-00834-X.DOI
  16. [16]A. G. Sukharev. Optimal numerical integration formulas for some classes of functions of several variables. Dokl. Akad. Nauk SSSR 246(2) (1979), 282–285. English transl.: Soviet Math. Dokl. 20 (1979), 472–475. https://www.mathnet.ru/eng/dan42697.
  17. [17]V. Temlyakov. Multivariate Approximation. Cambridge Monographs on Applied and Computational Mathematics 32, Cambridge University Press, Cambridge, 2018. doi:10.1017/9781108689687.DOI
  18. [18]J. Vybiral. A variant of Schur’s product theorem and its applications. Adv. Math. 368 (2020), 107140. doi:10.1016/j.aim.2020.107140.DOI
  19. [19]J. O. Woitaszczyk. Multivariate integration in C∞([0,1]^d) is not strongly tractable. J. Complexity 19 (2003), 638–643. doi:10.1016/S0885-064X(03)00069-4.
  20. [20]H. Woźniakowski. Open problems for tractability of multivariate integration. J. Complexity 19 (2003), 434–444. doi:10.1016/S0885-064X(03)00016-5.DOI
  21. [21]A. A. Zhensykbaev. Monosplines of minimal norm and the best quadrature formulae. Russian Math. Surveys 36(4) (1981), 121–180. doi:10.1070/RM1981v036n04ABEH003024.DOI

Paper details

vlnc:W_zy6ck5k2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents