PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Feng Dai, Andriy Prymak

arXiv:2610.07679v1math.NAcs.NAmath.CAmath.FAmath.PR

TL;DR

The paper studies how to minimize the cardinality of a norming set while keeping its uniform-norm constant controlled. It combines stable de la Vallée Poussin sampling operators with a Smolyak-type construction and proves a random norming theorem for sums of spaces on commuting regular partitions. With probability at least 1−η, ∥f∥∞≤B_{d,ε}∥f∥_{X_m} holds simultaneously for every f∈T(N,d).

  • Problem

    The paper studies how to minimize the cardinality of a norming set while keeping its uniform-norm constant controlled.

    Source: §1 · p. 2

  • Method

    It combines stable de la Vallée Poussin sampling operators with a Smolyak-type construction and proves a random norming theorem for sums of spaces on commuting regular partitions.

    Source: §1 · p. 4

  • Results

    With probability at least 1−η, ∥f∥∞≤B_{d,ε}∥f∥_{X_m} holds simultaneously for every f∈T(N,d).

    Source: §1 · p. 4

  • Takeaways & Limitations

    For frequencies in {−1,0,1}^d, a polynomially growing dimensional prefactor requires B≥e^{cd} for sufficiently large d.

    Source: §1 · p. 3

    The abstract random norming theorem assumes regular partitions whose conditional expectation operators commute.

    Source: §6.1 · p. 13

Abstract

from arXiv · show

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\ge2$ and $\varepsilon\in(0,1)$, we construct an explicit norming set with at most $\bigl(C_1(1+\varepsilon^{-1})\bigr)^{d-1}N^{1+\varepsilon}$ points and norming constant at most $\bigl(C_2(1+\varepsilon^{-1})\bigr)^{d-1}$, where $C_1,C_2$ are absolute constants. We also prove that independent Haar-distributed points achieve the same exponent $1+\varepsilon$: a sample of size at least $C(d,\varepsilon)N^{1+\varepsilon}\log(2/\eta)$ norms the entire space simultaneously with probability at least $1-\eta$, with a norming constant bounded by $\exp(C_d\varepsilon^{-d})$ and independent of $N$. The deterministic construction combines uniformly stable de la Vall\'ee 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 $\bigl(\pi d/(2e\log B)\bigr)^{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.

1. Introduction

The introduction frames uniform-norm sampling as a trade-off between the size of a norming set and its norming constant. It presents deterministic and random constructions with near-linear power scaling in N, alongside a dimension-dependent obstruction.

1. Introduction

  • The sampling problem is to minimize a norming set’s cardinality while controlling its constant; existing bounds include a dimension-two lower bound against order N up to logarithmic factors at fixed constant.A norming set W for V satisfies ∥f∥∞≤B∥f∥W for every f in V.Source: §1 · p. 2
  • The explicit construction brings the cardinality exponent arbitrarily close to 1 for fixed d, improving the earlier power bound when ε is sufficiently small.For fixed d and ε, the constants are independent of N; taking ε small worsens the norming and multiplicative constants.Source: §1 · p. 3
  • For frequencies in {−1,0,1}^d, a fixed norming constant rules out a cardinality prefactor growing only polynomially in d.If the prefactor C(d) is polynomially bounded, then B≥e^{cd} for sufficiently large d.Source: §1 · p. 3
  • Random points achieve the same 1+ε exponent as the deterministic construction and norm the entire space simultaneously with probability at least 1−η.The random norming constant is bounded independently of N; the introduction contrasts its ε-dependence with the deterministic constant.Source: §1 · p. 4
  • The deterministic construction combines uniformly stable de la Vallée Poussin sampling operators across geometric scales using a Smolyak-type identity.The hyperbolic-cross condition places active multi-indices in a bounded-width simplex; grids for its boundary layers form the norming set.Source: §1 · p. 4
  • The random proof establishes norming for sums of spaces on commuting regular partitions, then approximates hyperbolic-cross polynomials by dyadic piecewise-constant models.Matrix Chernoff bounds give empirical L2 control, which is transferred to uniform norming using contractions and an annihilating polynomial.Source: §1 · p. 4

