Pith. sign in

REVIEW 3 major objections 4 minor 53 references

Sparse grids vs. random points for high-dimensional polynomial approximation

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper's central claim: least-squares on random points, with twice as many samples as Smolyak's sparse grid, matches its accuracy in low dimensions and clearly beats it in high dimensions on the tested benchmark families.

desk verdict Useful benchmark showing LS often matches Smolyak, but the high-dimensional 'clear superiority' claim needs seeds and repeated draws before it can be trusted. read the letter →

arxiv 2506.24054 v1 pith:NTILMP6X submitted 2025-06-30 math.NA cs.NA

Jakob Eggl , Elias Mindlberger , Mario Ullrich This is my paper · ORCID
classification math.NAcs.NA MSC 41A1041A6365D0565D15
keywords polynomialapproximationsparsegridsSmolyak'salgorithmleastsquaresrandomsamplinghigh-dimensionalChebyshevpolynomialsbenchmarkfunctions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish that a conceptually simple least-squares estimator based on random points can replace interpolation on sparse grids (Smolyak's algorithm) for high-dimensional polynomial approximation, without losing accuracy. Both methods project onto the same polynomial space $E(q,d)$, but the least-squares methods use twice as many samples, drawn once from the uniform or Chebyshev distributions. On nine benchmark families in dimensions up to 100, at least one least-squares variant matches Smolyak in low dimensions, and in high dimensions it is often much better. The practical stakes are that random points are easy to generate in any dimension, while constructing sparse grids of prescribed cardinality is more involved, and Smolyak's method itself is not the winner in the tested high-dimensional regime.

What carries the argument

The load-bearing objects are the Smolyak space $E(q,d)$ from Proposition 3, the space of polynomials exactly reproduced by Smolyak's algorithm, and the two least-squares estimators (6) and (7) that project the same function onto that space from $2N(q,d)$ independent random points, uniformly distributed or sampled with the tensorized Chebyshev density. The comparison metric is the worst-case error over $Q = 50$ random instances of each benchmark family, estimated at $M$ fresh uniformly distributed test points as a maximum absolute deviation and a root-mean-square deviation. The random point sets are generated once for each $q$ and $d$ and then fixed for the whole simulation.

What would settle it

Re-run the same pipeline with many independent point-set draws for each $q$ and $d$, say 100 seeds, and compare the distribution of least-squares errors against Smolyak's error; if under a majority of draws least squares fails to match Smolyak in high dimensions, the paper's 'clear superiority' claim would not survive.

Watch

Extended reading notes

Core claim

The paper's central claim is that Smolyak's algorithm is not the method of choice for moderate-scale polynomial approximation in high dimensions. With $n = 2N(q,d)$ random sample points, the plain least-squares projection onto the same polynomial space $E(q,d)$ that Smolyak uses exactly reproduces matches or beats Smolyak's $N(q,d)$-point interpolant across all nine benchmark families, and in dimensions roughly 11 through 100 the advantage is often large, especially for the unweighted LS-uniform variant. The paper presents this as an experimental finding, extending the classical theory of sparse-grid interpolation from the earlier literature, and explicitly notes that the observed performance is not yet supported by matching theoretical error bounds.

Load-bearing premise

The one fixed random point set used for each $q$ and $d$ is typical, with no reported seed and no averaging over draws, so the observed least-squares advantage could in principle be an artifact of unrepresentative point sets.

Editorial extensions

