Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On $L_2$-approximation in Hilbert spaces using function values

David Krieg, Mario Ullrich

Published May 7, 2019• 6 citations
OpenAlex

Abstract

We study $L_2$-approximation of functions from Hilbert spaces $H$ in which function evaluation is a continuous linear functional, using function values as information. Under certain assumptions on $H$, we prove that the $n$-th minimal worst-case error $e_n$ satisfies \[ e_n \,\lesssim\, a_{n/\log(n)}, \] where $a_n$ is the $n$-th minimal worst-case error for algorithms using arbitrary linear information, i.e., the $n$-th approximation number. Our result applies, in particular, to Sobolev spaces with dominating mixed smoothness $H=H^s_{\rm mix}(\mathbb{T}^d)$ with $s>1/2$ and we obtain \[ e_n \,\lesssim\, n^{-s} \log^{sd}(n). \] This improves upon previous bounds whenever $d>2s+1$.

Related papers

Function Values Are Enough for $$L_2$$-Approximation

David Krieg, Mario Ullrich

Abstract We study the $$L_2$$ L 2 -approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number $$e_n$$ e n is the minimal worst-case error that can be achieved with n function values, whereas the approximation number $$a_n$$ a n is the minimal worst-case error that can be achieved with n pieces of arbitrary linear information (like derivatives or Fourier coefficients). We show that $$\begin{aligned} e_n \,\lesssim \, \sqrt{\frac{1}{k_n} \sum _{j\ge k_n} a_j^2}, \end{aligned}$$ e n ≲ 1 k n ∑ j ≥ k n a j 2 , where $$k_n \asymp n/\log (n)$$ k n ≍ n / log ( n ) . This proves that the sampling numbers decay with the same polynomial rate as the approximation numbers and therefore that function values are basically as powerful as arbitrary linear information if the approximation numbers are square-summable. Our result applies, in particular, to Sobolev spaces $$H^s_\mathrm{mix}(\mathbb {T}^d)$$ H mix s ( T d ) with dominating mixed smoothness $$s>1/2$$ s > 1 / 2 and dimension $$d\in \mathbb {N}$$ d ∈ N , and we obtain $$\begin{aligned} e_n \,\lesssim \, n^{-s} \log ^{sd}(n). \end{aligned}$$ e n ≲ n <mm

arXiv:1905.02516•Foundations of Computational Mathematics•Dec 7, 2020•15 citations

The power of standard information for multivariate approximation in the randomized setting

G.W. Wasilkowski, H. Woźniakowski

