🔢 mathematics

High-dimensional sparse trigonometric approximation in the uniform norm and consequences for sampling recovery

This paper establishes new high-dimensional sparse trigonometric approximation results for Wiener classes in $L_q$ and $L_\infty$ norms with precise dimension-dependent constants, demonstrating that the number of terms scales quadratically with inverse accuracy and enabling tractable sampling recovery for functions with bounded mixed smoothness via $\ell_1$ -minimization.

Original authors: Moritz Moeller, Serhii Stasyuk, Tino Ullrich

Published 2026-07-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Moritz Moeller, Serhii Stasyuk, Tino Ullrich

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to describe a massive, chaotic city to a friend who has never seen it. You have a limited amount of time and only a few sentences to work with. If you try to describe every single building, street, and person, you'll run out of time before you even get to the first block. This is the "curse of dimensionality." In the world of math and science, when we try to understand things with many different variables (like temperature, humidity, wind speed, and time all at once), the amount of information needed to get a perfect picture usually explodes, growing so fast that it becomes impossible to handle.

However, many real-world signals aren't actually chaotic messes; they are "sparse." Think of a city that is mostly empty fields with just a few key landmarks. If you know the city is sparse, you don't need to describe every empty field; you just need to find the landmarks. This paper lives in the field of approximation theory, which is basically the science of the best possible shortcuts. It asks: If we have a complex, multi-dimensional function (a mathematical description of a shape or signal), how can we rebuild it using only a tiny handful of its most important parts? Specifically, the authors are looking at trigonometric approximation, which is like rebuilding a complex sound wave or image using only a few specific musical notes or colors, rather than the whole spectrum. The goal is to see if we can keep these shortcuts efficient even when the number of variables (dimensions) gets huge, without the math breaking down.

The authors of this paper, Moritz Moeller, Serhii Stasyuk, and Tino Ullrich, tackle a tricky problem: they want to know how well we can approximate these complex, high-dimensional shapes using the fewest possible "notes" (terms) while guaranteeing the result is within a specific error margin in every single detail, not just on average. In math terms, they are looking at the uniform norm, which means the error must be small everywhere, not just in an average sense. They focus on a specific type of mathematical space called Wiener classes, where the "notes" of the function decay quickly enough to be considered sparse.