If this is right

  • For a practitioner, the comparison says that using twice as many random points as sparse-grid points is enough to match sparse-grid accuracy, with no need for nested point sets or a prescribed grid structure.
  • In high dimensions (roughly $d \ge 11$ up to 100), the unweighted uniform least-squares variant is often the best of the three methods, so a simple iid uniform sampling rule can replace carefully chosen interpolation nodes.
  • Smolyak's method remains much cheaper per run; least squares needs a large dense linear solve, so the accuracy advantage comes with a serious runtime and memory price.
  • When the data is contaminated by noise, least squares is more stable than Smolyak interpolation, with LS-uniform gaining stability in high dimension and LS-Chebyshev in low dimension.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: The paper's results invite the open conjecture that $2N(q,d)$ iid random points, possibly with Chebyshev weights, are enough for least squares to match Smolyak's error on the class $F_d^s$; proving this would likely require a uniform-norm discretization that avoids the current $\sqrt{n}$ loss.
  • Extension: The same experimental template could test whether deterministic low-discrepancy point sets preserve the high-dimensional least-squares advantage, which would separate the effect of randomness from the effect of point-set geometry.
  • Extension: If the high-dimensional least-squares advantage generalizes beyond these benchmark families, it weakens the practical case for sparse-grid interpolation in very high dimensions where only small scales are affordable, shifting attention to solving the underlying least-squares systems efficiently.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper revisits the influential comparison of Barthelmann, Novak, and Ritter (2000) and contrasts Smolyak interpolation on Chebyshev sparse grids (SA) with two least-squares variants that use 2N(q,d) random points on the same polynomial space E(q,d): unweighted least squares with uniform random points (LS-uniform) and weighted least squares with points drawn from the Chebyshev density (LS-Chebyshev). The authors survey known theoretical bounds, discuss the gap between available probabilistic guarantees (which require n log n samples) and their 2N sampling regime, and report numerical experiments on nine benchmark families for dimensions up to 100. Their main empirical claims are that at least one LS variant consistently matches SA in low dimensions, that LS is clearly superior to SA in high dimensions at small scales, and that LS is more stable under noisy data. The manuscript includes code and results on GitHub.

Significance. If the high-dimensional claim is robust, the paper has real practical significance: it suggests that simple random least squares with modest oversampling can outperform sparse-grid interpolation on smooth benchmark functions in high dimensions, a regime where sparse grids are often assumed to be the method of choice. The paper is also a useful service in that it repeats and extends the theoretical analysis of the BNR paper and makes all code and data publicly available, which strengthens reproducibility. The experimental protocol is internally consistent: all three methods are evaluated on the same test points and the same random functions, and the theoretical gap between the 2N sampling regime and the n log n guarantees is stated honestly. The significance is conditional, however, because the headline high-dimensional conclusion rests on a single random realization of the LS point sets and on only two small scales, so the statistical robustness of the 'clear superiority' claim is not yet established.

major comments (3)
  1. [§4.1 and §3 (Theorem 7)] The central empirical claim that LS with only 2N(q,d) random points matches or beats Smolyak's N(q,d)-point interpolant rests on a single random realization of the LS point set for each (q,d). Section 4.1 states that 'these random points are generated only once and then fixed for the rest of the simulation', and no random seed is reported. Theorem 7, the only probabilistic guarantee quoted in the paper, applies to b n log(n) iid points; the 2N regime is exactly the regime where no such guarantee is available. A single atypical draw of the design matrix, for example one with a large condition number, could change the rankings in Figures 6-10. The paper should repeat each high-dimensional experiment over several independent point-set draws and report the spread (minimum/median/maximum or boxplots), and it should report seeds for full reproducibility.
  2. [§4.4] The high-dimensional conclusion is based on scales k=1 and k=2 only, and the paper presents selected figures rather than complete tables for d>10. Because the headline 'clear superiority' claim is specifically about high dimensions, the authors should either provide aggregate statistics over all nine function families and all d (for example, the number of families in which each method attains the smallest ewc_max and ewc_mean as a function of d) or state explicitly that the conclusion is limited to these two small scales. As written, the conclusion is drawn largely from visual inspection of a subset of the data.
  3. [§4.4 and §4.2] The authors themselves flag that the large high-dimensional errors 'may be caused by a wrong scaling (in d) of the test functions'. A constant scaling per function cannot change the relative ranking of the three methods, so this caveat does not invalidate the internal comparison. However, several families (Discontinuous, Ridge Product, and Oscillatory) produce errors that grow exponentially with d, and the resulting comparison may reflect the benchmark design more than the typical behavior of the algorithms. The paper should either normalize the test functions (for example, to unit sup-norm or unit L2-norm) or justify explicitly why the chosen parameter scaling is representative for the claimed high-dimensional superiority.
minor comments (4)
  1. [Figures 6-8] The captions for the scale-1 panels read 'points LS = 2 N(q + 1, d)', which appears to be a typo for '2 N(d + 1, d)'; the scale-2 panels have the analogous issue.
  2. [§4.1] The sentence 'with Q = 50 random functions g1, ..., gQ from each class by choosing corresponding parameters c, w ~ U[0,1]^d and rescale such that ||c||_1 = d' is grammatically incomplete and does not specify whether w is also rescaled; please clarify.
  3. [§4.5] The sentence 'In high dimensions, however, LS-uniform seems to be more stable than LS-Chebyshev. This is to be understood theoretically.' appears to be missing a verb; it should read 'This remains to be understood theoretically' or similar.
  4. [§3] There is a typo in 'we only discuss one part on the story here', which should be 'one part of the story here'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the central claim is an external benchmark comparison, not a consequence of the cited theory.