We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted $L_2$-norm. We consider functions with an arbitrarily large number of variables, $d$, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the $n$th minimal errors, i.e., of the minimal errors among all algorithms using $n$ function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor $\varepsilon$ is polynomial in $\varepsilon ^{-1}$ (strong tractability), and polynomial in $d$ and $\varepsilon ^{-1}$ (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of $d$, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.

Mathematics of Computation•Dec 13, 2006•35 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ of all algorithms that use $N$ information evaluations from the class $\Lambda$ in the $d$-dimensional case. The two classes $\Lambda$ considered in this paper are the class $\Lambda^{{\rm all}}$ consisting of all linear functionals and the class $\Lambda^{{\rm std}}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

arXiv:1701.02910•Functiones et Approximatio Commentarii Mathematici•May 4, 2017•1 citation

Worst case tractability of $L_2$-approximation for weighted Korobov spaces

Huichao Yan, Jia Chen

We study $L_2$-approximation problems $\text{APP}_d$ in the worst case setting in the weighted Korobov spaces $H_{d,\a,{\bm \ga}}$ with parameter sequences ${\bm \ga}=\{\ga_j\}$ and $\a=\{\az_j\}$ of positive real numbers $1\ge \ga_1\ge \ga_2\ge \cdots\ge 0$ and $\frac1 2<\az_1\le \az_2\le \cdots$. We consider the minimal worst case error $e(n,\text{APP}_d)$ of algorithms that use $n$ arbitrary continuous linear functionals with $d$ variables. We study polynomial convergence of the minimal worst case error, which means that $e(n,\text{APP}_d)$ converges to zero polynomially fast with increasing $n$. We recall the notions of polynomial, strongly polynomial, weak and $(t_1,t_2)$-weak tractability. In particular, polynomial tractability means that we need a polynomial number of arbitrary continuous linear functionals in $d$ and $\va^{-1}$ with the accuracy $\va$ of the approximation. We obtain that the matching necessary and sufficient condition on the sequences ${\bm \ga}$ and $\a$ for strongly polynomial tractability or polynomial tractability is $$\dz:=\liminf_{j\to\infty}\frac{\ln \ga_j^{-1}}{\ln j}>0,$$ and the exponent of strongly polynomial tractability is $$p^{\text{str}}=2\max\big\{\frac 1 \dz, \frac 1 {2\az_1}\big\}.$$

arXiv:2308.13753•Aug 26, 2023•0 citations

Multi- and infinite-variate integration and 𝐿²-approximation on Hilbert spaces with Gaussian kernels

Michael Gnewuch, Klaus Ritter, Robin Rüßmann

We study integration and L 2 L^2 -approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n n -th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.

arXiv:2412.05368•Mathematics of Computation•Jan 12, 2026•3 citations

Tractability of $ L_2 $-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting

Weiran Ding, Jiansong Li, Yumeng Jia +1 more

This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.

Electronic Research Archive•Jan 1, 2025•0 citations
On L2L_2L2​-approximation in Hilbert spaces using function values
We study L2L_2L2​-approximation of functions from Hilbert spaces HHH in which
function evaluation is a continuous linear functional, using function values as
information. Under certain assumptions on HHH, we prove that the nnn-th minimal
worst-case error ene_nen​ satisfies [ e_n ,\lesssim, a_{n/\log(n)}, ] where
ana_nan​ is the nnn-th minimal worst-case error for algorithms using arbitrary
linear information, i.e., the nnn-th approximation number. Our result applies,
in particular, to Sobolev spaces with dominating mixed smoothness H=Hmixs(Td)H=H^s_{\rm mix}(\mathbb{T}^d)H=Hmixs​(Td) with s>1/2s>1/2s>1/2 and we obtain [ e_n ,\lesssim, n^{-s}
\log^{sd}(n). ] This improves upon previous bounds whenever d>2s+1d>2s+1d>2s+1.
Function Values Are Enough for L2L_2L2​-Approximation
Abstract We study the L2L_2L2​ L 2 -approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number ene_nen​ e n is the minimal worst-case error that can be achieved with n function values, whereas the approximation number ana_nan​ a n is the minimal worst-case error that can be achieved with n pieces of arbitrary linear information (like derivatives or Fourier coefficients). We show that en ≲ 1kn∑j≥knaj2,\begin{aligned} e_n \,\lesssim \, \sqrt{\frac{1}{k_n} \sum _{j\ge k_n} a_j^2}, \end{aligned}en​≲kn​1​j≥kn​∑​aj2​​,​ e n ≲ 1 k n ∑ j ≥ k n a j 2 , where kn≍n/log⁡(n)k_n \asymp n/\log (n)kn​≍n/log(n) k n ≍ n / log ( n ) . This proves that the sampling numbers decay with the same polynomial rate as the approximation numbers and therefore that function values are basically as powerful as arbitrary linear information if the approximation numbers are square-summable. Our result applies, in particular, to Sobolev spaces Hmixs(Td)H^s_\mathrm{mix}(\mathbb {T}^d)Hmixs​(Td) H mix s ( T d ) with dominating mixed smoothness s>1/2s>1/2s>1/2 s > 1 / 2 and dimension d∈Nd\in \mathbb {N}d∈N d ∈ N , and we obtain en ≲ n−slog⁡sd(n).\begin{aligned} e_n \,\lesssim \, n^{-s} \log ^{sd}(n). \end{aligned}en​≲n−slogsd(n).​ e n ≲ n <mm
We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted L2L_2L2​-norm. We consider functions with an arbitrarily large number of variables, ddd, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the nnnth minimal errors, i.e., of the minimal errors among all algorithms using nnn function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor ε\varepsilonε is polynomial in ε−1\varepsilon ^{-1}ε−1 (strong tractability), and polynomial in ddd and ε−1\varepsilon ^{-1}ε−1 (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of ddd, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class Λ\LambdaΛ in the ddd-dimensional case. The two classes Λ\LambdaΛ considered in this paper are the class Λall\Lambda^{{\rm all}}Λall consisting of all linear functionals and the class Λstd\Lambda^{{\rm std}}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
Worst case tractability of L2L_2L2​-approximation for weighted Korobov spaces
We study L2L_2L2​-approximation problems APPd\text{APP}_dAPPd​ in the worst case setting in the weighted Korobov spaces $H_{d,\a,{\bm \ga}}$ with parameter sequences ${\bm \ga}=\{\ga_j\}$ and $\a=\{\az_j\}$ of positive real numbers $1\ge \ga_1\ge \ga_2\ge \cdots\ge 0$ and $\frac1 2<\az_1\le \az_2\le \cdots$. We consider the minimal worst case error e(n,APPd)e(n,\text{APP}_d)e(n,APPd​) of algorithms that use nnn arbitrary continuous linear functionals with ddd variables. We study polynomial convergence of the minimal worst case error, which means that e(n,APPd)e(n,\text{APP}_d)e(n,APPd​) converges to zero polynomially fast with increasing nnn. We recall the notions of polynomial, strongly polynomial, weak and (t1,t2)(t_1,t_2)(t1​,t2​)-weak tractability. In particular, polynomial tractability means that we need a polynomial number of arbitrary continuous linear functionals in ddd and $\va^{-1}$ with the accuracy $\va$ of the approximation. We obtain that the matching necessary and sufficient condition on the sequences ${\bm \ga}$ and $\a$ for strongly polynomial tractability or polynomial tractability is $$\dz:=\liminf_{j\to\infty}\frac{\ln \ga_j^{-1}}{\ln j}>0,$$ and the exponent of strongly polynomial tractability is $$p^{\text{str}}=2\max\big\{\frac 1 \dz, \frac 1 {2\az_1}\big\}.$$
We study integration and L 2 L^2 -approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n n -th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.
This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.