2. Uniformly stable sampling operators

The section replaces a degree-dependent derivative estimate with exact sampling operators whose norms are uniformly bounded. Their one-dimensional properties extend to multiple variables through commuting coordinate operators.

2. Uniformly stable sampling operators

  • The construction replaces the derivative-estimate step behind the earlier logarithmic factor with exact sampling operators uniformly bounded in degree.The cited earlier estimate is identified as the source of the (log N)^(d−1) factor.Source: §2 · p. 5
  • The de la Vallée Poussin kernel is defined as K_n(t) = 2F_{2n−1}(t) − F_{n−1}(t).The section uses this kernel to construct the sampling operators.Source: §2 · p. 5
  • For every f in T([-n,n]), V_n f = f; for every f in C(T), V_n f belongs to T([-2n+1, 2n−1]), giving output frequencies bounded by 2n−1.Source: §2 · p. 5
  • Applying an operator U in coordinate j defines U^(j), and operators acting in distinct variables commute.This coordinate-wise extension lets the one-dimensional operators be used in tensor-product constructions.Source: §2 · p. 5

3. Proof of Theorem 1.1

The proof combines stable tensor-product sampling with a Smolyak identity, restricting the active scale indices for hyperbolic-cross polynomials. It then norms the polynomial using a union of tensor-product grids and establishes the bounds with specified absolute constants.

3. Proof of Theorem 1.1

  • The proof uses scales q = N^(1/r) and M_j = ⌈q^j⌉, with the sampling operators T_j defined from V_{M_j} through level r.It forms increments Δ_j = T_j − T_{j−1} and tensor products of these operators.Source: §3 · pp. 6–7
  • For f in T(N,d), the tensor increments Δ_νf vanish when |ν|_1 > L, restricting the Smolyak representation to a bounded range of scale indices.The proof derives this restriction from the hyperbolic-cross frequency condition.Source: §3 · p. 7
  • Tensor-product sampling gives ∥T_νφ∥∞ ≤ A^d∥φ∥_{W_ν}, and the proof assembles the grids W_ν into W_{d,r}(N).The grid estimates and cardinality argument yield the bounds identified in the proof.Source: §3 · pp. 8–9
  • The proof shows that (3.12) and the last cardinality estimate prove bounds (1.6) and (1.5), respectively, with constants C1 = 96 and C2 = 6eA2.Source: §3 · p. 9

4. Dependence on the dimension

The section asks whether polynomial growth in dimension of a norming set can coexist with a fixed norming constant. It shows that even for T(1,d), polynomial cardinality forces the norming constant to grow exponentially with dimension.

4. Dependence on the dimension

  • The proof uses translation invariance to cover the torus with translates of the superlevel set {F ≥ B^−1}.It then relates the covering to the volume of a Euclidean ball.Source: §4 · pp. 9–10
  • If the cardinality bound C(d) grows at most polynomially, a norming set for T(1,d) must have B ≥ e^(cd) for sufficiently large d.Here B is the norming constant in the inequality ∥f∥∞ ≤ B∥f∥_W.Source: §4 · pp. 9–10

5. A transfer principle for random sampling discretization of the uniform norm

The section develops a transfer from deterministic norming sets to random sampling for finite-dimensional translation-invariant spaces. It combines a finite-net argument with independent samples and applies the resulting principle to obtain a random-sampling bound.

5. A transfer principle for random sampling discretization of the uniform norm

  • The transfer principle links deterministic norming to random norming for finite-dimensional translation-invariant spaces.Its main link is an estimate derived from the deterministic norming inequality and translation invariance.Source: §5 · pp. 10–11
  • The theorem assumes a finite set W of size m0 with norming constant B ≥ 2 for the translation-invariant space V.The theorem concerns random samples that norm V simultaneously with high probability.Source: §5 · pp. 10–11
  • Applying the transfer argument to deterministic norming sets yields a preliminary random-sampling bound; the proof uses m0 ≤ C(d,ε)N^(1+ε/2) and absorbs a logarithmic factor into N^(ε/2).The cited estimate is log^(d−1)(2N) ≤ C(d,ε)N^(ε/2) for N ≥ 2.Source: §5 · p. 11
  • A maximal δ-separated subset of the unit ball supplies a finite net, and independence and a union bound control the probability that sample points miss its superlevel sets.The proof transfers the resulting net bound to arbitrary functions in V.Source: §5 · p. 12

