🔢 mathematics

Universal, sample-optimal algorithms for recovery of anisotropic functions from i.i.d. samples

This paper introduces a nonadaptive, universal algorithm based on compressed sensing that achieves near-optimal recovery rates for high-dimensional anisotropic functions from i.i.d. samples, while proving that such nonlinear approaches are necessary to avoid the suboptimal, dimension-dependent performance of universal linear algorithms.

Original authors: Ben Adcock (Simon Fraser University, Canada), Avi Gupta (Simon Fraser University, Canada)

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben Adcock (Simon Fraser University, Canada), Avi Gupta (Simon Fraser University, Canada)

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 reconstruct a complex, multi-layered painting, but you can only see a few scattered pixels at a time. This is the core challenge of high-dimensional function approximation. In the real world, this happens when scientists try to model everything from the weather (which depends on temperature, pressure, humidity, wind speed, etc.) to financial markets or quantum physics.

The problem gets even trickier when the painting is anisotropic.

The "Anisotropic" Puzzle

Think of a standard, smooth painting where every part is equally detailed. That's isotropic. But imagine a painting where the sky is painted with broad, smooth brushstrokes, but the foreground trees are painted with incredibly fine, jagged detail. The "smoothness" varies depending on which direction you look. This is anisotropy.

In many real-world problems, we don't know which parts are smooth and which are rough. We don't know the "brushstroke style" of the function we are trying to learn. We just know it exists.

The Goal: A Universal Algorithm

The authors of this paper asked: Can we build a single "universal" algorithm that works perfectly, no matter how the smoothness is distributed?

Usually, algorithms are like specialized tools: a hammer is great for nails but terrible for screws. If you don't know if you're dealing with nails or screws, you're stuck. The authors wanted a "Swiss Army Knife" that could handle any combination of smooth and rough areas without needing to be told what it's looking at beforehand.

The Solution: Compressed Sensing as a Detective

The authors developed a new method based on Compressed Sensing. Here is the analogy:

Imagine you are a detective trying to solve a crime in a massive city (the high-dimensional space). You know the criminal is hiding in a specific building, but you don't know which one.

The Old Way (Linear): You send a police officer to check every single building one by one. This is slow and inefficient. In math terms, this is a "linear algorithm."
The New Way (Nonlinear/Compressed Sensing): You use a clever strategy. You ask a few specific questions (take a few samples) that, when combined, instantly point to the most likely suspects. You ignore the empty buildings and focus only on the "sparse" clues that matter.

The paper shows that by treating the function as a collection of Fourier coefficients (think of these as the ingredients in a recipe) and using a mathematical technique called SR-LASSO (a type of optimization), they can reconstruct the whole function from very few random samples.

The Big Discovery: You Need a "Smart" Algorithm

The most surprising finding of the paper is about Linearity vs. Nonlinearity.

Linear Algorithms are like a rigid, pre-set rulebook. They try to apply the same logic to every part of the problem. The authors proved that if you try to use a rigid, linear rulebook to solve this "unknown smoothness" puzzle, you hit a Curse of Dimensionality.
- The Metaphor: Imagine trying to find a needle in a haystack. A linear algorithm is like a robot that checks every single straw one by one. As the haystack gets bigger (more dimensions), the time it takes explodes. The paper shows that linear algorithms suffer a penalty that grows like $(\log m)^{d-1}$ , where $d$ is the number of variables. If you have 10 variables, this penalty is huge.
Nonlinear Algorithms are like a smart detective who can adapt. They can look at the data and decide, "Okay, this part is smooth, let's ignore the noise there," or "This part is rough, let's focus here."
- The Metaphor: The smart detective ignores the empty parts of the haystack and goes straight to the spot where the needle is likely to be. The penalty for this smart approach is tiny and doesn't explode with the number of variables.

Why This Matters

