pith. sign in

arxiv: 2604.07660 · v1 · submitted 2026-04-08 · 🧮 math.NA · cs.IT· cs.NA· math.IT

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

Ben Adcock , Avi Gupta (Simon Fraser University , Canada) This is my paper

Pith reviewed 2026-05-10 16:50 UTC · model grok-4.3

classification 🧮 math.NA cs.ITcs.NAmath.IT
keywords anisotropic Sobolev spacesdominating mixed smoothnesscompressed sensingFourier recoveryuniversal approximationhigh-dimensional functionssample optimalitynonlinear algorithms
0
0 comments X

The pith

A compressed sensing algorithm recovers periodic anisotropic functions optimally from i.i.d. samples up to polylog factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a nonadaptive universal algorithm for approximating high-dimensional periodic functions with unknown anisotropic smoothness by recasting the recovery as a sparse Fourier coefficient problem solved via compressed sensing. This approach achieves near-optimal convergence rates uniformly across different anisotropic Sobolev and dominating mixed smoothness classes without adapting to the specific smoothness. A lower bound on the adaptive m-width confirms the optimality up to a dimension-independent polylogarithmic factor, while linear algorithms are shown to suffer from a worse, dimension-dependent suboptimality. This matters because it provides a practical way to recover functions when the anisotropy is unknown in advance, avoiding the need for separate methods per class.

Core claim

We present a universal algorithm that uses compressed sensing to recover the Fourier coefficients of periodic functions belonging to anisotropic Sobolev spaces or anisotropic spaces of dominating mixed smoothness from i.i.d. samples. The algorithm is nonadaptive and achieves approximation rates optimal up to a dimension-independent polylogarithmic factor, as established by a lower bound for the adaptive m-width of the unit balls of these classes. We further show that any universal linear algorithm is at best suboptimal by a dimension-dependent polylogarithmic factor, establishing the necessity of nonlinear methods for achieving universal sample-optimal recovery.

What carries the argument

The nonadaptive compressed sensing recovery of Fourier coefficients that serves as a universal approximator across anisotropic smoothness classes.

If this is right

  • The same algorithm applies to both anisotropic Sobolev spaces and dominating mixed smoothness spaces without modification.
  • Rates are near-optimal independently of the specific anisotropy parameters.
  • Linear methods incur an extra dimension-dependent penalty in the convergence rate for universal recovery.
  • Nonlinear sparse recovery is essential to avoid additional losses in high-dimensional settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar compressed sensing techniques might extend to non-periodic domains by substituting other orthogonal bases for the Fourier expansion.
  • The results indicate that nonlinearity helps overcome extra rate penalties when the smoothness structure is hidden in high dimensions.
  • Practical tests on data sets with varying unknown anisotropy could check whether the polylog overhead remains small in applications.

Load-bearing premise

The target functions are periodic so that they admit a Fourier series, and they lie in one of the specified anisotropic smoothness classes with i.i.d. samples available.

What would settle it

A concrete function in an anisotropic Sobolev space where the compressed sensing recovery produces approximation error larger than the claimed near-optimal rate by more than the polylog factor.

read the original abstract

A key problem in approximation theory is the recovery of high-dimensional functions from samples. In many cases, the functions of interest exhibit anisotropic smoothness, and, in many practical settings, the nature of this anisotropy may be unknown a priori. Therefore, an important question involves the development of universal algorithms, namely, algorithms that simultaneously achieve optimal or near-optimal rates of convergence across a range of different anisotropic smoothness classes. In this work, we consider universal approximation of periodic functions that belong to anisotropic Sobolev spaces and anisotropic dominating mixed smoothness Sobolev spaces. Our first result is the construction of a universal algorithm. This recasts function recovery as a sparse recovery problem for Fourier coefficients and then exploits compressed sensing to yield the desired approximation rates. Note that this algorithm is nonadaptive, as it does not seek to learn the anisotropic smoothness of the target function. We then demonstrate optimality of this algorithm up to a dimension-independent polylogarithmic factor. We do this by presenting a lower bound for the adaptive $m$-width for the unit balls of such function classes. Finally, we demonstrate the necessity of nonlinear algorithms. We show that universal linear algorithms can achieve rates that are at best suboptimal by a dimension-dependent polylogarithmic factor. In other words, they suffer from a curse of dimensionality in the rate -- a phenomenon which justifies the necessity of nonlinear algorithms for universal recovery.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript constructs a nonadaptive universal algorithm for recovering periodic functions belonging to anisotropic Sobolev spaces and anisotropic dominating mixed smoothness Sobolev spaces from i.i.d. samples. The approach recasts recovery as a sparse Fourier-coefficient recovery problem and applies compressed-sensing techniques to achieve the desired approximation rates without adapting to the unknown anisotropy. Optimality (up to a dimension-independent polylogarithmic factor) is established via a lower bound on the adaptive m-widths of the corresponding unit balls. The paper additionally shows that any universal linear algorithm is at best suboptimal by a dimension-dependent polylogarithmic factor, thereby justifying the use of nonlinear methods.

