pith. sign in

arxiv: 2606.26459 · v1 · pith:A6XTCGAWnew · submitted 2026-06-24 · 🧮 math.NA · cs.IT· cs.NA· math.IT

The devil in the (de)tails: an improved recovery guarantee for sparse approximation

Ben Adcock , Simone Brugiapaglia , Avi Gupta This is my paper

Pith reviewed 2026-06-26 01:00 UTC · model grok-4.3

classification 🧮 math.NA cs.ITcs.NAmath.IT
keywords sparse approximationcompressed sensingtruncation errori.i.d. samplingWiener spacesSobolev spacesRiesz systemsfunction approximation
0
0 comments X

The pith

Exploiting i.i.d. pointwise samples lets the discrete L2 truncation error track continuous L2 decay instead of the L infinity bound, allowing much smaller truncation sets in sparse approximation.

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

In sparse approximation of functions from i.i.d. pointwise samples via compressed sensing, truncating the dictionary to a finite set introduces a discrete L2 truncation error. Standard methods bound this error using the continuous L infinity norm, a worst-case deterministic bound that ignores sample randomness and requires unnecessarily large truncation sets. The paper derives a probabilistic bound that instead follows the faster decay of the continuous L2 norm by exploiting the i.i.d. structure of the samples. This yields significantly smaller truncation sets, smaller sensing matrices, and lower computational cost. The approach is demonstrated on weighted Wiener spaces and anisotropic Sobolev spaces, with an additional improved bound for bounded Riesz systems that reduces dependence on the Riesz constants.

Core claim

The central claim is that the discrete L2 truncation error over i.i.d. sample points admits a bound reflecting the continuous L2-norm truncation error decay, rather than being bounded by the L infinity norm. This is achieved by exploiting the i.i.d. structure, yielding smaller truncation index sets n, decreased computational cost, and applications to specific spaces with better results than recent works. Additionally, an improved bound for sparse approximation in bounded Riesz systems is presented where the measurement condition has a smaller, scale-invariant dependence on the Riesz constants.

What carries the argument

The probabilistic bound on the discrete L2 truncation error that exploits the i.i.d. structure of samples to track the continuous L2-norm decay.

If this is right

  • Significantly smaller truncation sets n suffice to keep the truncation error under control.
  • The size of the matrix in the sparse recovery algorithm decreases, directly lowering computational cost.
  • Recovery guarantees improve for functions in weighted Wiener spaces and anisotropic Sobolev spaces compared with prior deterministic bounds.
  • The measurement condition for sparse approximation in bounded Riesz systems depends less on the Riesz constants and remains scale-invariant.

Where Pith is reading between the lines

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

  • The same i.i.d.-exploiting argument could apply to other random sampling measures that admit similar concentration inequalities.
  • Adaptive choice of the truncation index set based on realized samples becomes feasible under the new bound.
  • The reduced matrix size may combine with existing acceleration techniques for compressed sensing solvers in high dimensions.
  • Numerical verification on concrete test functions could directly measure the predicted reduction in n while holding recovery error fixed.

Load-bearing premise

The pointwise samples are i.i.d., which permits replacing the deterministic worst-case L infinity bound on truncation error with a probabilistic bound that tracks the continuous L2-norm decay.

What would settle it

A numerical experiment in which the observed discrete L2 truncation error for i.i.d. samples stays as large as the continuous L infinity norm in a weighted Wiener space would falsify the improved bound.

Figures

Figures reproduced from arXiv: 2606.26459 by Avi Gupta, Ben Adcock, Simone Brugiapaglia.