Universality: You don't need to know the "smoothness" of your data in advance. The algorithm figures it out on the fly.
Efficiency: You can get a very accurate picture of a complex system using far fewer samples than previously thought possible.
The "Curse" is Real: The paper proves that if you try to use simple, linear methods for these universal problems, you will fail as the complexity grows. You must use these smarter, nonlinear methods to succeed.

Summary in a Nutshell

The paper is about building a universal, smart scanner for complex, multi-dimensional data. It proves that:

We can recover these complex functions from random samples almost as fast as the theoretical limit allows.
We don't need to know the details of the function beforehand.
Crucially, we cannot do this with simple, rigid math (linear methods). We need "smart," adaptive math (nonlinear methods) to avoid getting lost in the complexity of high dimensions.

It's the difference between trying to map a continent by walking every inch of it (linear) versus using a satellite to instantly spot the cities and roads (nonlinear).

1. Problem Statement

The paper addresses the high-dimensional approximation of periodic functions $f: \mathbb{T}^d \to \mathbb{C}$ (where $d \gg 1$ ) that exhibit anisotropic smoothness. Anisotropy implies that the function's smoothness varies across different coordinate directions.

The Challenge: In many practical settings (e.g., black-box simulations), the specific anisotropic parameters (the degree of smoothness in each direction) are unknown a priori.
The Goal: Develop universal algorithms that can recover these functions from a limited number of pointwise samples ( $m$ ) with near-optimal convergence rates, regardless of the specific anisotropic parameters, without needing to adaptively learn the smoothness first.
Function Classes: The authors focus on two types of anisotropic Sobolev spaces on the $d$ $d$ -dimensional torus:
1. Anisotropic Dominating Mixed Smoothness ( $H^\alpha_{\text{mix}}$ ): Characterized by a product structure of smoothness parameters $\alpha = (\alpha_1, \dots, \alpha_d)$ .
2. Anisotropic Sobolev Spaces ( $H^\beta$ ): Characterized by a sum structure of smoothness parameters $\beta = (\beta_1, \dots, \beta_d)$ .

2. Methodology

The authors employ a framework combining Compressed Sensing (CS) and Sparse Recovery techniques.

Sparse Representation: The problem is recast as recovering the Fourier coefficients of the function. Theoretical results (Section 2) establish that functions in these anisotropic spaces have Fourier coefficients that are "sparse" in a specific sense (they belong to weak $\ell_p$ spaces with specific decay rates).
Algorithm Construction:
- Sampling: The algorithm uses $m$ independent and identically distributed (i.i.d.) samples drawn from the uniform measure on $\mathbb{T}^d$ .
- Truncation: A hyperbolic cross index set $\Lambda_r$ is selected to truncate the infinite Fourier series.
- Recovery: The recovery is formulated as a sparse recovery problem $b = A\hat{f}_\Lambda + v$ , where $A$ is a normalized Fourier matrix.
- Decoder: The authors utilize the Square-Root LASSO (SR-LASSO) decoder to solve the optimization problem:
  $\min_{z} \lambda \|z\|_1 + \|Az - b\|_2$
  This approach is non-adaptive; the algorithm structure is fixed and does not change based on the data to estimate smoothness.
Theoretical Tools:
- Stechkin's Inequalities: Used to bound the best $s$ -term approximation errors in terms of the function norms.
- Restricted Isometry Property (RIP) / rNSP: The authors prove that random Fourier matrices satisfy the $\ell_2$ -robust Null Space Property with high probability, ensuring stable recovery via SR-LASSO.

3. Key Contributions

A. Existence of Universal Algorithms (Upper Bounds)

The paper constructs explicit reconstruction maps $R$ that achieve near-optimal rates for any anisotropy parameter $\alpha$ or $\beta$ (within reasonable bounds, e.g., $>1/2$ ).

