The curse of dimensionality for the L_p-discrepancy with finite p
share
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 ε∈ (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 ε. 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_∞-discrepancy depends exactly linearly on d. The behavior of inverse of L_p-discrepancy for general p ∉{2,∞} is an open problem since many years. In this paper we show that the L_p-discrepancy suffers from the curse of dimensionality for all p which are of the form p=2 ℓ/(2 ℓ -1) with ℓ∈ℕ. 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.
READ FULL TEXT