Figure 1
Figure 1. Figure 1: The partition constructed in Lemma 3.1. ∥cTk ∥2 for all possible index sets Tk of the given size. We do this via the deviation inequality, Theorem 2.8, yielding ∥e∥2 ≤ X∞ k=1 θk [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
read the original abstract

Many functions exhibit approximate sparsity in their coefficients with respect to a given dictionary. In recent literature, sparse approximation in such a dictionary from i.i.d. pointwise samples, underpinned by compressed sensing, has become a powerful tool for high-dimensional function approximation. A key step in this framework is truncating the (typically countably-infinite) dictionary to a finite index set of size $n$, so that compressed sensing tools can be used to approximate the function by a sparse combination of these truncated dictionary elements. This introduces a discrete $L^2$-truncation error over the sample points, which in standard approaches, is bounded by the continuous $L^\infty$-norm. Such a deterministic, worst-case bound ignores the randomness of the sample points entirely. As a result, $n$ must be taken unnecessarily large to keep the truncation error under control, which directly inflates the size of the matrix involved in the sparse recovery algorithm and increases computational cost. In this paper, we show that by exploiting the i.i.d. structure of the sample points, the discrete $L^2$ truncation error admits a bound that instead reflects the faster decay behaviour of the continuous $L^2$-norm truncation error and yields significantly smaller truncation sets and decreased computational cost. We demonstrate this through applications to weighted Wiener spaces and anisotropic Sobolev spaces, in each case obtaining significantly smaller truncation sets than recent works. In addition, we also present an improved bound of independent interest for sparse approximation in bounded Riesz systems, where the measurement condition exhibits a smaller (and scale-invariant) dependence on the Riesz constants than in previous works.

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

0 major / 3 minor

Summary. The manuscript claims that, for sparse approximation of functions from i.i.d. pointwise samples via compressed sensing, the discrete L² truncation error can be bounded probabilistically so that it tracks the faster decay rate of the continuous L² truncation error rather than the deterministic L^∞ bound. This yields substantially smaller truncation sets, reduced matrix sizes, and lower computational cost. The improvement is demonstrated on weighted Wiener spaces and anisotropic Sobolev spaces (producing smaller sets than recent literature) and is accompanied by an improved measurement condition for bounded Riesz systems whose dependence on the Riesz constants is smaller and scale-invariant.

Significance. If the derivations hold, the work offers a practical reduction in the computational burden of high-dimensional sparse approximation by systematically exploiting the randomness already present in the sampling model. The applications to concrete function spaces and the independent-interest Riesz-system bound are concrete strengths; the latter removes an unnecessary scaling factor that appears in earlier analyses.

minor comments (3)
  1. [§2] §2 (or wherever the main concentration argument appears): the statement that the discrete L² error 'admits a bound that reflects the continuous L² decay' should be accompanied by an explicit statement of the probability and the constants that appear in the final truncation-set size; without these the comparison to prior deterministic bounds remains qualitative.
  2. [§4, §5] The applications in §4 and §5 compare truncation-set cardinalities with 'recent works,' but the precise parameter regimes (e.g., smoothness indices, weight sequences) used for those comparisons should be tabulated for reproducibility.
  3. Notation: the symbol n is used both for the truncation cardinality and, later, for the number of samples; a brief clarification or change of symbol would avoid confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the practical benefits, and recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives an improved truncation bound by replacing a deterministic L∞ worst-case estimate on the discrete L2 truncation error with a probabilistic concentration result that tracks the faster decay of the continuous L2 truncation error, exploiting the i.i.d. sampling assumption. This step invokes standard concentration inequalities and compressed-sensing recovery guarantees rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation. The applications to weighted Wiener and anisotropic Sobolev spaces are presented as concrete instances of the same general argument, with no equations shown to reduce to prior author-specific ansatzes or uniqueness theorems by construction. The overall argument therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review is abstract-only; no free parameters, invented entities, or ad-hoc axioms are visible. The work relies on standard domain assumptions from compressed sensing (Riesz systems, i.i.d. sampling) that are not introduced by the paper itself.

axioms (2)
  • domain assumption The dictionary forms a bounded Riesz system
    Invoked for the improved bound of independent interest mentioned in the abstract.
  • domain assumption Samples are drawn i.i.d. from the underlying measure
    Central premise that enables the probabilistic L2-style bound instead of deterministic L∞ bound.

pith-pipeline@v0.9.1-grok · 5837 in / 1355 out tokens · 51850 ms · 2026-06-26T01:00:52.492830+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

47 extracted references · 1 linked inside Pith

  1. [1]

    Adcock.Modified Fourier expansions: theory, construction and applications

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

    2010

  2. [2]

    Adcock, A

    B. Adcock, A. Bao, and S. Brugiapaglia. Correcting for unknown errors in sparse high-dimensional function approximation.Numer. Math., 142(3):667–711, 2019

    2019

  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

    2024

  4. [4]

    Adcock, S

    B. Adcock, S. Brugiapaglia, N. Dexter, and S. Moraga. Near-optimal learning of Banach-valued, high-dimensional functions via deep neural networks.Neural Networks, 181:106761, 2025

    2025

  5. [5]

    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

    2022

  6. [6]

    Adcock, M

    B. Adcock, M. J. Colbrook, and M. Neyra-Nesterenko. Restarts subject to approximate sharpness: a parameter-free and optimal scheme for first-order methods.Found. Comput. Math., pages 1–56, 2025

    2025

  7. [7]

    Adcock, N

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

    2024

  8. [8]

    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. 33

    2024

  9. [9]

    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

    2025

  10. [10]

    Adcock and A

    B. Adcock and A. Gupta. Universal, sample-optimal algorithms for recovery of anisotropic functions from i.i.d. samples.arXiv:2604.07660, 2026

    Pith/arXiv arXiv 2026

  11. [11]

    Adcock and A

    B. Adcock and A. C. Hansen.Compressive Imaging: Structure, Sampling, Learning. Cambridge University Press, Cambridge, UK, 2021

    2021

  12. [12]

    Bartel and P

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

    arXiv 2025

  13. [13]

    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

    2011

  14. [14]

    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

    2007

  15. [15]

    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

    2005

  16. [16]

    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

    2021

  17. [17]

    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

    2017

  18. [18]

    Chambolle and T

    A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applica- tions to imaging.J. Math. Imaging Vision, 40(1):120–145, 2011

    2011

  19. [19]

    Chambolle and T

    A. Chambolle and T. Pock. On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program., 159(1-2):253–287, 2016

    2016

  20. [20]

    B. Choi, M. A. Iwen, and F. Krahmer. Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables.Found. Comput. Math., 21(2):275–329, 2021

    2021

  21. [21]

    B. Choi, M. A. Iwen, and T. Volkmer. Sparse harmonic transforms II: bests-term approximation guarantees for bounded orthonormal product bases in sublinear-time.Numer. Math., 148(2):293– 362, 2021

    2021

  22. [22]

    D˜ ung, V

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

    2018

  23. [23]

    Dai and V

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

    2024

  24. [24]

    Dolbeault, D

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

    2023

  25. [25]

    Foucart and H

    S. Foucart and H. Rauhut.A Mathematical Introduction to Compressive Sensing. Appl. Numer. Harmon. Anal. Birkh¨ auser, New York, NY, 2013

    2013

  26. [26]

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

    2023

  27. [27]

    H. C. Jung.Estimation of low-complexity signals using structured and quantized observations. PhD thesis, RWTH Aachen University, 2022

    2022

  28. [28]

    K¨ ammerer, T

    L. K¨ ammerer, T. Ullrich, and T. Volkmer. Worst-case recovery guarantees for least squares ap- proximation using random samples.Constr. Approx., 54(2):295–352, 2021. 34

    2021

  29. [29]

    Kolomoitsev, T

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

    2023

  30. [30]

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

    2025

  31. [31]

    Krieg, K

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

    2025

  32. [32]

    Krieg and M

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

    2021

  33. [33]

    Krieg and M

    D. Krieg and M. Ullrich. Function values are enough forL 2-approximation: Part ii.J. Complexity, 66:101569, 2021

    2021

  34. [34]

    Migliorati.Polynomial approximation by means of the random discreteL 2 projection and ap- plication to inverse problems for PDEs with stochastic data

    G. Migliorati.Polynomial approximation by means of the random discreteL 2 projection and ap- plication to inverse problems for PDEs with stochastic data. PhD thesis, Politecnico di Milano, 2013

    2013

  35. [35]

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

    2023

  36. [36]

    Moeller, S

    M. Moeller, S. Neumayer, K. Pozharska, T. Sommerfeld, and T. Ullrich. High-dimensional sparse recovery from function samples: Decoders, guarantees and instance optimality.arXiv:2503.16209, 2025

    arXiv 2025

  37. [37]

    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

    2024

  38. [38]

    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

    arXiv 2024

  39. [39]

    Moeller, S

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

    2026

  40. [40]

    Nagel, M

    N. Nagel, M. Sch¨ afer, and T. Ullrich. A new upper bound for sampling numbers.Found. Comput. Math., 22(2):445–468, 2022

    2022

  41. [41]

    Needell and R

    D. Needell and R. Vershynin. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit.IEEE J. Sel. Topics Signal Process., 4(2):310–316, 2010

    2010

  42. [42]

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

    2022

  43. [43]

    Novak and H

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

    2008

  44. [44]

    Rauhut and R

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

    2012

  45. [45]

    Rauhut and R

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

    2016

  46. [46]

    Temlyakov.Multivariate Approximation

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

    2018

  47. [47]

    J. A. Tropp. User-friendly tail bounds for sums of random matrices.Found. Comput. Math., 12:389–434, 2012. 35

    2012