We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

math.NA

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Mathematics > Numerical Analysis

Title: The $L_p$-discrepancy for finite $p>1$ suffers from the curse of dimensionality

Abstract: The $L_p$-discrepancy is a classical quantitative measure for the irregularity of distribution of an $N$-element point set in the $d$-dimensional unit cube. Its inverse for dimension $d$ and error threshold $\varepsilon \in (0,1)$ is the number of points in $[0,1)^d$ that is required 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\}$ was an open problem since many years. Recently, the curse of dimensionality for the $L_p$-discrepancy was shown for an infinite sequence of values $p$ in $(1,2]$, but the general result seemed to be out of reach. In the present paper we show that the $L_p$-discrepancy suffers from the curse of dimensionality for all $p$ in $(1,\infty)$ and only the case $p=1$ is still open. This result follows from a more general result that we show for the worst-case error of positive quadrature formulas for an anchored Sobolev space of once differentiable functions in each variable whose first mixed derivative has finite $L_q$-norm, where $q$ is the H\"older conjugate of $p$.
Comments: arXiv admin note: substantial text overlap with arXiv:2303.01787
Subjects: Numerical Analysis (math.NA)
MSC classes: 11K38, 65C05, 65Y20
Cite as: arXiv:2403.07961 [math.NA]
  (or arXiv:2403.07961v2 [math.NA] for this version)

Submission history

From: Friedrich Pillichshammer [view email]
[v1] Tue, 12 Mar 2024 09:47:26 GMT (44kb,D)
[v2] Tue, 26 Mar 2024 19:34:23 GMT (53kb,D)

Link back to: arXiv, form interface, contact.