Current browse context:
math.NA
Change to browse by:
References & Citations
Mathematics > Numerical Analysis
Title: The curse of dimensionality for the $L_p$-discrepancy with finite $p$
(Submitted on 3 Mar 2023 (v1), last revised 12 Jun 2023 (this version, v2))
Abstract: The $L_p$-discrepancy is a quantitative measure for the irregularity of distribution of an $N$-element point set in the $d$-dimensional unit cube, which is closely related to the worst-case error of quasi-Monte Carlo algorithms for numerical integration. Its inverse for dimension $d$ and error threshold $\varepsilon \in (0,1)$ is the minimal number of points in $[0,1)^d$ such that the minimal normalized $L_p$-discrepancy is less or equal $\varepsilon$. It is well known, that the inverse of $L_2$-discrepancy grows exponentially fast with the dimension $d$, i.e., we have the curse of dimensionality, whereas the inverse of $L_{\infty}$-discrepancy depends exactly linearly on $d$. The behavior of inverse of $L_p$-discrepancy for general $p \not\in \{2,\infty\}$ has been an open problem for many years. In this paper we show that the $L_p$-discrepancy suffers from the curse of dimensionality for all $p$ in $(1,2]$ which are of the form $p=2 \ell/(2 \ell -1)$ with $\ell \in \mathbb{N}$.
This result follows from a more general result that we show for the worst-case error of numerical integration in an anchored Sobolev space with anchor 0 of once differentiable functions in each variable whose first derivative has finite $L_q$-norm, where $q$ is an even positive integer satisfying $1/p+1/q=1$.
Submission history
From: Friedrich Pillichshammer [view email][v1] Fri, 3 Mar 2023 08:53:29 GMT (43kb,D)
[v2] Mon, 12 Jun 2023 08:03:33 GMT (43kb,D)
Link back to: arXiv, form interface, contact.