full rationale

The paper's headline claim—that least squares with 2N random points matches or outperforms Smolyak interpolation—is established by direct numerical experiments on nine externally defined benchmark function families (Genz integrand families and related test functions from [21, 22, 48]). The LS estimators are defined in (6) and (7) on the same polynomial space E(q,d) used by Smolyak, with no parameter fitted to the comparison outcome. Theoretical results such as Theorem 7 (citing Krieg-Ullrich, which includes an author of this paper) are explicitly not the basis for the 2N experiments; the paper states 'This is not yet supported by theory' regarding the experimental finding that simple LS methods work without logarithmic oversampling. Thus the load-bearing evidence for the superiority claim is measured against external benchmark functions, not derived by construction from the cited theorems. The fixed single random point-set design (Section 4.1) is a statistical robustness concern, not a circularity: it does not make the comparison equal to its inputs by definition. No self-definitional, fitted-input, or self-citation-load-bearing step was found, so the paper is self-contained against external benchmarks for its central empirical claim.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are postulated. All inputs to the comparison are standard benchmark families, existing polynomial spaces, and established theoretical bounds; the free parameters listed are experimental design choices that shape the empirical claim.

free parameters (5)
  • LS oversampling factor = 2 (LS uses 2*N(q,d) points)
    Defined in equations (6) and (7); the central observation that 2n random points suffice is specific to this factor, and no other factors are tested.
  • Test-function parameter rescaling = c, w ~ U[0,1]^d with ||c||_1 = d
    Section 4.1: parameters are drawn uniformly and c is rescaled to have l1 norm d; Section 4.4 notes a possible 'wrong' scaling in d may drive non-convergence, so the comparison depends on this normalization.
  • Number of random functions per class = Q = 50
    Section 4.1: worst-case errors are over Q=50 random parameter draws per class; the empirical curves are sensitive to this sample size.
  • Test point count M = M = N(q,d) for d <= 10; M = 100*N(d+2,d) for large d
    Section 4.1: reported e_max and e_mean are evaluated on M random test points; the authors explicitly do not claim this estimates the true error well.
  • Noise level in stability test = sigma = 1e-7
    Section 4.5: Gaussian noise with standard deviation 1e-7 is added to the zero function to test stability.
assumptions (4)
  • standard math Smolyak interpolation is exact on the sparse grid and satisfies the error bound of Theorem 4 from [3].
    Section 2 restates these as proven in the 2000 paper; they serve as the reference for SA error behavior.
  • domain assumption The least squares solution is unique and stable when the number of points exceeds the dimension of E(q,d), and the same polynomial space is a fair common approximation space.
    Section 3 and equations (6)-(7): LS uses 2*N(q,d) points with dim E(q,d)=N(q,d); the fairness of this doubling is assumed.
  • domain assumption The nine Genz and related benchmark families with random parameters represent typical hard high-dimensional approximation problems.
    Section 4.2: claims about LS superiority generalize from these families; they are standard benchmarks, but the representativeness is not established.
  • domain assumption The error metrics on a single set of M test points and one fixed realization of LS sampling points reliably rank the methods.
    Section 4.1: no repeated seeds or confidence intervals are reported, so the observed ranking presumes the realized point sets are typical.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sparse grids vs. random points for high-dimensional polynomial approximation." pith.science (2026). https://pith.science/paper/NTILMP6X

@misc{pith2026250624054,
  author       = {Pith},
  title        = {Pith review of: Sparse grids vs. random points for high-dimensional polynomial approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NTILMP6X}},
  note         = {Machine review of arXiv:2506.24054}
}
abstract

We study polynomial approximation on a $d$-cube, where $d$ is large, and compare interpolation on sparse grids, aka Smolyak's algorithm (SA), with a simple least squares method based on randomly generated points (LS) using standard benchmark functions. Our main motivation is the influential paper [Barthelmann, Novak, Ritter: High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12, 2000]. We repeat and extend their theoretical analysis and numerical experiments for SA and compare to LS in dimensions up to 100. Our extensive experiments demonstrate that LS, even with only slight oversampling, consistently matches the accuracy of SA in low dimensions. In high dimensions, however, LS shows clear superiority.

