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

Let \(L_{p,N}(\mathcal{P})\) be \(L_p\)-discrepancy of \(N\)-point set \(\mathcal{P}\in\mathbb{R}^d\). Assume \(\mathrm{disc}_p(N,d)=\min_{\mathcal{P}} L_{p,N}(\mathcal{P})\) and \(N^{\mathrm{disc}}_p(\varepsilon,d)=\min\{N\in\mathbb{N}:\mathrm{disc}_p(N,d)\leq \varepsilon \mathrm{disc}_p(0,d) \}\).\N\NIt is known, that \(cd\varepsilon^{-1}\leq N^{\mathrm{disc}}_{\infty}(\varepsilon,d)\leq Cd\varepsilon^{-2}\). So \( N^{\mathrm{disc}}_{\infty}(\varepsilon,d)\) depends only linearly on the dimension \(d\).\N\NBy contrast, it is proved that for \(p\in(1;\infty)\) \(N^{\mathrm{disc}}_p(\varepsilon,d)\) grows exponentially fast with the dimension \(d\). More precisely, \(N^{\mathrm{disc}}_p(\varepsilon,d) \geq C_p^d (1-2\varepsilon)\) with some \(C_p>1\).\N\NPreviously, a similar result was known only for \(p=2\).

Cites work

Cited in

(2)

This page was built for publication: The \(L_p\)-discrepancy for finite \(p>1\) suffers from the curse of dimensionality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7020425)