Significance. If the proofs hold, the work supplies a concrete, nonadaptive construction that is nearly sample-optimal across an entire family of anisotropic classes and supplies an independent lower bound that certifies the rate. The explicit separation between linear and nonlinear universal methods, together with the dimension-independent polylog gap, is a notable strength and directly addresses a central question in high-dimensional approximation theory.

major comments (2)
  1. [Lower-bound argument (after the algorithm construction)] The lower bound on adaptive m-widths is load-bearing for the near-optimality claim; the manuscript should make explicit how the polylogarithmic factor arises and confirm that its dependence on dimension is only polylogarithmic (rather than polynomial) in the relevant theorem statement and proof.
  2. [Section on linear versus nonlinear universal algorithms] The argument that linear methods incur a dimension-dependent polylogarithmic penalty is central to the necessity-of-nonlinearity conclusion; the derivation of this penalty should be stated with explicit constants or exponents so that the dimension dependence is unambiguous.
minor comments (2)
  1. The abstract states the rates are optimal 'up to a dimension-independent polylogarithmic factor' but does not record the precise sample complexity m in terms of the smoothness indices and dimension; adding this relation would improve readability.
  2. Notation for the anisotropy parameters (e.g., the vector of smoothness indices) should be introduced once and used consistently when stating both the upper and lower bounds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive evaluation, and the constructive suggestions that will improve the clarity of the manuscript. We address the two major comments point by point below and will incorporate the requested clarifications in the revised version.

read point-by-point responses

  1. Referee: The lower bound on adaptive m-widths is load-bearing for the near-optimality claim; the manuscript should make explicit how the polylogarithmic factor arises and confirm that its dependence on dimension is only polylogarithmic (rather than polynomial) in the relevant theorem statement and proof.

    Authors: We agree that the origin and dimension dependence of the polylogarithmic factor in the lower bound on adaptive m-widths should be stated more explicitly. In the proof of the lower bound (currently Theorem 3.3), the factor arises from standard volume-ratio estimates on the entropy numbers of the anisotropic Sobolev unit ball; the exponent is independent of dimension d and depends only on the smoothness parameters. We will revise the theorem statement to read explicitly that the lower bound holds up to a factor of (log m)^C with C independent of d, and we will add a short paragraph immediately after the theorem tracing the appearance of this factor in the entropy-number argument. This change will be made in the next revision. revision: yes

  2. Referee: The argument that linear methods incur a dimension-dependent polylogarithmic penalty is central to the necessity-of-nonlinearity conclusion; the derivation of this penalty should be stated with explicit constants or exponents so that the dimension dependence is unambiguous.

    Authors: We agree that the dimension dependence in the linear-method lower bound should be made fully explicit. The current proof of Theorem 4.2 derives the penalty via a combinatorial argument (a variant of the Sauer-Shelah lemma applied to the sign patterns of linear functionals) that produces a factor of the form (log d)^c for an explicit positive constant c depending only on the smoothness parameters. We will update the theorem statement to include the explicit exponent (or the precise functional form of the polylog) and will insert one additional sentence in the proof that isolates the combinatorial step responsible for the d-dependence. These modifications will appear in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation proceeds by explicitly constructing a nonadaptive algorithm that recasts periodic function recovery as sparse recovery of Fourier coefficients and applies standard compressed sensing techniques to achieve the stated rates across anisotropic Sobolev and dominating mixed smoothness classes. Optimality is established via a separate lower bound on adaptive m-widths, and the suboptimality of linear methods is shown by a distinct argument on dimension-dependent polylog factors. None of these steps reduce by construction to fitted inputs, self-definitions, or self-citation chains; all rely on external results from approximation theory and compressed sensing under the explicit assumptions of periodicity and i.i.d. samples. The paper is therefore self-contained with independent content in its central claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard properties of periodic Sobolev spaces, Fourier series, and compressed sensing recovery guarantees; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math Periodic functions admit Fourier expansions and anisotropic Sobolev norms control coefficient decay
    Invoked throughout the abstract as the setting for the recovery problem.
  • standard math Compressed sensing yields stable recovery of sparse vectors from random measurements
    Used to obtain the approximation rates for the universal algorithm.