Figures

Figures reproduced from arXiv: 2506.24054 by the authors.

Figure 1
Figure 1. Visualization of the functions for d = 2. 4.3. Approximation in low dimensions. We now present some of our results for dimensions up to d = 10 with “large” scales up to 9. Hence, the maximal numbers of points used are given, e.g., by N(12, 3) = 13953, N(13, 5) = 51713 and N(16, 10) = 171425 for Smolyak, while both LS use twice as many. First, we present a table giving the precise values of e wc max and e wc mean for… view at source ↗
Figure 2
Figure 2. Some functions at fixed dimension d = 10 [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Some functions at fixed dimension d = 10 [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Some functions at fixed dimension d = 5 [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 5
Figure 5. Figure 5: Some functions at fixed dimension d = 3. 4.4. Approximation in high dimensions. We now turn to our re￾sult in high dimensions up to 100. We can only consider small scales due to the fast increasing number of points. (See [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]
Figure 6
Figure 6. Figure 6: Some functions for fixed scale 1 and 2 [PITH_FULL_IMAGE:figures/full_fig_p022_6.png]
Figure 7
Figure 7. Figure 7: Some functions for fixed scale 1 and 2 [PITH_FULL_IMAGE:figures/full_fig_p023_7.png]
Figure 8
Figure 8. Figure 8: Some functions for fixed scale 1 and 2 [PITH_FULL_IMAGE:figures/full_fig_p024_8.png]
Figure 9
Figure 9. Figure 9: Noise for d = 5 and d = 10 [PITH_FULL_IMAGE:figures/full_fig_p025_9.png]
Figure 10
Figure 10. Figure 10: Noise for scales 1 and 2 in high dimensions. 5. Discussion Let us finally discuss some possible limitations and provide sugges￾tions for future research. The most important drawback of least squares is its running time and memory requirement: Smolyak’s algorithm is mu…
Figure 11
Figure 11. Figure 11: Runtime for small dimensions 11 21 31 41 51 61 71 81 91 100 Dimension 10 0 10 1 10 2 10 3 Runtime (seconds) Runtime vs. Dimension LS scale 1 LS scale 2 SA scale 1 SA scale 2 [PITH_FULL_IMAGE:figures/full_fig_p027_11.png]
Figure 12
Figure 12. Figure 12: Runtime for high dimensions Here are some further comments: • We used a rather straightforward implementation of the least squares method. We leave it for future research to perform nu￾merical tests in the above setting with more elaborate methods to find an (approxim…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 35 canonical work pages

  1. [1]

    Anderson, Z

    E. Anderson, Z. Bai, C. Bischof et al., LAPACK users’ guide , Society for Industrial and Applied Mathematics, 3, 1999, doi: 10.1137/1.9780898719604

    doi:10.1137/1.9780898719604 1999

  2. [2]

    Bartel, M

    F. Bartel, M. Sch¨ afer and T. Ullrich,Constructive subsampling of finite frames with applications in optimal function recovery , Applied Comput. Harmon. Anal., 65, 209—248, 2023, doi: 10.1016/j.acha.2023.02.004

    work page doi:10.1016/j.acha.2023.02.004 2023

  3. [3]

    Barthelmann, E

    V. Barthelmann, E. Novak and K. Ritter, High dimensional polynomial inter- polation on sparse grids , Advances in Computational Mathematics 12, 273– 288, 2000, doi: 10.1023/A:1018977404843

    doi:10.1023/a:1018977404843

  4. [4]

    Bos, J.P

    L. Bos, J.P. Calvi, N. Levenberg, A. Sommariva and M. Vianello, Geometric weakly admissible meshes, discrete least squares approximations and approxi- mate Fekete points , Math. Comp., 80, 1623–1638, 2011, doi: 10.1090/S0025- 5718-2011-02442-7

    doi:10.1090/s0025- 2011

  5. [5]

    Bos, Fekete points as norming sets , Dolomites Research Notes on Approxi- mation, 11(4), 26-–34, 2018, doi: 10.14658/PUPJ-DRNA-2018-4-3

    L. Bos, Fekete points as norming sets , Dolomites Research Notes on Approxi- mation, 11(4), 26-–34, 2018, doi: 10.14658/PUPJ-DRNA-2018-4-3

    work page doi:10.14658/pupj-drna-2018-4-3 2018

  6. [6]

    Bos, On optimal designs for a d-cube , Dolomites Research Notes on Ap- proximation, 15(4), 20–34, 2018, doi: 10.14658/PUPJ-DRNA-2022-4-3

    L. Bos, On optimal designs for a d-cube , Dolomites Research Notes on Ap- proximation, 15(4), 20–34, 2018, doi: 10.14658/PUPJ-DRNA-2022-4-3

    work page doi:10.14658/pupj-drna-2022-4-3 2018

  7. [7]

    L. Bos, F. Piazzon and M. Vianello, Near optimal polynomial regres- sion on norming meshes , Sampling Theory and Applications, 2019, doi: 10.1109/SampTA45681.2019.9030910

    work page arXiv 2019

  8. [8]

    Bungartz and M

    H.J. Bungartz and M. Griebel, Sparse grids, Acta Numerica 13, 147–269, 2004, doi: 10.1017/S0962492904000182 SPARSE GRIDS VS. RANDOM POINTS 29

    doi:10.1017/s0962492904000182 2004

Show all 53 references
  1. [9]

    Becker, O

    L. Becker, O. Klein, J. Slote, A. Volberg and H. Zhang, Dimension-free dis- cretizations of the uniform norm by small product sets , Invent. math., 239, 469–503, 2025, doi: 10.1007/s00222-024-01306-9

    2025 doi

  2. [10]

    Calvi and N

    J.P. Calvi and N. Levenberg, Uniform approximation by discrete least squares polynomials , J. Approx. Theory, 152(1), 82–100, 2009, doi: 10.1016/j.jat.2007.05.005

    2009 doi

  3. [11]

    Chkifa, A

    A. Chkifa, A. Cohen, G. Migliorati, F. Nobile and R. Tempone, Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs , M2AN, 49, 815—837, 2015, doi: 10.1051/m2an/2014050

    2015

  4. [12]

    Chkifa and M

    A. Chkifa and M. Dolbeault, Randomized least-squares with minimal over- sampling and interpolation in general spaces , SIAM J. Numer. Anal. 62(4), 1515–1538, 2024, doi: 10.1137/23M160178X

    2024 doi

  5. [13]

    Cohen, M.A

    A. Cohen, M.A. Davenport and D. Leviatan, On the stability and accuracy of least squares approximations, Foundations of Computational Mathematics, 13, 819–834, 2013, doi: 10.1007/s10208-013-9142-3

    2013 doi

  6. [14]

    Cohen, G

    A. Cohen, G. Migliorati, Optimal weighted least squares methods , SMAI J. Comput. Math. 3, 181—203, 2017, doi: 10.5802/smai-jcm.24

    2017 doi

  7. [15]

    Coleman and S

    C. Coleman and S. Lyon, Efficient implementations of Smolyak’s algorithm for function approximation in Python and Julia 2013, https://github.com/ EconForge/Smolyak

    2013

  8. [16]

    Dolbeault and A

    M. Dolbeault and A. Cohen, Optimal pointwise sampling for L2 approximation, J. Complexity, 68, 101602, 2022, doi: 10.1016/j.jco.2021.101602

    2022

  9. [17]

    Dolbeault, D

    M. Dolbeault, D. Krieg and M. Ullrich, A sharp upper bound for sam- pling numbers in L2, Appl. Comput. Harmon. Anal. 63, 113–134, 2023, doi: 10.1016/j.acha.2022.12.001

    2023 doi

  10. [18]

    Dai and A

    F. Dai and A. Prymak, Optimal polynomial meshes exist on any multi- variate convex domain , Found Comput Math, 24, 989–1018, 2024, doi: 10.1007/s10208-023-09606-x

    2024 doi

  11. [19]

    D˜ ung, V

    D. D˜ ung, V. Temlyakov and T. Ullrich, Hyperbolic cross approximation Birkh¨ auser Cham, 2018, doi: 10.1007/978-3-319-92240-9

    2018 doi

  12. [20]

    Ehlich and K

    H. Ehlich and K. Zeller, Auswertung der Normen von Interpolationsoperatoren, Mathematische Annalen, 105–112, 1966, doi: 10.1007/BF01429047

    1966 doi

  13. [21]

    Genz, Testing multidimensional integration routines, Proc

    A. Genz, Testing multidimensional integration routines, Proc. of International Conference on Tools, Methods and Languages for Scientific and Engineering Computation, 81–94, 1984

    1984

  14. [22]

    A. Genz, A package for testing multiple integration subroutines , Numerical integration: Recent developments, software and applications, 203, 337–340, 1987, doi: 10.1007/978-94-009-3889-2 33

    1987 doi

  15. [23]

    Griebel, H

    M. Griebel, H. Harbrecht and M. Multerer, Kernel interpolation on sparse grids, arXiv:2505.12282, 2025

    2025 arXiv

  16. [24]

    Gr¨ ochenig, Sampling, Marcinkiewicz-Zygmund inequalities, approxima- tion, and quadrature rules , J

    K. Gr¨ ochenig, Sampling, Marcinkiewicz-Zygmund inequalities, approxima- tion, and quadrature rules , J. Approx. Theory, 257:105455, 2020, doi: 10.1016/j.jat.2020.105455

    2020

  17. [25]

    L. Guo, A. Narayan and T. Zhou, Constructing least-squares polynomial ap- proximations, SIAM Review, 62(2), 483–508, 2020, doi: 10.1137/18M1234151

    2020 doi

  18. [26]

    Harris, K.J.Millman and S

    C.R. Harris, K.J.Millman and S. van der Walt et al., Array programming with NumPy, Nature, 585, 357–362, 2020, doi: 10.1038/s41586-020-2649-2

    2020 doi

  19. [27]

    Johnson, Why, when, and how biochemists should use least squares , Ana- lytical biochemistry, 206(2), 215-225, 1992, doi: 10.1016/0003-2697(92)90356-c

    M.L. Johnson, Why, when, and how biochemists should use least squares , Ana- lytical biochemistry, 206(2), 215-225, 1992, doi: 10.1016/0003-2697(92)90356-c

    1992 doi

  20. [28]

    K.L. Judd, L. Maliar, S. Maliar and R. Valero, Smolyak method for solv- ing dynamic economic models: Lagrange interpolation, anisotropic grid and SPARSE GRIDS VS. RANDOM POINTS 30 adaptive domain J. Economic Dynamics and Control, 44, 92–123, 2014, doi: 10.1016/j.jedc.2014.03.003

    2014 doi

  21. [29]

    Kashin, S

    B. Kashin, S. Konyagin and V. Temlyakov, Sampling discretization of the uni- form norm , Constr. Approx., 57(2), 663–694, 2023, doi: 10.1007/s00365-023- 09618-4

    2023 doi

  22. [30]

    Kashin, E

    B. Kashin, E. Kosov, I. Limonova and V. Temlyakov, Sampling discretization and related problems, J. Complexity, 101653, 2022

    2022

  23. [31]

    Kro´ o,On optimal polynomial meshes, J

    A. Kro´ o,On optimal polynomial meshes, J. Approx Theory, 163(9), 1107–1124, 2011, doi: 10.1016/j.jat.2011.03.007

    2011 doi

  24. [32]

    Krieg, K

    D. Krieg, K. Pozharska, M. Ullrich and T. Ullrich, Sampling projections in the uniform norm to appear in Forum Math Sigma, 2025, https://arxiv.org/ abs/2401.02220

    2025

  25. [33]

    Krieg, K

    D. Krieg, K. Pozharska, M. Ullrich, T. Ullrich, Sampling recovery in L2 and other norms , to appear in Math. Comp., 2023, https://arxiv.org/abs/ 2305.07539

    2023

  26. [34]

    Krieg, P

    D. Krieg, P. Siedlecki, M. Ullrich and H. Wo´ zniakowski,Exponential tractability of L2-approximation with function values , Adv. Comput. Math. 49, 18, 2023, doi: 10.1007/s10444-023-10021-7

    2023 doi

  27. [35]

    Krieg and M

    D. Krieg and M. Ullrich, Function values are enough for L2-approximation, Found. Comp. Mathematics, 21(4), 1141–1151, 2021, doi: 10.1007/s10208- 020-09481-w

    2021 doi

  28. [36]

    Krieg and M

    D. Krieg and M. Ullrich, Function values are enough for L2-approximation: Part II , J. Complexity 66, 101569, 2021, doi: 10.1016/j.jco.2021.101569

    2021

  29. [37]

    Lines and S

    L.R. Lines and S. Treitel, A review of least-squares inversion and its application to geophysical problems , Geophysical prospecting, 32(2), 159-186, 1984

    1984

  30. [38]

    Migliorati, F

    G. Migliorati, F. Nobile, E. von Schwerin and R. Tempone, Analysis of dis- crete projection on polynomial spaces with random evaluations, Found Comput Math, 14, 419-–456, 2014, doi: 10.1007/s10208-013-9186-4

    2014 doi

  31. [39]

    Narayan, J

    A. Narayan, J. Jakeman, T. Zhou, A Christoffel function weighted least squares algorithm for collocation approximations , Math. Comp. 86 (306), 1913–1947, 2017, http://arxiv.org/abs/1412.4305

    1913 arXiv

  32. [40]

    Novak and K

    E. Novak and K. Ritter, High dimensional integration of smooth functions over cubes, Num. Mathematik, 75, 79–97, 1996, doi: 10.1007/s002110050231

    1996 doi

  33. [41]

    Novak and K

    E. Novak and K. Ritter, Simple cubature formulas with high polynomial exact- ness, Constr. Approx., 15, 499—522, 1999, doi: 10.1007/s003659900119

    1999 doi

  34. [42]

    Narayan and Y

    A. Narayan and Y. Xu, Randomized weakly admissible meshes , J. Approx. Theory, 285, 105835, 2023, doi: 10.1016/j.jat.2022.105835

    2023

  35. [43]

    Reichel On polynomial approximation in the uniform norm by the discrete least squares method , BIT, 26(3), 349–368, 1986, doi: 10.1007/BF01933715

    L. Reichel On polynomial approximation in the uniform norm by the discrete least squares method , BIT, 26(3), 349–368, 1986, doi: 10.1007/BF01933715

    1986 doi

  36. [44]

    Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions , Dokl

    S.A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions , Dokl. Akad. Nauk SSSR, 148(5), 1042–1045, 1963, http://mathscinet.ams.org/mathscinet-getitem?mr=0147825

    1963

  37. [45]

    Sonnleitner, M

    M. Sonnleitner, M. Ullrich, On the power of iid information for linear approx- imation, J. Appl. Numer. Anal., 1, 88–126, 2023, doi: 10.30970/ana.2023.1.88

    2023 doi

  38. [46]

    Stoyanov, User manual: TASMANIAN sparse grids , ORNL/TM- 2015/596, 2015

    M.K. Stoyanov, User manual: TASMANIAN sparse grids , ORNL/TM- 2015/596, 2015

    2015

  39. [47]

    Stoyanov, D

    M.K. Stoyanov, D. Lebrun-Grandie, J. Burkardt and D. Munster, Tasmanian, 2013, doi: 10.11578/dc.20171025.on.1087

    2013 doi

  40. [48]

    Surjanovic and D

    S. Surjanovic and D. Bingham, Virtual library of simulation experiments: Test functions and datasets , 2013, retrieved March 29, 2025, https://www.sfu. ca/~ssurjano/integration.html

    2013

  41. [49]

    V. N. Temlyakov, On optimal recovery in L2, J. Complexity, 65, 101545, 2021, doi: 10.1016/j.jco.2020.101545. SPARSE GRIDS VS. RANDOM POINTS 31

    2021

  42. [50]

    Temlyakov, Approximation of periodic functions of several variables by trigonometric polynomials, and widths of some classes of functions , Math

    V.N. Temlyakov, Approximation of periodic functions of several variables by trigonometric polynomials, and widths of some classes of functions , Math. USSR-Izv., 27(2), 285–322, 1986, doi: 10.1070/IM1986v027n02ABEH001179

    1986 doi

  43. [51]

    Ullrich, On the worst-case error of least squares algorithms for L2- approximation with high probability , J

    M. Ullrich, On the worst-case error of least squares algorithms for L2- approximation with high probability , J. Complexity, 101484, 2020, doi: 10.1016/j.jco.2020.101484

    2020

  44. [52]

    Virtanen, R

    P. Virtanen, R. Gommers and T.E. Oliphant et al., SciPy 1.0: Fundamental algorithms for scientific computing in Python , Nature Methods, 17, 261–272, 2020, doi: 10.1038/s41592-019-0686-2

    2020 doi

  45. [53]

    Wasilkowski and H

    G.W. Wasilkowski and H. Wo´ zniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems , J. Complexity, 11(1), 1–56, 1995, doi: 10.1006/jcom.1995.1001

    1995

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.