Here is what they found: They proved that for these specific types of functions, you can indeed get a very accurate reconstruction using a surprisingly small number of terms, even when the dimension $d$ is large. The number of terms you need, let's call it $m$ , doesn't have to grow exponentially with the dimension (which would be a disaster). Instead, it grows in a manageable way. Specifically, to get a certain level of accuracy (let's say an error of $\varepsilon$ ), the number of terms $m$ scales at most quadratically with the inverse accuracy ( $1/\varepsilon$ ), though the exact rate also depends on a parameter $\theta$ that defines the sparsity of the function class.

The paper provides precise formulas for this. For example, if you are working with a specific class of functions defined by a parameter $\theta$ (where $0 < \theta \le 1$ ), the error you get with $m$ terms drops at a rate of $m^{-(1/\theta - 1/2)}$ . This is a very good rate. The authors also calculated the exact constants in these formulas, showing that the influence of the dimension $d$ is kept under control, mostly appearing as a harmless logarithmic term (like $\log(d)$ ) rather than a scary exponential one.

To get these results, the team used a clever two-step strategy. First, they looked at the problem in a "softer" setting (the $L_q$ norm, which is like an average error) where the math is easier, and they proved that the constants there don't explode as the dimension grows. Then, they used a refined version of a classic tool called Nikol'skii's inequality to "extrapolate" those results to the strict "uniform norm" (the worst-case error). This step was crucial because it allowed them to show that even in the strictest sense, the dimension $d$ only adds a small, logarithmic penalty to the size of the spectrum (the range of frequencies used), rather than ruining the whole approximation.

The paper also connects this to sampling recovery, which is the practical problem of reconstructing a function from a limited number of measurements (like taking a few photos of a 3D object). They show that because their sparse approximation works so well, you can recover these high-dimensional functions from a limited number of samples using a technique called $\ell_1$ -minimization (a method popular in compressed sensing). The result is that for these specific classes of functions, the problem is "tractable," meaning it is solvable in a reasonable amount of time and with a reasonable amount of data, even as the number of variables increases.

One thing the paper is careful to note is that these specific, clean results apply to functions with a certain type of sparsity (the $\ell_1$ -summability condition). If the functions don't have this specific structure, or if you look at different types of smoothness spaces (like those with $\theta = \infty$ ), the math gets messier, and you might see extra logarithmic factors popping up. But for the classes they studied, the "curse of dimensionality" is effectively tamed. They didn't just guess this; they provided rigorous mathematical proofs with explicit constants, showing exactly how the error behaves. For instance, they showed that for a specific case involving Besov spaces with mixed smoothness, the error in the uniform norm is bounded by a formula involving $d \log(d)$ and a decay rate of $m^{-1/2}$ , proving that the dimension's impact is far less severe than previously feared for these specific types of signals.

In short, this paper is a victory for efficiency in high-dimensional math. It proves that if a signal is sparse enough, we don't need to fear the number of variables. We can pick out the few most important "notes" to rebuild the whole song, and the math guarantees that we won't need a million notes just because the song has a million dimensions. The authors have given us the precise map for how many notes we need and how the size of the city (the dimension) affects the journey, ensuring that the path remains walkable even as the city grows.

Technical Summary: High-dimensional sparse trigonometric approximation in the uniform norm and consequences for sampling recovery

Problem Statement
The paper addresses the challenge of reconstructing high-dimensional multivariate functions from a limited number of function samples, a task often hindered by the "curse of dimensionality." Specifically, the authors investigate the recovery of functions belonging to Wiener classes and Besov spaces with mixed smoothness. The central problem is to establish precise bounds for the best $m$ -term trigonometric approximation error in the uniform norm ( $L_\infty$ ) and to determine how these bounds scale with the dimension $d$ . The ultimate goal is to translate these approximation results into guarantees for non-linear sampling recovery (using $m$ function values) in the $L_2$ norm, thereby assessing the tractability of the problem.

Methodology
The authors employ a three-step strategy to bridge the gap between $L_q$ and $L_\infty$ approximation in high dimensions:

Probabilistic $L_q$ Approximation: For the Wiener algebra $A_\theta$ (defined by $\ell_\theta$ -summability of Fourier coefficients) and related Besov spaces, the authors derive upper and lower bounds for the best $m$ -term approximation error in $L_q$ ( $2 \le q < \infty$ ). Unlike previous works that relied on greedy algorithms without tracking dimension-dependent constants, this paper utilizes a probabilistic approach based on the random selection of coefficients (inspired by [19]) and the Bernstein inequality. This allows for the explicit tracking of constants, demonstrating that the error bounds scale polynomially with $d$ and $q$ .
Refined Nikol'skii Inequality: To extend the $L_q$ results to the uniform norm ( $L_\infty$ ), the authors prove a sharpened version of the classical Nikol'skii inequality (Theorem 3.1). This inequality relates the $L_\infty$ norm to the $L_q$ norm for trigonometric polynomials with frequencies in a rectangular box $[-N, N]^d$ . Crucially, the constant in this inequality is controlled such that it grows only polynomially (or logarithmically) with $d$ when $q$ is chosen appropriately (specifically $q \sim \log(d)\log(\#Q)$ ). This avoids the exponential growth in $d$ typical of classical proofs.
Interpolation and Extrapolation: Using interpolation arguments (specifically the $K$ -method and Hausdorff-Young inequalities), the results are extended to different parameter regimes for $\theta$ and $q$ . Finally, the established $L_\infty$ approximation bounds are combined with a known relationship between non-linear sampling numbers and best $m$ -term approximation errors (from [14]) to derive sampling recovery rates.

Key Contributions and Results

Precise Constants for $L_q$ Approximation: The paper provides explicit constants for the best $m$ -term approximation widths $\sigma_m(A_\theta; \mathcal{T}^d)_{L_q}$ . For $2 \le q < \infty$ and $0 < \theta \le 1$ , the upper bound is shown to be $C \sqrt{q} m^{-(1/\theta - 1/2)}$ , where the constant $C$ is independent of the dimension $d$ (Theorem 4.4). Lower bounds are also established with precise constants.
Dimension-Dependent $L_\infty$ Bounds: By combining the $L_q$ results with the refined Nikol'skii inequality, the authors derive bounds for the uniform norm. For trigonometric polynomials with support size $\#Q$ , the error satisfies:
$\sigma_{4m}(t; \mathcal{T}^d)_{L_\infty} \lesssim \log(d)^{1/2} m^{-(1/\theta - 1/2)} (\log \#Q)^{1/2} \|t\|_{A_\theta}$
(Theorem 4.5). This result demonstrates that the influence of the dimension $d$ is confined to a logarithmic factor in the support size and a polynomial factor in $d$ , rather than an exponential one.
Results for Besov Spaces: The findings are extended to Besov spaces with dominating mixed smoothness, denoted $B^r_{p,\theta}$ . For the limiting mixed smoothness case $r = 1/\theta - 1/2$ , the paper establishes that the best $m$ -term approximation error in $L_\infty$ decays at a rate of $m^{-(1/\theta - 1/2)}$ , with the dimension dependence appearing as $d \log(d)^{1/2}$ (Theorem 5.3).
Sampling Recovery Implications: The paper translates these approximation results into bounds for non-linear sampling numbers $\varrho_m$ in the $L_2$ norm. Using the relation from [14], it is shown that for functions in these classes, the sampling recovery error decays polynomially with $m$ , and the dependence on dimension $d$ is at most polynomial (specifically $O(d^2)$ or similar, depending on parameters) up to logarithmic factors (Corollary 5.4). This confirms the polynomial tractability of the sampling recovery problem for these specific function classes.

Significance and Claims
The authors claim that their work provides a "tractable" solution to high-dimensional sampling recovery for specific sparse function classes. The primary significance lies in:

Control of Dimensionality: The paper demonstrates that for Wiener and related Besov classes, the curse of dimensionality can be avoided. The recovery error depends polynomially on $d$ rather than exponentially.
Explicit Constants: Unlike many asymptotic results in approximation theory, this paper provides precise, dimension-independent (or polynomially dependent) constants for the approximation widths. This is essential for practical applications and for establishing rigorous tractability results.
Extension to Uniform Norm: The paper successfully bridges the gap between $L_q$ and $L_\infty$ approximation in high dimensions using a refined Nikol'skii inequality, a step that was previously not fully quantified with respect to dimension.
Complement to Existing Literature: The results complement recent polynomial tractability findings by Krieg [16] and refine the understanding of the relationship between sparse trigonometric approximation and non-linear sampling numbers established in [14].

The paper concludes that for functions with $\ell_\theta$ -sparsity (where $\theta \le 1$ ), the influence of dimension is manageable, making the recovery of such functions via $\ell_1$ -minimization (or related non-linear methods) feasible in high-dimensional settings.

More like this