pith-pipeline@v0.9.0 · 5554 in / 1279 out tokens · 39949 ms · 2026-05-10T16:50:28.196405+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages

  1. [1]

    Adcock.Modified Fourier expansions: theory, construction and applications

    B. Adcock.Modified Fourier expansions: theory, construction and applications. PhD thesis, University of Cambridge, 2010

    work page 2010

  2. [2]

    Adcock, S

    B. Adcock and S. Brugiapaglia. Monte Carlo is a good sampling strategy for polynomial approximation in high dimensions.arXiv:2208.09045, 2023. 35

    work page arXiv 2023

  3. [3]

    Adcock, S

    B. Adcock, S. Brugiapaglia, N. Dexter, and S. Moraga.On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples, volume 13 ofMem. Eur. Math. Soc.EMS Press, 2024

    work page 2024

  4. [4]

    Adcock, S

    B. Adcock, S. Brugiapaglia, and C. G. Webster.Sparse Polynomial Approximation of High-Dimensional Functions. Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2022

    work page 2022

  5. [5]

    Adcock, N

    B. Adcock, N. Dexter, and S. Moraga. Optimal approximation of infinite-dimensional holomorphic functions.Calcolo, 61(1):12, 2024

    work page 2024

  6. [6]

    Adcock, N

    B. Adcock, N. Dexter, and S. Moraga. Optimal deep learning of holomorphic operators between Banach spaces. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 27725–27789. Curran Associates, Inc., 2024

    work page 2024

  7. [7]

    Adcock, N

    B. Adcock, N. Dexter, and S. Moraga. Optimal approximation of infinite-dimensional holomorphic functions II: recovery from iid pointwise samples.J. Complexity, 89:101933, 2025

    work page 2025

  8. [8]

    URL:https://arxiv.org/abs/2410.23440,arXiv:2410.23440

    B. Adcock, M. Griebel, and G. Maier. The sample complexity of learning Lipschitz operators with respect to Gaussian measures.arXiv:2410.23440, 2025

    work page arXiv 2025

  9. [9]

    Bartel and P

    F. Bartel and P. Schr¨ oter. Learning and leveraging anisotropy parameters in ANOVA approximation. arXiv:2511.00251, 2025

    work page arXiv 2025

  10. [10]

    Belloni, V

    A. Belloni, V. Chernozhukov, and L. Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming.Biometrika, 98(4):791–806, 2011

    work page 2011

  11. [11]

    Binev, A

    P. Binev, A. Cohen, W. Dahmen, and R. DeVore. Universal algorithms for learning theory. Part II: Piecewise polynomial functions.Constr. Approx., 26(2):127–152, 2007

    work page 2007

  12. [12]

    Binev, A

    P. Binev, A. Cohen, W. Dahmen, R. DeVore, V. Temlyakov, and P. Bartlett. Universal algorithms for learning theory. Part I: Piecewise constant functions.J. Mach. Learn. Res., 6(9), 2005

    work page 2005

  13. [13]

    Brugiapaglia, S

    S. Brugiapaglia, S. Dirksen, H. C. Jung, and H. Rauhut. Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs.Appl. Comput. Harmon. Anal., 53:231–269, 2021

    work page 2021

  14. [14]

    Byrenheid and T

    G. Byrenheid and T. Ullrich. Optimal sampling recovery of mixed order Sobolev embeddings via discrete Littlewood–Paley type characterizations.Anal. Math., 43(2):133–191, 2017

    work page 2017

  15. [15]

    Chen and H

    J. Chen and H. Wang. Preasymptotics and asymptotics of approximation numbers of anisotropic Sobolev embeddings.J. Complexity, 39:94–110, 2017

    work page 2017

  16. [16]

    Cobos, T

    F. Cobos, T. K¨ uhn, and W. Sickel. Optimal approximation of multivariate periodic Sobolev functions in the sup-norm.J. Funct. Anal., 270(11):4196–4212, 2016

    work page 2016

  17. [17]

    D˜ ung, V

    D. D˜ ung, V. Temlyakov, and T. Ullrich.Hyperbolic Cross Approximation. Adv. Courses Math. CRM Barcelona. Birkh¨ auser, Basel, Switzerland, 2018

    work page 2018

  18. [18]

    Dai and V

    F. Dai and V. Temlyakov. Universal sampling discretization.Constr. Approx., 58:589–613, 2023

    work page 2023

  19. [19]

    Dai and V

    F. Dai and V. Temlyakov. Random points are good for universal discretization.J. Math. Anal. Appl., 529(1):127570, 2024

    work page 2024

  20. [20]

    Dai and V

    F. Dai and V. N. Temlyakov. Universal discretization and sparse recovery.J. Approx. Theory, 311:106199, 2025

    work page 2025

  21. [21]

    Dai and V

    F. Dai and V. N. Temlyakov. A survey on sampling recovery.arXiv:2601.08787, 2026

    work page arXiv 2026

  22. [22]

    DeVore, R

    R. DeVore, R. D. Nowak, R. Parhi, G. Petrova, and J. W. Siegel. Optimal recovery meets minimax estimation.arXiv:2502.17671, 2025

    work page arXiv 2025

  23. [23]

    Dolbeault, D

    M. Dolbeault, D. Krieg, and M. Ullrich. A sharp upper bound for sampling numbers in L2.Appl. Comput. Harmon. Anal., 63:113–134, 2023. 36

    work page 2023

  24. [24]

    Griebel and J

    M. Griebel and J. Hamaekers. Fast discrete Fourier transform on generalized sparse grids. In J. Garcke and D. Pfl¨ uger, editors,Sparse Grids and Applications – Munich 2012, pages 75–107. Springer, Cham, 2014

    work page 2012

  25. [25]

    H¨ ollig

    K. H¨ ollig. Diameters of classes of smooth functions. InQuantitative Approximation, pages 163–175. Academic Press, New York, 1980

    work page 1980

  26. [26]

    T. Jahn, T. Ullrich, and F. Voigtlaender. Sampling numbers of smoothness classes via ℓ1-minimization. J. Complexity, 79:101786, 2023

    work page 2023

  27. [27]

    Kolomoitsev, T

    Y. Kolomoitsev, T. Lomako, and S. Tikhonov. Sparse grid approximation in weighted Wiener spaces.J. Fourier Anal. Appl., 29(2):19, 2023

    work page 2023

  28. [28]

    E. D. Kosov and V. N. Temlyakov. Sampling recovery of functions with mixed smoothness.Adv. Oper. Theory, 10(2):49, 2025

    work page 2025

  29. [29]

    D. Krieg. Tractability of sampling recovery on unweighted function classes.Proc. Amer. Math. Soc. Ser. B, 11(12):115–125, 2024

    work page 2024

  30. [30]

    Krieg, E

    D. Krieg, E. Novak, and M. Sonnleitner. Recovery of Sobolev functions restricted to iid sampling.Math. Comp., 91(338):2715–2738, 2022

    work page 2022

  31. [31]

    Krieg, K

    D. Krieg, K. Pozharska, M. Ullrich, and T. Ullrich. Sampling recovery in L2 and other norms.Math. Comp., 2025

    work page 2025

  32. [32]

    Krieg and M

    D. Krieg and M. Sonnleitner. Random points are optimal for the approximation of Sobolev functions. IMA J. Numer. Anal., 44(3):1346–1371, 2024

    work page 2024

  33. [33]

    Krieg and M

    D. Krieg and M. Sonnleitner. Function recovery on manifolds using scattered data.J. Approx. Theory, 305:106098, 2025

    work page 2025

  34. [34]

    Krieg and M

    D. Krieg and M. Ullrich. Function values are enough for L2-approximation.Found. Comput. Math., 21(4):1141–1151, 2021

    work page 2021

  35. [35]

    K¨ uhn, W

    T. K¨ uhn, W. Sickel, and T. Ullrich. Approximation of mixed order Sobolev functions on the d-torus: asymptotics, preasymptotics, andd-dependence.Constr. Approx., 42:353–398, 2015

    work page 2015

  36. [36]

    K¨ uhn, W

    T. K¨ uhn, W. Sickel, and T. Ullrich. How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings.J. Complexity, 63:101523, 2021

    work page 2021

  37. [37]

    Migliorati.Polynomial approximation by means of the random discrete L2 projection and application to inverse problems for PDEs with stochastic data

    G. Migliorati.Polynomial approximation by means of the random discrete L2 projection and application to inverse problems for PDEs with stochastic data. PhD thesis, Politecnico di Milano, 2013

    work page 2013

  38. [38]

    B. S. Mitjagin. Approximation of functions of Lp and C spaces on the torus.Mat. Sb., 58(100):397–414, 1962

    work page 1962

  39. [39]

    M. Moeller. Gelfand numbers and best m-term trigonometric approximation for weighted mixed Wiener classes inL 2. Master’s thesis, TU Chemnitz, Germany, 2023

    work page 2023

  40. [40]

    Moeller, K

    M. Moeller, K. Pozharska, and T. Ullrich. Instance optimal function recovery – samples, decoders and asymptotic performance.arXiv:2503.16209, 2025

    work page arXiv 2025

  41. [41]

    Moeller, K

    M. Moeller, K. Pozharska, and T. Ullrich. Sampling designs for function recovery – theoretical guarantees, comparison and optimality.MCQMC 2024 Proceedings, 2025. to appear

    work page 2024

  42. [42]

    Moeller, S

    M. Moeller, S. Stasyuk, and T. Ullrich. High-dimensional sparse trigonometric approximation in the uniform norm and consequences for sampling recovery.arXiv:2407.15965, 2024

    work page arXiv 2024

  43. [43]

    Moeller, S

    M. Moeller, S. Stasyuk, and T. Ullrich. Best m-term trigonometric approximation in weighted Wiener spaces and applications.Adv. Oper. Theory, 11(2):18, 2026

    work page 2026

  44. [44]

    V. D. Nguyen, V. K. Nguyen, and W. Sickel. s-numbers of embeddings of weighted Wiener algebras.J. Approx. Theory, 279:105745, 2022. 37

    work page 2022

  45. [45]

    Novak and H

    E. Novak and H. Wo´ zniakowski.Tractability of Multivariate Problems, Volume I: Linear Information. Number 6 in EMS Tracts in Mathematics. European Mathematical Society Publishing House, Z¨ urich, Switzerland, 2008

    work page 2008

  46. [46]

    Rauhut and R

    H. Rauhut and R. Ward. Sparse Legendre expansions via ℓ1-minimization.J. Approx. Theory, 164(5):517– 533, 2012

    work page 2012

  47. [47]

    Rauhut and R

    H. Rauhut and R. Ward. Interpolation via weighted ℓ1 minimization.Appl. Comput. Harmon. Anal., 40(2):321–351, 2016

    work page 2016

  48. [48]

    Sonnleitner and M

    M. Sonnleitner and M. Ullrich. On the power of iid information for linear approximation. arXiv:2310.12740, 2023

    work page arXiv 2023

  49. [49]

    M. I. Stesin. Aleksandrov diameters of finite-dimensional sets and classes of smooth functions.Dokl. Akad. Nauk SSSR, 220(6):1278–1281, 1975. In Russian

    work page 1975

  50. [50]

    S. A. Telyakovskii. Some bounds for trigonometric series with quasi-convex coefficients.Mat. Sb., 105(3):426–444, 1964

    work page 1964

  51. [51]

    Temlyakov.Multivariate Approximation

    V. Temlyakov.Multivariate Approximation. Cambridge University Press, 2018

    work page 2018

  52. [52]

    V. N. Temlyakov. Approximation by elements of a finite-dimensional subspace of functions from various Sobolev or Nikol’skii spaces.Math. Notes, 43(6):444–454, 1988

    work page 1988

  53. [53]

    X. Wang. Volumes of generalized unit balls.Math. Mag., 78(5):390–395, 2005. 38

    work page 2005