6. Random norming for commuting regular partitions

The section proves a random norming theorem for sums of function spaces associated with commuting regular partitions. Its proof combines a joint orthogonal decomposition, a matrix Chernoff estimate, and an annihilating polynomial.

6. Random norming for commuting regular partitions

  • The abstract theorem applies to sums of partition-constant spaces for regular partitions whose conditional expectation operators commute.Its proof combines a joint orthogonal decomposition, a matrix Chernoff estimate, and a polynomial that annihilates the average conditional expectation.Source: §6 · p. 12, §6.1 · p. 13

6.2. The joint orthogonal decomposition.

  • Commuting projections yield a joint orthogonal decomposition, and an annihilating polynomial is constructed for their average on the sum space.The proof uses the product structure of commuting projections to establish orthogonality between distinct components.Source: §6.2 · p. 14, §6.3 · p. 15

6.3. Lemmas.

  • On the frame event, each partition cell contains a sample point, and the empirical projections approximate the original projections within 2δ in L2.A further auxiliary lemma converts a small L2 operator norm into a strict uniform-norm contraction after boundedly many iterations.Source: §6.3 · pp. 17, 19

6.4. Proof of Theorem 6.1.

  • The proof concludes with the asserted norming inequality and an absolute-constant bound.The supplied proof passages state that the inequality holds for every F in V and that C is absolute.Source: §6.4 · pp. 20–21

7. The grids of Td and the de la Vall´ee Poussin decomposition

This section builds regular grids on the torus and decomposes functions into dyadic de la Vallée Poussin pieces. The frequency localization of those pieces supports a thin-simplex description of the active scales.

The grids of T^d

  • The grids D_n are regular equal-measure partitions, and their associated projections commute according to the coordinatewise meet of their indices.Refinement follows the coordinatewise order on multi-indices.Source: §7 · p. 21

The de la Vallée Poussin decomposition

  • The dyadic operators Ψ_n split f into de la Vallée Poussin pieces whose spectra lie in the bands J_n.The stated absolute constant for the associated operator bound can be chosen as A = 6.Source: §7 · p. 22

Active indices

  • For frequencies in the hyperbolic cross, active dyadic indices satisfy |n|_1 < L + d.This confines the relevant multi-indices to a thin simplex.Source: §7 · p. 23

Simplex indices

  • Every multi-index in the stated bounded index set is dominated by an index on the simplex |m|_1 = L + d.This provides the simplex indices used to organize the multiscale construction.Source: §7 · p. 23

8. Sampling discretization of uniform norms by random points

The random construction organizes dyadic scales into retained macro-partitions and transfers approximation of hyperbolic-cross polynomials to those partitions. The proof obtains an N^(1+ε) sample scale at failure probability 1/2 and amplifies the success probability.

8.1. The macro-partitions.

  • Retained macro-partitions are regular and G-coarse, and their conditional expectation operators commute.There are at most d q^(d−1) retained indices.Source: §8.1 · p. 25

8.2. Transfer of the approximation.

  • The scale transfer assigns each active dyadic component to a refining macro-partition and approximates it by a function constant on that partition.The approximation error for each component is bounded by ϑ0 times the uniform norm of the original polynomial.Source: §8.2 · pp. 26–27
  • The union of independent sample blocks is norming whenever at least one block is norming, yielding the stated probability amplification.The block failure events are independent.Source: §8.2 · p. 27

8.3. Proof of Theorem 1.2.

  • C(d, ε)N^(1+ε) iid samples suffice for norming with probability at least 1/2.The proof then amplifies this probability for arbitrary η.Source: §8.3 · p. 29

Related papers

Loading 2610.07679v1…