Sampling discretization of the uniform norm for hyperbolic-cross trigonometric polynomials

Abstract

We study sampling discretization of the uniform norm for trigonometric polynomials with frequencies in a hyperbolic cross of level $N$ on $\T^d$. For every $d,N\ge 2$ and $\epsilon \in (0,1)$, we construct an explicit norming set with at most $(C_1(1+{\epsilon }^{-1}){)}^{d-1}{N}^{1+\epsilon }$ points and norming constant at most $(C_2(1+{\epsilon }^{-1}){)}^{d-1}$, where $C_1,C_2$ are absolute constants. We also prove that independent Haar-distributed points achieve the same exponent $1+\epsilon$: a sample of size at least $C(d,\epsilon )N^{1+\epsilon }\log (2/\eta )$ norms the entire space simultaneously with probability at least $1-\eta$, with a norming constant bounded by $\exp (C_d{\epsilon }^{-d})$ and independent of $N$. The deterministic construction combines uniformly stable de la Vallée Poussin sampling operators with a Smolyak-type combination identity. The random result follows from an abstract norming theorem for sums of spaces associated with commuting regular partitions, together with a multiscale approximation of hyperbolic-cross polynomials. Finally, we show that every norming set of constant $B>1$ for the trigonometric polynomials with frequencies in $\{-1,0,1{\}}^d$ has at least $(\pi d/(2e\log B){)}^{d/2}$ points. This rules out quadratic bounds in the dimension of the polynomial space with a prefactor growing only polynomially in $d$ when the norming constant is fixed.