Rates for $H^\alpha_{\text{mix}}$ : The error decays as:
$\left( \frac{\log^{p(\alpha)-1}(\tilde{m})}{\tilde{m}} \right)^{h(\alpha)}$
where $h(\alpha) = \min \alpha_i$ and $p(\alpha)$ is the number of indices achieving this minimum.
Rates for $H^\beta$ : The error decays as:
$\left( \frac{1}{\tilde{m}} \right)^{g(\beta)}$
where $g(\beta) = (\sum \beta_j^{-1})^{-1}$ .
Sample Efficiency: The effective sample size $\tilde{m}$ is $m$ divided by polylogarithmic factors ( $\log^3 m \log \log m$ ).
Universality: The algorithm is non-adaptive. It does not attempt to estimate the smoothness parameters $\alpha$ or $\beta$ from the data; the same map works for the entire class of functions.

B. Optimality of Rates (Lower Bounds)

The authors prove that the derived rates are optimal up to the polylogarithmic factors.

They establish lower bounds for the adaptive $m$ -width (the best possible error achievable by any adaptive linear or nonlinear algorithm using $m$ measurements) for the unit balls of these spaces.
The lower bounds match the upper bounds of their universal algorithms, confirming that i.i.d. sampling is near-optimal information and that the polylogarithmic gap is likely unavoidable for universal recovery.

C. Necessity of Nonlinear Algorithms

A critical contribution is demonstrating that linear algorithms cannot achieve universal optimality.

Curse of Dimensionality for Linear Methods: The authors show that any universal linear algorithm achieving optimal rates for a range of anisotropic parameters suffers from a dimension-dependent penalty. Specifically, the sample complexity $n$ required for a linear algorithm to match the performance of their nonlinear algorithm is:
$n \gtrsim \frac{m}{(\log m)^{d-1}}$
Conclusion: For dimensions $d > 4$ , linear algorithms are strictly suboptimal compared to the proposed nonlinear (SR-LASSO based) algorithms. This justifies the necessity of nonlinearity for universal recovery in high dimensions.

4. Key Results Summary

Feature	Anisotropic Mixed Smoothness ( $H^\alpha_{\text{mix}}$ )	Anisotropic Sobolev ( $H^\beta$ )
Smoothness Parameter	$\alpha = (\alpha_1, \dots, \alpha_d)$	$\beta = (\beta_1, \dots, \beta_d)$
Key Exponent	$h(\alpha) = \min_i \alpha_i$	$g(\beta) = (\sum \beta_j^{-1})^{-1}$
Log Factor	Depends on $p(\alpha)$ (count of min $\alpha_i$ )	None (pure power law)
Universal Rate	$\tilde{m}^{-h(\alpha)} \log^{p(\alpha)-1}(\tilde{m})$	$\tilde{m}^{-g(\beta)}$
Linear vs. Nonlinear	Linear algorithms incur $(\log m)^{d-1}$ penalty	Linear algorithms incur $(\log m)^{d-1}$ penalty

5. Significance and Impact

Solving the "Unknown Anisotropy" Problem: Most existing high-dimensional approximation methods assume the smoothness structure is known. This paper provides the first rigorous construction of universal algorithms that work without this prior knowledge, making them applicable to real-world black-box problems.
Validation of i.i.d. Sampling: The results confirm that simple random sampling (i.i.d. from uniform measure) is sufficient to achieve near-optimal recovery rates, removing the need for complex, adaptive sampling designs.
Nonlinearity is Essential: The paper provides a theoretical proof that for universal recovery of anisotropic functions, nonlinear methods are not just beneficial but necessary to avoid a curse of dimensionality in the convergence rate.
Compressed Sensing in Approximation Theory: The work bridges the gap between compressed sensing (typically used for sparse vectors) and high-dimensional function approximation, demonstrating that $\ell_1$ -minimization (via SR-LASSO) is a powerful tool for recovering functions with complex, unknown anisotropic structures.

In summary, Adcock and Gupta establish that one can recover high-dimensional anisotropic functions from random samples using a fixed, non-adaptive, nonlinear algorithm that achieves rates nearly as good as if the anisotropy were known, and they prove that no linear algorithm can match this performance universally.