The star discrepancy is a quantitative measure of the uniformity of a point set in the unit cube. A central quantity of interest is the inverse of the star discrepancy, N ( ε , s ) , defined as the minimum number of points required to achieve a star discrepancy of at most ε in dimension s . It is known that N ( ε , s ) depends only linearly on the dimension s . Finding explicit point set constructions that achieve this optimal linear dependence on the dimension remains a major open problem. In this paper, we make progress on this question by analyzing point sets constructed from a multiset union of digitally shifted Korobov polynomial lattice point sets. Specifically, we show the following two results. A union of randomly generated Korobov polynomial lattice point sets shifted by a random digital shift of depth m can achieve a star discrepancy whose inverse depends only linearly on s . The second result shows that a union of all Korobov polynomial lattice point sets, each shifted by a different random digital shift, achieves the same star discrepancy bound. While our proof relies on a concentration result (Bernstein's inequality) and is therefore non-constructive, it significantly reduces the search space for such point sets from a continuum of possibilities to a finite set of candidates, marking a step towards a fully explicit construction.

We study the L p -discrepancy of random point sets in high dimensions, with emphasis on small values of p . Although the classical L p -discrepancy suffers from the curse of dimensionality for all p ∈ ( 1 , ∞ ) , the gap between known upper and lower bounds remains substantial, in particular for small p ≥ 1 . To clarify this picture, we review the existing results for i.i.d. uniformly distributed points and derive new upper bounds for generalized L p -discrepancies, obtained by allowing non-uniform sampling densities and corresponding non-negative quadrature weights. Using the probabilistic method, we show that random points drawn from optimally chosen product densities lead to significantly improved upper bounds. For p = 2 these bounds are explicit and optimal; for general p ∈ [ 1 , ∞ ) we obtain sharp asymptotic estimates. The improvement can be interpreted as a form of importance sampling for the underlying Sobolev space F d , q . Our results also reveal that, even with optimal densities, the curse of dimensionality persists for random points when p ≥ 1 , and it becomes most pronounced for small p . This suggests that the curse should also hold for the classical L 1 -discrepancy for deterministic point sets.

We prove lower bounds on the worst-case error of numerical integration in tensor product spaces. The information complexity is the minimal number N of function evaluations that is necessary such that the N -th minimal error is less than a factor ε times the initial error, i.e., the error for N = 0 , where ε belongs to ( 0 , 1 ) . We are interested to which extent the information complexity depends on the number d of variables of the integrands. If the information complexity grows exponentially fast in d , then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem, we present two methods for providing lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function and can be seen as a generalization of the method of decomposable reproducing kernels. The second method, although only applicable for positive quadrature rules, does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. Several applications of both methods are presented.

In this paper we consider integration and L2-approximation for functions over Rs from weighted Hermite spaces. The first part of the paper is devoted to a comparison of several weighted Hermite spaces that appear in literature, which is interesting on its own. Then we study tractability of the integration and L2-approximation problem for the introduced Hermite spaces, which describes the growth rate of the information complexity when the error threshold ε tends to 0 and the problem dimension s grows to infinity. Our main results are characterizations of tractability in terms of the involved weights, which model the importance of the successive coordinate directions for functions from the weighted Hermite spaces.

The Lp-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. It's inverse for dimension d and error threshold ε∈(0,1) is the minimal number of points in [0,1)d such that the minimal normalized Lp-discrepancy is less or equal ε. It is well known, that the inverse of L2-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 Lp-discrepancy for general p∉{2,∞} has been an open problem for many years. In this paper we show that the Lp-discrepancy suffers from the curse of dimensionality for all p in (1,2] which are of the form p=2ℓ/(2ℓ−1) with ℓ∈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 Lq-norm, where q is an even positive integer satisfying 1/p+1/q=1.

The constant center frequency to bandwidth ratio (Q-factor) of wavelet transforms provides a very natural representation for audio data. However, invertible wavelet transforms have either required non-uniform decimation—leading to irregular data structures that are cumbersome to work with—or require excessively high oversampling with unacceptable computational overhead. Here, we present a novel decimation strategy for wavelet transforms that leads to stable representations with oversampling rates close to one and uniform decimation. Specifically, we show that finite implementations of the resulting representation are energy-preserving in the sense of frame theory. The obtained wavelet coefficients can be stored in a time-frequency matrix with a natural interpretation of columns as time frames and rows as frequency channels. This matrix structure immediately grants access to a large number of algorithms that are successfully used in time-frequency audio processing, but could not previously be used jointly with wavelet transforms. We demonstrate the application of our method in processing based on nonnegative matrix factorization, in onset detection, and in phaseless reconstruction.

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals needed to obtain an ε-approximation for the d-variate problem which is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function that depends polynomially on d and logarithmically on ε−1. The corresponding unweighted problem was studied in Hickernell et al. (2020) with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on d and logarithmic dependence on ε−1, we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential (s,t)-weak tractability with max(s,t)≥1. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential (s,t)-weak tractability with max(s,t)<1 is left for future study. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019).