No CrossRef data available.
Article contents
Approximation of functions: Optimal sampling and complexity
Part of:
General; Approximations and expansions
Approximations and expansions
Numerical analysis
Numerical approximation and computational geometry
Normed linear spaces and Banach spaces; Banach lattices
Published online by Cambridge University Press: 19 June 2026
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
We consider the approximation or recovery of functions based on a finite number of function evaluations. This is a well-studied problem in optimal recovery, machine learning and numerical analysis in general, but many fundamental insights were obtained only recently. We discuss different aspects of the information-theoretic limit that appears because of the limited data available, as well as algorithms and sampling strategies that come as close to it as possible.
We also discuss (optimal) sampling in a broader sense, allowing other types of measurements that may be nonlinear, adaptive and random, and present several relations between the different settings in the spirit of information-based complexity. We hope that this article will provide both a basic introduction to the subject and a contemporary summary of the current state of research.
Information
- Type
- Research Article
- Information
- Creative Commons
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.- Copyright
- © The Author(s), 2026. Published by Cambridge University Press
References
Adcock, B. (2025), Optimal sampling for least-squares approximation,
Found. Comput. Math.
25, 1975–2034.10.1007/s10208-025-09738-2CrossRefGoogle Scholar
Adcock, B. and Cardenas, J. M. (2020), Near-optimal sampling strategies for multivariate function approximation on general domains,
SIAM J. Math. Data Sci.
2, 607–630.10.1137/19M1279459CrossRefGoogle Scholar
Adcock, B., Brugiapaglia, S. and Webster, C. G. (2022),
Sparse Polynomial Approximation of High-Dimensional Functions
, Vol. 25 of Computational Science & Engineering, SIAM.10.1137/1.9781611976885CrossRefGoogle Scholar
Adcock, B., Brugiapaglia, S., Dexter, N. and Moraga, S. (2024),
On Efficient Algorithms for Computing Near-Best Polynomial Approximations to High-Dimensional, Hilbert-Valued Functions from Limited Samples
, Vol. 13 of Memoirs of the European Mathematical Society, European Mathematical Society (EMS).10.4171/mems/13CrossRefGoogle Scholar
Aistleitner, C. and Dick, J. (2015), Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality,
Acta Arith.
167, 143–171.10.4064/aa167-2-4CrossRefGoogle Scholar
An, C., Cai, M. and Goda, T. (2026), Quasi-Monte Carlo hyperinterpolation,
J. Comput. Appl. Math.
486, art. 117612.10.1016/j.cam.2026.117612CrossRefGoogle Scholar
An, C., Ran, J. and Wu, H.-N. (2025), The path of hyperinterpolation: A survey,
Dolomites Res. Notes Approx.
18, 135–145.Google Scholar
Arcangéli, R., López de Silanes, M. C. and Torrens, J. J. (2007), An extension of a bound for functions in Sobolev spaces, with applications to (m, s)-spline interpolation and smoothing,
Numer. Math.
107, 181–211.10.1007/s00211-007-0092-zCrossRefGoogle Scholar
Aronszajn, N. (1950), Theory of reproducing kernels,
Trans. Amer. Math. Soc.
68, 337–404.10.1090/S0002-9947-1950-0051437-7CrossRefGoogle Scholar
Babenko, K. I. (1960), About the approximation of periodic functions of many variable trigonometric polynomials,
Dokl. Akad. Nauk
32, 247–250.Google Scholar
Bach, F. (2024),
Learning Theory from First Principles
, Adaptive Computation and Machine Learning, MIT Press.Google Scholar
Bachmayr, M., Dahmen, W., DeVore, R. and Grasedyck, L. (2014), Approximation of high-dimensional rank one tensors,
Constr. Approx.
39, 385–395.10.1007/s00365-013-9219-xCrossRefGoogle Scholar
Bachmayr, M., Dusson, G., Ortner, C. and Thomas, J. (2024), Polynomial approximation of symmetric functions,
Math. Comp.
93, 811–839.10.1090/mcom/3868CrossRefGoogle Scholar
Bakhvalov, N. S. (1959), On the approximate calculation of multiple integrals,
Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him.
1959, 3–18. English translation: J. Complexity 31, 502–516 (2015).Google Scholar
Bartel, F. (2023), Error guarantees for least squares approximation with noisy samples in domain adaptation,
SMAI J. Comput. Math.
9, 95–120.10.5802/smai-jcm.96CrossRefGoogle Scholar
Bartel, F. and Dũng, D. (2024), Sampling recovery in Bochner spaces and applications to parametric PDEs. Available at arXiv:2409.05050.Google Scholar
Bartel, F., Kämmerer, L., Pozharska, K., Schäfer, M. and Ullrich, T. (2025), Exact discretization, tight frames and recovery via D-optimal designs,
SMAI J. Comput. Math.
11, 607–636.10.5802/smai-jcm.136CrossRefGoogle Scholar
Bartel, F., Schäfer, M. and Ullrich, T. (2023), Constructive subsampling of finite frames with applications in optimal function recovery,
Appl. Comput. Harmon. Anal.
65, 209–248.10.1016/j.acha.2023.02.004CrossRefGoogle Scholar
Barthelmann, V., Novak, E. and Ritter, K. (2000), High dimensional polynomial interpolation on sparse grids,
Adv. Comput. Math.
12, 273–288.10.1023/A:1018977404843CrossRefGoogle Scholar
Batson, J., Spielman, D. A. and Srivastava, N. (2014), Twice-Ramanujan sparsifiers,
SIAM Rev.
56, 315–334.10.1137/130949117CrossRefGoogle Scholar
Bauer, B., Devroye, L., Kohler, M., Krzyżak, A. and Walk, H. (2017), Nonparametric estimation of a function from noiseless observations at random points,
J. Multivariate Anal.
160, 93–104.10.1016/j.jmva.2017.05.010CrossRefGoogle Scholar
Bauhardt, W. (1977), Hilbert-Zahlen von Operatoren in Banachräumen,
Math. Nachr.
79, 181–187.10.1002/mana.19770790114CrossRefGoogle Scholar
Belhadji, A., Bardenet, R. and Chainais, P. (2026), Signal reconstruction using determinantal sampling,
Appl. Comput. Harmon. Anal.
82, art. 101822.10.1016/j.acha.2025.101822CrossRefGoogle Scholar
Belkin, M. (2021), Fit without fear: Remarkable mathematical phenomena of deep learning through the prism of interpolation,
Acta Numer.
30, 203–248.10.1017/S0962492921000039CrossRefGoogle Scholar
Bellman, R. (1957),
Dynamic Programming
, Rand Corporation research study, Princeton University Press.Google ScholarPubMed
Belloni, A., Chernozhukov, V. and Wang, L. (2011), Square-root lasso: Pivotal recovery of sparse signals via conic programming,
Biometrika
98, 791–806.10.1093/biomet/asr043CrossRefGoogle Scholar
Ben-David, S., Blitzer, J., Crammer, K. and Pereira, F. (2006), Analysis of representations for domain adaptation, in
Advances in Neural Information Processing Systems 19
(Schölkopf, B. et al., eds), MIT Press.Google Scholar
Bernardi, C. and Maday, Y. (1992), Polynomial interpolation results in Sobolev spaces,
J. Comput. Appl. Math.
43, 53–80.10.1016/0377-0427(92)90259-ZCrossRefGoogle Scholar
Bernstein, S. (1931), Sur la limitation des valeurs d’un polynôme P n(x) de degré n sur tout un segment par ses valeurs en (n + 1) points du segment,
Bull. Acad. Sci. URSS
1931, 1025–1050.Google Scholar
Binev, P., Bonito, A., Cohen, A., Dahmen, W., DeVore, R. and Petrova, G. (2024a), Solving PDEs with incomplete information,
SIAM J. Numer. Anal.
62, 1278–1312.10.1137/23M1546671CrossRefGoogle Scholar
Binev, P., Bonito, A., DeVore, R. and Petrova, G. (2024b), Optimal learning,
Calcolo
61, art. 15.10.1007/s10092-023-00564-yCrossRefGoogle Scholar
Bonito, A., Canuto, C., Nochetto, R. H. and Veeser, A. (2024), Adaptive finite element methods,
Acta Numer.
33, 163–485.10.1017/S0962492924000011CrossRefGoogle Scholar
Borsuk, K. (1933), Drei Sätze über die n-dimensionale euklidische Sphäre,
Fundam. Math.
20, 177–190.10.4064/fm-20-1-177-190CrossRefGoogle Scholar
Bos, L. (2018), Fekete points as norming sets,
Dolomites Res. Notes Approx.
11, 26–34.Google Scholar
Bos, L., Calvi, J.-P., Levenberg, N., Sommariva, A. and Vianello, M. (2011), Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points,
Math. Comp.
80, 1623–1638.10.1090/S0025-5718-2011-02442-7CrossRefGoogle Scholar
Bourgain, J. (2014), An improved estimate in the restricted isometry problem, in
Geometric Aspects of Functional Analysis: Proceedings of the Israel Seminar (GAFA) 2011–2013
, Springer, pp. 65–70.10.1007/978-3-319-09477-9_5CrossRefGoogle Scholar
Boutsidis, C., Drineas, P. and Magdon-Ismail, M. (2014), Near-optimal column-based matrix reconstruction,
SIAM J. Comput.
43, 687–717.10.1137/12086755XCrossRefGoogle Scholar
Brauchart, J. S., Dick, J., Saff, E. B., Sloan, I. H., Wang, Y. G. and Womersley, R. S. (2015), Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces,
J. Math. Anal. Appl.
431, 782–811.10.1016/j.jmaa.2015.05.079CrossRefGoogle Scholar
Brenner, S. and Scott, L. (2008),
The Mathematical Theory of Finite Element Methods
, Vol. 15 of Texts in Applied Mathematics, Springer.10.1007/978-0-387-75934-0CrossRefGoogle Scholar
Brugiapaglia, S., Dirksen, S., Jung, H. C. and Rauhut, H. (2021), Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs,
Appl. Comput. Harmon. Anal.
53, 231–269.10.1016/j.acha.2021.01.004CrossRefGoogle Scholar
Buhmann, M. D. (2003),
Radial Basis Functions: Theory and Implementations
, Vol. 12 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press.10.1017/CBO9780511543241CrossRefGoogle Scholar
Byrenheid, G., Kunsch, R. J. and Nguyen, V. K. (2018), Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness,
J. Complexity
46, 90–102.10.1016/j.jco.2017.12.002CrossRefGoogle Scholar
Cahill, J., Casazza, P. G. and Daubechies, I. (2016), Phase retrieval in infinite-dimensional Hilbert spaces,
Trans. Amer. Math. Soc. Ser. B
3, 63–76.10.1090/btran/12CrossRefGoogle Scholar
Calvi, J.-P. and Levenberg, N. (2008), Uniform approximation by discrete least squares polynomials,
J. Approx. Theory
152, 82–100.10.1016/j.jat.2007.05.005CrossRefGoogle Scholar
Candès, E. J. and Tao, T. (2005), Decoding by linear programming,
IEEE Trans. Inform. Theory
51, 4203–4215.10.1109/TIT.2005.858979CrossRefGoogle Scholar
Candès, E. J. and Tao, T. (2006), Near-optimal signal recovery from random projections: Universal encoding strategies?,
IEEE Trans. Inform. Theory
52, 5406–5425.10.1109/TIT.2006.885507CrossRefGoogle Scholar
Candès, E. J., Eldar, Y. C., Strohmer, T. and Voroninski, V. (2015), Phase retrieval via matrix completion,
SIAM Rev.
57, 225–251.10.1137/151005099CrossRefGoogle Scholar
Candès, E. J., Romberg, J. K. and Tao, T. (2006), Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,
IEEE Trans. Inform. Theory
52, 489–509.10.1109/TIT.2005.862083CrossRefGoogle Scholar
Candès, E. J., Wakin, M. B. and Boyd, S. P. (2008), Enhancing sparsity by reweighted ℓ 1 minimization,
J. Fourier Anal. Appl.
14, 877–905.10.1007/s00041-008-9045-xCrossRefGoogle Scholar
Carl, B. (1981a), Entropy numbers of embedding maps between Besov spaces with an application to eigenvalue problems,
Proc. Roy. Soc. Edinburgh Sect. A
90, 63–70.10.1017/S0308210500015341CrossRefGoogle Scholar
Carl, B. (1981b), Entropy numbers, s-numbers, and eigenvalue problems,
J. Funct. Anal.
41, 290–306.10.1016/0022-1236(81)90076-8CrossRefGoogle Scholar
Carl, B. and Stephani, I. (1990),
Entropy, Compactness and the Approximation of Operators
, Vol. 98 of Cambridge Tracts in Mathematics, Cambridge University Press.10.1017/CBO9780511897467CrossRefGoogle Scholar
Chatterjee, S. and Hadi, A. S. (1986), Influential observations, high leverage points, and outliers in linear regression,
Statist. Sci.
1, 379–416.Google Scholar
Chen, L. and Jiang, H. (2024), On the information complexity for integration in subspaces of the Wiener algebra,
J. Complexity
81, art. 101819.10.1016/j.jco.2023.101819CrossRefGoogle Scholar
Cheraghchi, M., Guruswami, V. and Velingker, A. (2013), Restricted isometry of Fourier matrices and list decodability of random linear codes, in
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
, SIAM and ACM, pp. 432–442.Google Scholar
Chkifa, A., Cohen, A., Migliorati, G., Nobile, F. and Tempone, R. (2015), Discrete least squares polynomial approximation with random evaluations: Application to parametric and stochastic elliptic PDEs,
ESAIM Math. Model. Numer. Anal.
49, 815–837.10.1051/m2an/2014050CrossRefGoogle Scholar
Chkifa, A., Dexter, N., Tran, H. and Webster, C. G. (2018), Polynomial approximation via compressed sensing of high-dimensional functions on lower sets,
Math. Comp.
87, 1415–1450.10.1090/mcom/3272CrossRefGoogle Scholar
Chkifa, A., Dolbeault, M., Krieg, D. and Ullrich, M. (2026), Constructive discretization and approximation in reproducing kernel Hilbert spaces. Available at arXiv:2602.18719v1.Google Scholar
Ciarlet, P. G. (1978),
The Finite Element Method for Elliptic Problems
, Vol. 4 of Studies in Mathematics and its Applications, Elsevier.Google Scholar
Cobos, F., Kühn, T. and Sickel, W. (2016), Optimal approximation of multivariate periodic sobolev functions in the sup-norm,
J. Funct. Anal.
270, 4196–4212.10.1016/j.jfa.2016.03.018CrossRefGoogle Scholar
Cohen, A. and DeVore, R. (2015), Approximation of high-dimensional parametric PDEs,
Acta Numer.
24, 1–159.10.1017/S0962492915000033CrossRefGoogle Scholar
Cohen, A. and Migliorati, G. (2017), Optimal weighted least squares methods,
SMAI J. Comput. Math.
3, 181–203.10.5802/smai-jcm.24CrossRefGoogle Scholar
Cohen, A., Davenport, M. A. and Leviatan, D. (2013), On the stability and accuracy of least squares approximations,
Found. Comput. Math.
13, 819–834.10.1007/s10208-013-9142-3CrossRefGoogle Scholar
Cohen, A., DeVore, R., Petrova, G. and Wojtaszczyk, P. (2022), Optimal stable nonlinear approximation,
Found. Comput. Math.
22, 607–648.10.1007/s10208-021-09494-zCrossRefGoogle Scholar
Cohen, A., Dolbeault, M., Mula, O. and Somacal, A. (2023), Nonlinear approximation spaces for inverse problems,
Anal. Appl. (Singap.)
21, 217–253.10.1142/S0219530522400140CrossRefGoogle Scholar
Creutzig, J. and Wojtaszczyk, P. (2004), Linear vs. nonlinear algorithms for linear problems,
J. Complexity
20, 807–820.10.1016/j.jco.2004.05.003CrossRefGoogle Scholar
Cucker, F. and Smale, S. (2002), On the mathematical foundations of learning,
Bull. Amer. Math. Soc. (N.S.)
39, 1–49.10.1090/S0273-0979-01-00923-5CrossRefGoogle Scholar
Dai, F. (2006), On generalized hyperinterpolation on the sphere,
Proc. Amer. Math. Soc.
134, 2931–2941.10.1090/S0002-9939-06-08421-8CrossRefGoogle Scholar
Dai, F. and Prymak, A. (2024), Optimal polynomial meshes exist on any multivariate convex domain,
Found. Comput. Math.
24, 989–1018.10.1007/s10208-023-09606-xCrossRefGoogle Scholar
Dai, F. and Temlyakov, V. (2024), Random points are good for universal discretization,
J. Math. Anal. Appl.
529, art. 127570.10.1016/j.jmaa.2023.127570CrossRefGoogle Scholar
Dai, F., Prymak, A., Shadrin, A., Temlyakov, V. and Tikhonov, S. (2021), Entropy numbers and Marcinkiewicz-type discretization,
J. Funct. Anal.
281, art. 109090.10.1016/j.jfa.2021.109090CrossRefGoogle Scholar
Dai, F., Prymak, A., Temlyakov, V. N. and Tikhonov, S. Y. (2019), Integral norm discretization and related problems,
Russ. Math. Surv.
74, 579–630.10.1070/RM9892CrossRefGoogle Scholar
Day, M. M. (1955), Strict convexity and smoothness of normed spaces,
Trans. Amer. Math. Soc.
78, 516–528.10.1090/S0002-9947-1955-0067351-1CrossRefGoogle Scholar
DeVore, R. A. (1998), Nonlinear approximation,
Acta Numer.
7, 51–150.10.1017/S0962492900002816CrossRefGoogle Scholar
DeVore, R. A. (2007), Deterministic constructions of compressed sensing matrices,
J. Complexity
23, 918–925.10.1016/j.jco.2007.04.002CrossRefGoogle Scholar
DeVore, R. A., Howard, R. and Micchelli, C. (1989), Optimal nonlinear approximation,
Manuscr. Math.
63, 469–478.10.1007/BF01171759CrossRefGoogle Scholar
DeVore, R. A., Kyriazis, G., Leviatan, D. and Tikhomirov, V. M. (1993), Wavelet compression and nonlinear n-widths,
Adv. Comput. Math.
1, 197–214.10.1007/BF02071385CrossRefGoogle Scholar
DeVore, R., Hanin, B. and Petrova, G. (2021), Neural network approximation,
Acta Numer.
30, 327–444.10.1017/S0962492921000052CrossRefGoogle Scholar
DeVore, R., Petrova, G. and Wojtaszczyk, P. (2017), Data assimilation and sampling in Banach spaces,
Calcolo
54, 963–1007.10.1007/s10092-017-0216-5CrossRefGoogle Scholar
Dick, J. (2014), Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series,
J. Approx. Theory
183, 14–30.10.1016/j.jat.2014.03.015CrossRefGoogle Scholar
Dick, J., Goda, T. and Suzuki, K. (2025), Tractability results for integration in subspaces of the Wiener algebra,
J. Complexity
90, art. 101948.10.1016/j.jco.2025.101948CrossRefGoogle Scholar
Dick, J., Kritzer, P. and Pillichshammer, F. (2022),
Lattice Rules: Numerical Integration, Approximation, and Discrepancy
, Vol. 58 of Springer Series in Computational Mathematics, Springer.10.1007/978-3-031-09951-9CrossRefGoogle Scholar
Dick, J., Kritzer, P., Pillichshammer, F. and Woźniakowski, H. (2014), Approximation of analytic functions in Korobov spaces,
J. Complexity
30, 2–28.10.1016/j.jco.2013.05.001CrossRefGoogle Scholar
Dick, J., Kuo, F. Y. and Sloan, I. H. (2013), High-dimensional integration: The quasi-Monte Carlo way,
Acta Numer.
22, 133–288.10.1017/S0962492913000044CrossRefGoogle Scholar
Dinu, M.-C., Holzleitner, M., Beck, M., Nguyen, H. D., Huber, A., Eghbal-Zadeh, H., Moser, B. A., Pereverzyev, S., Hochreiter, S. and Zellinger, W. (2023), Addressing parameter choice issues in unsupervised domain adaptation by aggregation, in
The Eleventh International Conference on Learning Representations (ICLR 2023)
.Google Scholar
Dolbeault, M. and Chkifa, M. A. (2024), Randomized least-squares with minimal oversampling and interpolation in general spaces,
SIAM J. Numer. Anal.
62, 1515–1538.10.1137/23M160178XCrossRefGoogle Scholar
Dolbeault, M. and Cohen, A. (2022a), Optimal pointwise sampling for L 2 approximation,
J. Complexity
68, art. 101602.10.1016/j.jco.2021.101602CrossRefGoogle Scholar
Dolbeault, M. and Cohen, A. (2022b), Optimal sampling and Christoffel functions on general domains,
Constr. Approx.
56, 121–163.10.1007/s00365-021-09558-xCrossRefGoogle Scholar
Dolbeault, M., Krieg, D. and Ullrich, M. (2023), A sharp upper bound for sampling numbers in L 2,
Appl. Comput. Harmon. Anal.
63, 113–134.10.1016/j.acha.2022.12.001CrossRefGoogle Scholar
Donoho, D. L. (2006), Compressed sensing,
IEEE Trans. Inform. Theory
52, 1289–1306.10.1109/TIT.2006.871582CrossRefGoogle Scholar
Dũng, D., Temlyakov, V. N. and Ullrich, T. (2018),
Hyperbolic Cross Approximation
, Advanced Courses in Mathematics, CRM Barcelona, Springer International Publishing.10.1007/978-3-319-92240-9CrossRefGoogle Scholar
Ebert, A. and Pillichshammer, F. (2021), Tractability of approximation in the weighted Korobov space in the worst-case setting: A complete picture,
J. Complexity
67, art. 101571.10.1016/j.jco.2021.101571CrossRefGoogle Scholar
Edmunds, D. E. and Lang, J. (2013), Gelfand numbers and widths,
J. Approx. Theory
166, 78–84.10.1016/j.jat.2012.10.008CrossRefGoogle Scholar
Ehler, M., Graef, M. and Oates, C. J. (2019), Optimal Monte Carlo integration on closed manifolds,
Statist. Comput.
29, 1203–1214.10.1007/s11222-019-09894-wCrossRefGoogle Scholar
Erdős, P. (1961), Problems and results on the theory of interpolation II,
Acta Math. Acad. Sci. Hung.
12, 235–244.10.1007/BF02066686CrossRefGoogle Scholar
Erdős, P. and Turan, P. (1937), On interpolation I: Quadrature- and mean-convergence in the Lagrange-interpolation,
Ann. of Math. (2)
38, 142–155.10.2307/1968516CrossRefGoogle Scholar
Faber, G. (1914), Über die interpolatorische Darstellung stetiger Funktionen,
Jahresber. Dtsch. Math.-Ver.
23, 192–210.Google Scholar
Fang, G. and Duan, L. (2008), The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods,
J. Complexity
24, 398–409.10.1016/j.jco.2007.11.001CrossRefGoogle Scholar
Fannjiang, A. and Strohmer, T. (2020), The numerics of phase retrieval,
Acta Numer.
29, 125–228.10.1017/S0962492920000069CrossRefGoogle Scholar
Fasshauer, G. E., Hickernell, F. J. and Woźniakowski, H. (2012), On dimension-independent rates of convergence for function approximation with Gaussian kernels,
SIAM J. Numer. Anal.
50, 247–271.10.1137/10080138XCrossRefGoogle Scholar
Foucart, S. (2021), Instances of computational optimal recovery: Refined approximability models,
J. Complexity
62, art. 101503.10.1016/j.jco.2020.101503CrossRefGoogle Scholar
Foucart, S. (2022),
Mathematical Pictures at a Data Science Exhibition
, Cambridge University Press.10.1017/9781009003933CrossRefGoogle Scholar
Foucart, S. and Rauhut, H. (2013),
A Mathematical Introduction to Compressive Sensing
, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer.10.1007/978-0-8176-4948-7CrossRefGoogle Scholar
Freud, G. (1969),
Orthogonale Polynome
, Vol. 33 of Lehrbücher und Monographien aus dem Gebiete der Exakten Wissenschaften, Mathematische Reihe, Birkhäuser.10.1007/978-3-0348-7169-3CrossRefGoogle Scholar
Ganin, Y. and Lempitsky, V. (2015), Unsupervised domain adaptation by backpropagation, in
Proceedings of the 32nd International Conference on Machine Learning
(Bach, F. and Blei, D., eds), Vol. 37 of Proceedings of Machine Learning Research, PMLR, pp. 1180–1189.Google Scholar
Garling, D. J. H. and Gordon, Y. (1971), Relations between some constants associated with finite dimensional Banach spaces,
Israel J. Math.
9, 346–361.10.1007/BF02771685CrossRefGoogle Scholar
Garnaev, A. Y. and Gluskin, E. D. (1984), On widths of the Euclidean ball,
Sov. Math. Dokl.
30, 200–204.Google Scholar
Geng, J. and Wang, H. (2024), On the power of standard information for tractability for l ∞ approximation of periodic functions in the worst case setting,
J. Complexity
80, art. 101790.10.1016/j.jco.2023.101790CrossRefGoogle Scholar
Giles, M. B. (2015), Multilevel Monte Carlo methods,
Acta Numer.
24, 259–328.10.1017/S096249291500001XCrossRefGoogle Scholar
Gizewski, E. R., Mayer, L., Moser, B. A., Nguyen, D. H., Pereverzyev, S., Pereverzyev, S. V., Shepeleva, N. and Zellinger, W. (2022), On a regularization of unsupervised domain adaptation in RKHS,
Appl. Comput. Harmon. Anal.
57, 201–227.10.1016/j.acha.2021.12.002CrossRefGoogle Scholar
Gnewuch, M. and Woźniakowski, H. (2011), Quasi-polynomial tractability,
J. Complexity
27, 312–330.10.1016/j.jco.2010.07.001CrossRefGoogle Scholar
Goda, T. (2023), Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series,
Proc. Amer. Math. Soc.
151, 3925–3933.Google Scholar
Griebel, M. and Oettershagen, J. (2016), On tensor product approximation of analytic functions,
J. Approx. Theory
207, 348–379.10.1016/j.jat.2016.02.006CrossRefGoogle Scholar
Gröchenig, K. (1999), Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type,
Math. Comp.
68, 749–765.10.1090/S0025-5718-99-01029-7CrossRefGoogle Scholar
Gröchenig, K. (2020), Sampling, Marcinkiewicz–Zygmund inequalities, approximation, and quadrature rules,
J. Approx. Theory
257, art. 105455.10.1016/j.jat.2020.105455CrossRefGoogle Scholar
Guo, L., Narayan, A. and Zhou, T. (2020), Constructing least-squares polynomial approximations,
SIAM Rev.
62, 483–508.10.1137/18M1234151CrossRefGoogle Scholar
Hansen, O., Atkinson, K. and Chien, D. (2009), On the norm of the hyperinterpolation operator on the unit disc and its use for the solution of the nonlinear Poisson equation,
IMA J. Numer. Anal.
29, 257–283.10.1093/imanum/drm052CrossRefGoogle Scholar
Haviv, I. and Regev, O. (2017), The restricted isometry property of subsampled Fourier matrices, in
Geometric Aspects of Functional Analysis: Proceedings of the Israel seminar (GAFA) 2014–2016
, Springer, pp. 163–179.10.1007/978-3-319-45282-1_11CrossRefGoogle Scholar
Heinrich, S. (1989), On the relation between linear n-widths and approximation numbers,
J. Approx. Theory
58, 315–333.10.1016/0021-9045(89)90032-4CrossRefGoogle Scholar
Heinrich, S. (1992), Lower bounds for the complexity of Monte Carlo function approximation,
J. Complexity
8, 277–300.10.1016/0885-064X(92)90027-9CrossRefGoogle Scholar
Heinrich, S. (1994), Random approximation in numerical analysis, in
Functional Analysis
(Bierstedt, K. D. et al., eds), Dekker, pp. 123–171.Google Scholar
Heinrich, S. (2001), Multilevel Monte Carlo methods, in
Large-Scale Scientific Computing
(Margenov, S. et al., eds), Springer, pp. 58–67.10.1007/3-540-45346-6_5CrossRefGoogle Scholar
Heinrich, S. (2008), Randomized approximation of sobolev embeddings, in
Monte Carlo and Quasi-Monte Carlo Methods 2006
(Keller, A. et al., eds), Springer, pp. 445–459.10.1007/978-3-540-74496-2_26CrossRefGoogle Scholar
Heinrich, S. (2024a), Randomized complexity of parametric integration and the role of adaption I: Finite dimensional case,
J. Complexity
81, art. 101821.10.1016/j.jco.2023.101821CrossRefGoogle Scholar
Heinrich, S. (2024b), Randomized complexity of parametric integration and the role of adaption II: Sobolev spaces,
J. Complexity
82, art. 101823.10.1016/j.jco.2023.101823CrossRefGoogle Scholar
Heinrich, S. and Linde, R. (1984), On the asymptotic behaviour of Hilbert numbers,
Math. Nachr.
119, 117–120.10.1002/mana.19841190109CrossRefGoogle Scholar
Heinrich, S., Novak, E., Wasilkowski, G. W. and Woźniakowski, H. (2001), The inverse of the star-discrepancy depends linearly on the dimension,
Acta Arith.
96, 279–302.10.4064/aa96-3-7CrossRefGoogle Scholar
Hinrichs, A., Kolleck, A. and Vybíral, J. (2016), Carl’s inequality for quasi-Banach spaces,
J. Funct. Anal.
271, 2293–2307.10.1016/j.jfa.2016.05.011CrossRefGoogle Scholar
Hinrichs, A., Krieg, D., Novak, E. and Vybíral, J. (2021a), Lower bounds for the error of quadrature formulas for Hilbert spaces,
J. Complexity
65, art. 101544.10.1016/j.jco.2020.101544CrossRefGoogle Scholar
Hinrichs, A., Krieg, D., Novak, E. and Vybíral, J. (2022), Lower bounds for integration and recovery in L 2,
J. Complexity
72, art. 101662.10.1016/j.jco.2022.101662CrossRefGoogle Scholar
Hinrichs, A., Krieg, D., Novak, E., Prochno, J. and Ullrich, M. (2020), On the power of random information, in
Multivariate Algorithms and Information-Based Complexity
(Hickernell, F. J. and Kritzer, P., eds), De Gruyter, pp. 43–64.10.1515/9783110635461-004CrossRefGoogle Scholar
Hinrichs, A., Krieg, D., Novak, E., Prochno, J. and Ullrich, M. (2021b), Random sections of ellipsoids and the power of random information,
Trans. Amer. Math. Soc.
374, 8691–8713.10.1090/tran/8502CrossRefGoogle Scholar
Hinrichs, A., Novak, E. and Ullrich, M. (2014a), On weak tractability of the Clenshaw–Curtis Smolyak algorithm,
J. Approx. Theory
183, 31–44.10.1016/j.jat.2014.03.012CrossRefGoogle Scholar
Hinrichs, A., Novak, E. and Vybíral, J. (2008), Linear information versus function evaluations for L 2-approximation,
J. Approx. Theory
153, 97–107.10.1016/j.jat.2008.02.003CrossRefGoogle Scholar
Hinrichs, A., Novak, E. and Woźniakowski, H. (2013), Discontinuous information in the worst case and randomized settings,
Math. Nachr.
286, 679–690.10.1002/mana.201100128CrossRefGoogle Scholar
Hinrichs, A., Novak, E., Ullrich, M. and Woźniakowski, H. (2014b), The curse of dimensionality for numerical integration of smooth functions,
Math. Comp.
83, 2853–2863.10.1090/S0025-5718-2014-02855-XCrossRefGoogle Scholar
Hinrichs, A., Novak, E., Ullrich, M. and Woźniakowski, H. (2014c), The curse of dimensionality for numerical integration of smooth functions II,
J. Complexity
30, 117–143.10.1016/j.jco.2013.10.007CrossRefGoogle Scholar
Hinrichs, A., Novak, E., Ullrich, M. and Woźniakowski, H. (2017), Product rules are optimal for numerical integration in classical smoothness spaces,
J. Complexity
38, 39–49.10.1016/j.jco.2016.09.001CrossRefGoogle Scholar
Hinrichs, A., Prochno, J. and Sonnleitner, M. (2023), Random sections of ℓp-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators,
J. Approx. Theory
293, art. 105919.10.1016/j.jat.2023.105919CrossRefGoogle Scholar
Hinrichs, A., Prochno, J. and Ullrich, M. (2019), The curse of dimensionality for numerical integration on general domains,
J. Complexity
50, 25–42.10.1016/j.jco.2018.08.003CrossRefGoogle Scholar
Holst, L. (1980), On the lengths of the pieces of a stick broken at random,
J. Appl. Probab.
17, 623–634.10.2307/3212956CrossRefGoogle Scholar
Hua, L. K. and Wang, Y. (1981),
Applications of Number Theory to Numerical Analysis
, revised edition, Springer.Google Scholar
Huan, X., Jagalur, J. and Marzouk, Y. (2024), Optimal experimental design: Formulations and computations,
Acta Numer.
33, 715–840.10.1017/S0962492924000023CrossRefGoogle Scholar
Irrgeher, C., Kritzer, P., Pillichshammer, F. and Woźniakowski, H. (2016), Approximation in Hermite spaces of smooth functions,
J. Approx. Theory
207, 98–126.10.1016/j.jat.2016.02.008CrossRefGoogle Scholar
Ismagilov, R. S. (1974), Diameters of sets in normed linear spaces and the approximation of functions by trigonometric polynomials,
Russ. Math. Surv.
29, 169–186.10.1070/RM1974v029n03ABEH001287CrossRefGoogle Scholar
Jahn, T., Ullrich, T. and Voigtlaender, F. (2023), Sampling numbers of smoothness classes via ℓ 1-minimization,
J. Complexity
79, art. 101786.10.1016/j.jco.2023.101786CrossRefGoogle Scholar
Kadets, M. I. and Snobar, M. G. (1971), Certain functionals on the Minkowski compactum,
Mathematical Notes
10, 694–696.10.1007/BF01106467CrossRefGoogle Scholar
Kämmerer, L., Ullrich, T. and Volkmer, T. (2021), Worst-case recovery guarantees for least squares approximation using random samples,
Constr. Approx.
54, 295–352.10.1007/s00365-021-09555-0CrossRefGoogle Scholar
Kashin, B. (1977), Diameters of some finite-dimensional sets and classes of smooth functions,
Izv. Akad. Nauk SSSR Ser. Mat.
41, 334–351.Google Scholar
Kashin, B., Konyagin, S. and Temlyakov, V. (2023), Sampling discretization of the uniform norm,
Constr. Approx.
57, 663–694.10.1007/s00365-023-09618-4CrossRefGoogle Scholar
Kashin, B., Kosov, E., Limonova, I. and Temlyakov, V. (2022), Sampling discretization and related problems,
J. Complexity
71, art. 101653.10.1016/j.jco.2022.101653CrossRefGoogle Scholar
Kiefer, J. (1959), Optimum experimental designs,
J. R. Statist. Soc. Ser. B Statist. Methodol.
21, 272–319.10.1111/j.2517-6161.1959.tb00338.xCrossRefGoogle Scholar
Kiefer, J. (1974), General equivalence theory for optimum designs (approximate theory),
Ann. Statist.
2, 849–879.10.1214/aos/1176342810CrossRefGoogle Scholar
Kiefer, J. and Wolfowitz, J. (1960), The equivalence of two extremum problems,
Canad. J. Math.
12, 363–366.10.4153/CJM-1960-030-4CrossRefGoogle Scholar
Kolleck, A. and Vybíral, J. (2015), On some aspects of approximation of ridge functions,
J. Approx. Theory
194, 35–61.10.1016/j.jat.2015.01.003CrossRefGoogle Scholar
Kolomoitsev, Y., Lomako, T. and Tikhonov, S. (2023), Sparse grid approximation in weighted Wiener spaces,
J. Fourier Anal. Appl.
29, art. 19.10.1007/s00041-023-09994-2CrossRefGoogle Scholar
König, H. (1986),
Eigenvalue Distribution of Compact Operators
, Vol. 16 of Operator Theory: Advances and Applications, Birkhäuser.10.1007/978-3-0348-6278-3CrossRefGoogle Scholar
Korneichuk, N. P. (1994), Optimization of active algorithms for recovery of monotonic functions from Hölder’s class,
J. Complexity
10, 265–269.10.1006/jcom.1994.1013CrossRefGoogle Scholar
Kosov, E. and Tikhonov, S. (2025), Sampling discretization in Orlicz spaces,
J. Funct. Anal.
289, art. 110971.10.1016/j.jfa.2025.110971CrossRefGoogle Scholar
Kosov, E. D. and Temlyakov, V. N. (2025), Bounds for the sampling discretization error and their applications to the universal sampling discretization,
J. Complexity
90, art. 101958.10.1016/j.jco.2025.101958CrossRefGoogle Scholar
Krieg, D. (2018), Tensor power sequences and the approximation of tensor product operators,
J. Complexity
44, 30–51.10.1016/j.jco.2017.09.002CrossRefGoogle Scholar
Krieg, D. (2019), Optimal Monte Carlo methods for l 2-approximation,
Constr. Approx.
49, 385–403.10.1007/s00365-018-9428-4CrossRefGoogle Scholar
Krieg, D. (2024), Tractability of sampling recovery on unweighted function classes,
Proc. Amer. Math. Soc. Ser. B
11, 115–125.10.1090/bproc/216CrossRefGoogle Scholar
Krieg, D. and Kritzer, P. (2024), Homogeneous algorithms and solvable problems on cones,
J. Complexity
83, art. 101840.10.1016/j.jco.2024.101840CrossRefGoogle Scholar
Krieg, D. and Rudolf, D. (2019), Recovery algorithms for high-dimensional rank one tensors,
J. Approx. Theory
237, 17–29.10.1016/j.jat.2018.08.002CrossRefGoogle Scholar
Krieg, D. and Sonnleitner, M. (2024), Random points are optimal for the approximation of Sobolev functions,
IMA J. Numer. Anal.
44, 1346–1371.10.1093/imanum/drad014CrossRefGoogle Scholar
Krieg, D. and Sonnleitner, M. (2025), Function recovery on manifolds using scattered data,
J. Approx. Theory
305, art. 106098.10.1016/j.jat.2024.106098CrossRefGoogle Scholar
Krieg, D. and Ullrich, M. (2021a), Function values are enough for L 2-approximation,
Found. Comput. Math.
21, 1141–1151.10.1007/s10208-020-09481-wCrossRefGoogle Scholar
Krieg, D. and Ullrich, M. (2021b), Function values are enough for L 2-approximation II,
J. Complexity
66, art. 101569.10.1016/j.jco.2021.101569CrossRefGoogle Scholar
Krieg, D. and Vybíral, J. (2023), New lower bounds for the integration of periodic functions,
J. Fourier Anal. Appl.
29, art. 41.10.1007/s00041-023-10021-7CrossRefGoogle Scholar
Krieg, D., Novak, E. and Sonnleitner, M. (2022), Recovery of Sobolev functions restricted to iid sampling,
Math. Comp.
91, 2715–2738.10.1090/mcom/3763CrossRefGoogle Scholar
Krieg, D., Novak, E. and Ullrich, M. (2025a), On the power of adaption and randomization,
Forum Math. Sigma
13, art. e152.10.1017/fms.2025.10101CrossRefGoogle Scholar
Krieg, D., Novak, E. and Ullrich, M. (2026a), How many continuous measurements are needed to learn a vector? Available at arXiv:2412.06468. To appear in Proc. Amer. Math. Soc.
Google Scholar
Krieg, D., Novak, E., Plaskota, L. and Ullrich, M. (2026b), Noisy nonlinear information and entropy numbers,
Fourier Anal. Appl.
32, art. 36.10.1007/s00041-026-10249-zCrossRefGoogle Scholar
Krieg, D., Pozharska, K., Ullrich, M. and Ullrich, T. (2025b), Sampling recovery in L 2 and other norms,
Math. Comp.
Available at doi:10.1090/mcom/4148.CrossRefGoogle Scholar
Krieg, D., Pozharska, K., Ullrich, M. and Ullrich, T. (2026c), Sampling projections in the uniform norm,
J. Math. Anal. Appl.
553, art. 129873.10.1016/j.jmaa.2025.129873CrossRefGoogle Scholar
Krieg, D., Siedlecki, P., Ullrich, M. and Woźniakowski, H. (2023), Exponential tractability of L 2-approximation with function values,
Adv. Comput. Math.
49, art. 18.10.1007/s10444-023-10021-7CrossRefGoogle Scholar
Kroó, A. (2019), On the existence of optimal meshes in every convex domain on the plane,
J. Approx. Theory
238, 26–37.10.1016/j.jat.2017.02.004CrossRefGoogle Scholar
Kühn, T., Sickel, W. and Ullrich, T. (2015), Approximation of mixed order Sobolev functions on the d-torus: Asymptotics, preasymptotics and d-dependence,
Constr. Approx.
42, 353–398.10.1007/s00365-015-9299-xCrossRefGoogle Scholar
Kulesza, A. and Taskar, B. (2012), Determinantal point processes for machine learning,
Found. Trends. Mach. Learn.
5, 123–286.10.1561/2200000044CrossRefGoogle Scholar
Kung, H. T. (1976), The complexity of obtaining starting points for solving operator equations by Newton’s method, in
Analytic Computational Complexity
(Traub, J. F., ed.), Academic Press, pp. 35–57.10.1016/B978-0-12-697560-4.50008-3CrossRefGoogle Scholar
Kunsch, R. J. (2016), Bernstein numbers and lower bounds for the Monte Carlo error, in
Monte Carlo and Quasi-Monte Carlo Methods
(Cools, R. and Nuyens, D., eds), Vol. 163 of Springer Proceedings in Mathematics & Statistics, Springer, pp. 471–488.10.1007/978-3-319-33507-0_24CrossRefGoogle Scholar
Kunsch, R. J. (2017), High-dimensional function approximation: Breaking the curse with Monte Carlo methods. PhD thesis. Available at arXiv:1704.08213.Google Scholar
Kunsch, R. J. and Wnuk, M. (2026), Uniform approximation of vectors using adaptive randomized information,
J. Approx. Theory
313, art. 106216.10.1016/j.jat.2025.106216CrossRefGoogle Scholar
Kunsch, R. J., Novak, E. and Wnuk, M. (2024), Randomized approximation of summable sequences: Adaptive and non-adaptive,
J. Approx. Theory
304, art. 106056.10.1016/j.jat.2024.106056CrossRefGoogle Scholar
Kuo, F. Y., Schwab, C. and Sloan, I. H. (2012), Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients,
SIAM J. Numer. Anal.
50, 3351–3374.10.1137/110845537CrossRefGoogle Scholar
Kuo, F. Y., Sloan, I. H., Wasilkowski, G. W. and Woźniakowski, H. (2010), Liberating the dimension,
J. Complexity
26, 422–454.10.1016/j.jco.2009.12.003CrossRefGoogle Scholar
Kuo, F. Y., Wasilkowski, G. W. and Woźniakowski, H. (2008), Multivariate L ∞ approximation in the worst case setting over reproducing kernel Hilbert spaces,
J. Approx. Theory
152, 135–160.10.1016/j.jat.2007.11.006CrossRefGoogle Scholar
Kuo, F. Y., Wasilkowski, G. W. and Woźniakowski, H. (2009a), Lattice algorithms for multivariate L ∞ approximation in the worst-case setting,
Constr. Approx.
30, 475–493.10.1007/s00365-009-9075-xCrossRefGoogle Scholar
Kuo, F. Y., Wasilkowski, G. W. and Woźniakowski, H. (2009b), On the power of standard information for multivariate approximation in the worst case setting,
J. Approx. Theory
158, 97–125.10.1016/j.jat.2008.01.011CrossRefGoogle Scholar
Lang, J. and Edmunds, D. (2011),
Eigenvalues, Embeddings and Generalised Trigonometric Functions
, Vol. 2016 of Lecture Notes in Mathematics, Springer.10.1007/978-3-642-18429-1CrossRefGoogle Scholar
Lavancier, F., Møller, J. and Rubak, E. (2014), Determinantal point process models and statistical inference,
J. R. Statist. Soc. Ser. B Statist. Methodol.
77, 853–877.10.1111/rssb.12096CrossRefGoogle Scholar
Limonova, I. and Temlyakov, V. (2022), On sampling discretization in L 2,
J. Math. Anal. Appl.
515, art. 126457.10.1016/j.jmaa.2022.126457CrossRefGoogle Scholar
Limonova, I. V., Malykhin, Y. V. and Temlyakov, V. N. (2024), One-sided discretization inequalities and sampling recovery,
Russ. Math. Surv.
79, 515–545.10.4213/rm10175eCrossRefGoogle Scholar
Lorentz, G. G., von Golitschek, M. and Makovoz, Y. (1996),
Constructive Approximation: Advanced Problems
, Vol. 304 of Grundlehren der Mathematischen Wissenschaften, Springer.
10.1007/978-3-642-60932-9CrossRefGoogle Scholar
Ma, P., Mahoney, M. W. and Yu, B. (2015), A statistical perspective on algorithmic leveraging,
J. Mach. Learn. Res.
16, 861–911.Google Scholar
Malykhin, Y., Ryutin, K. and Zaitseva, T. (2022), Recovery of regular ridge functions on the ball,
Constr. Approx.
56, 687–708.10.1007/s00365-022-09568-3CrossRefGoogle Scholar
Malykhin, Y. V. (2025), Kolmogorov widths of the class
${W}_1^1$
,
Math. Notes
117, 1034–1039.10.1134/S000143462560293XCrossRefGoogle Scholar
,
Math. Notes
117, 1034–1039.10.1134/S000143462560293XCrossRefGoogle ScholarMarcus, A., Spielman, D. and Srivastava, N. (2015), Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem,
Ann. of Math. (2)
182, 327–350.10.4007/annals.2015.182.1.8CrossRefGoogle Scholar
Mathé, P. (1990), s-numbers in information-based complexity,
J. Complexity
6, 41–66.10.1016/0885-064X(90)90011-2CrossRefGoogle Scholar
Mathé, P. (1991), Random approximation of Sobolev embeddings,
J. Complexity
7, 261–281.10.1016/0885-064X(91)90036-WCrossRefGoogle Scholar
Mayer, S., Ullrich, T. and Vybíral, J. (2015), Entropy and sampling numbers of classes of ridge functions,
Constr. Approx.
42, 231–264.10.1007/s00365-014-9267-xCrossRefGoogle Scholar
Maz’ya, V. G. (1985),
Sobolev Spaces
, Springer Series in Soviet Mathematics, Springer.10.1007/978-3-662-09922-3CrossRefGoogle Scholar
Mendelson, S. and Pajor, A. (2006), On singular values of matrices with independent rows,
Bernoulli
12, 761–773.10.3150/bj/1161614945CrossRefGoogle Scholar
Mhaskar, H. N. (2010), Eignets for function approximation on manifolds,
Appl. Comput. Harm. Anal.
29, 63–87.10.1016/j.acha.2009.08.006CrossRefGoogle Scholar
Micchelli, C. A. and Rivlin, T. J. (1978), A survey of optimal recovery, in
Optimal Estimation in Approximation Theory
, The IBM Research Symposia Series, Springer, pp. 1–54.Google Scholar
Migliorati, G. (2021), Multivariate approximation of functions on irregular domains by weighted least-squares methods,
IMA J. Numer. Anal.
41, 1293–1317.10.1093/imanum/draa023CrossRefGoogle Scholar
Migliorati, G., Nobile, F., von Schwerin, E. and Tempone, R. (2014), Analysis of discrete L 2 projection on polynomial spaces with random evaluations,
Found. Comput. Math.
14, 419–456.Google Scholar
Mityagin, B. S. (1962), Approximation of functions in Lp and C on the torus,
Math. Notes
58, 397–414.Google Scholar
Mityagin, B. S. and Henkin, G. M. (1963), Inequalities between n-diameters,
Proc. Voronezh Seminar on Functional Analysis
7, 97–103.Google Scholar
Moeller, M., Neumayer, S., Pozharska, K., Sommerfeld, T. and Ullrich, T. (2025a), High-dimensional sparse recovery from function samples: Decoders, guarantees and instance optimality. Available at arXiv:2503.16209v2.Google Scholar
Moeller, M., Stasyuk, S. and Ullrich, T. (2025b), Best m-term trigonometric approximation in weighted Wiener spaces and applications. Available at arXiv:2508.07336.10.1007/s43036-025-00480-8CrossRefGoogle Scholar
Nagel, N., Schäfer, M. and Ullrich, T. (2022), A new upper bound for sampling numbers,
Found. Comput. Math.
22, 445–468.10.1007/s10208-021-09504-0CrossRefGoogle Scholar
Narcowich, F. J., Ward, J. D. and Wendland, H. (2005), Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting,
Math. Comp.
74, 743–763.10.1090/S0025-5718-04-01708-9CrossRefGoogle Scholar
Nevai, P. (1986), Géza Freud, orthogonal polynomials and Christoffel functions. A case study,
J. Approx. Theory
48, 3–167.10.1016/0021-9045(86)90016-XCrossRefGoogle Scholar
Nguyen, D. H., Zellinger, W. and Pereverzyev, S. (2024), On regularized Radon–Nikodym differentiation,
J. Mach. Learn. Res.
25, 1–24.Google Scholar
Nitzan, S., Olevskii, A. and Ulanovskii, A. (2013), A few remarks on sampling of signals with small spectrum,
Proc. Steklov Inst. Math.
280, 240–247.10.1134/S0081543813010173CrossRefGoogle Scholar
Nitzan, S., Olevskii, A. and Ulanovskii, A. (2016), Exponential frames on unbounded sets,
Proc. Amer. Math. Soc.
144, 109–118.10.1090/proc/12868CrossRefGoogle Scholar
Niu, B., Hickernell, F. J., Müller-Gronbach, T. and Ritter, K. (2011), Deterministic multi-level algorithms for infinite-dimensional integration on ℝℕ,
J. Complexity
27, 331–351.10.1016/j.jco.2010.08.001CrossRefGoogle Scholar
Nouy, A. and Michel, B. (2025), Weighted least-squares approximation with determinantal point processes and generalized volume sampling,
SMAI J. Comput. Math.
11, 1–36.10.5802/smai-jcm.117CrossRefGoogle Scholar
Novak, E. (1988),
Deterministic and Stochastic Error Bounds in Numerical Analysis
, Vol. 1349 of Lecture Notes in Mathematics, Springer.10.1007/BFb0079792CrossRefGoogle Scholar
Novak, E. (1992), Optimal linear randomized methods for linear operators in Hilbert spaces,
J. Complexity
8, 22–36.10.1016/0885-064X(92)90032-7CrossRefGoogle Scholar
Novak, E. (1995a), The adaptation problem for nonsymmetric convex sets,
J. Approx. Theory
82, 123–134.10.1006/jath.1995.1071CrossRefGoogle Scholar
Novak, E. (1995b), Optimal recovery and n-widths for convex classes of functions,
J. Approx. Theory
80, 390–408.10.1006/jath.1995.1025CrossRefGoogle Scholar
Novak, E. (1995c), The real number model in numerical analysis,
J. Complexity
11, 57–73.10.1006/jcom.1995.1002CrossRefGoogle Scholar
Novak, E. (1996), On the power of adaption,
J. Complexity
12, 199–237.10.1006/jcom.1996.0015CrossRefGoogle Scholar
Novak, E. (1999), Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials,
J. Complexity
15, 299–316.10.1006/jcom.1999.0507CrossRefGoogle Scholar
Novak, E. (2024), Optimal algorithms for numerical integration: Recent results and open problems, in
Monte Carlo and Quasi-Monte Carlo Methods (MCQMC 2022)
(Hinrichs, A. et al., eds), Vol. 460 of Springer Proceedings in Mathematics & Statistics, Springer, pp. 105–131.10.1007/978-3-031-59762-6_5CrossRefGoogle Scholar
Novak, E. and Pillichshammer, F. (2025), The Lp-discrepancy for finite p > 1 suffers from the curse of dimensionality,
Proc. Amer. Math. Soc.
153, 1447–1459.10.1090/proc/17100CrossRefGoogle Scholar
Novak, E. and Ritter, K. (1989), A stochastic analog to Chebyshev centers and optimal average case algorithms,
J. Complexity
5, 60–79.10.1016/0885-064X(89)90013-7CrossRefGoogle Scholar
Novak, E. and Rudolf, D. (2016), Tractability of the approximation of high-dimensional rank one tensors,
Constr. Approx.
43, 1–13.10.1007/s00365-015-9282-6CrossRefGoogle Scholar
Novak, E. and Triebel, H. (2006), Function spaces in Lipschitz domains and optimal rates of convergence for sampling,
Constr. Approx.
23, 325–350.10.1007/s00365-005-0612-yCrossRefGoogle Scholar
Novak, E. and Woźniakowski, H. (2001), Intractability results for integration and discrepancy,
J. Complexity
17, 388–441.10.1006/jcom.2000.0577CrossRefGoogle Scholar
Novak, E. and Woźniakowski, H. (2008),
Tractability of Multivariate Problems
, Vol. I, Linear Information, Vol. 6 of EMS Tracts in Mathematics, European Mathematical Society (EMS).10.4171/026CrossRefGoogle Scholar
Novak, E. and Woźniakowski, H. (2009), Approximation of infinitely differentiable multivariate functions is intractable,
J. Complexity
25, 398–404.10.1016/j.jco.2008.11.002CrossRefGoogle Scholar
Novak, E. and Woźniakowski, H. (2010),
Tractability of Multivariate Problems
, Vol. II, Standard Information for Functionals, Vol. 12 of EMS Tracts in Mathematics, European Mathematical Society (EMS).Google Scholar
Novak, E. and Woźniakowski, H. (2012),
Tractability of Multivariate Problems
, Vol. III, Standard Information for Operators, Vol. 18 of EMS Tracts in Mathematics, European Mathematical Society (EMS).10.4171/116CrossRefGoogle Scholar
Novak, E. and Woźniakowski, H. (2016), Tractability of multivariate problems for standard and linear information in the worst case setting I,
J. Approx. Theory
207, 177–192.10.1016/j.jat.2016.02.017CrossRefGoogle Scholar
Novak, E., Sloan, I. H. and Woźniakowski, H. (2004), Tractability of approximation for weighted Korobov spaces on classical and quantum computers,
Found. Comput. Math.
4, 121–156.10.1007/s10208-002-0074-6CrossRefGoogle Scholar
Nuyens, D., Suryanarayana, G. and Weimar, M. (2016), Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions: Error bounds and tractability,
Adv. Comput. Math.
42, 55–84.10.1007/s10444-015-9411-6CrossRefGoogle Scholar
Osipenko, K. Y. and Parfenov, O. G. (1995), Ismagilov type theorems for linear, Gel’fand and Bernstein n-widths,
J. Complexity
11, 474–492.10.1006/jcom.1995.1025CrossRefGoogle Scholar
Petersen, H. B. and Jung, P. (2022), Robust instance-optimal recovery of sparse signals at unknown noise levels,
Inf. Inference
11, 845–887.Google Scholar
Petrova, G. and Wojtaszczyk, P. (2023), Lipschitz widths,
Constr. Approx.
57, 759–805.10.1007/s00365-022-09576-3CrossRefGoogle Scholar
Pietsch, A. (1974), s-numbers of operators in Banach spaces,
Studia Math.
51, 201–223.10.4064/sm-51-3-201-223CrossRefGoogle Scholar
Pietsch, A. (1978),
Operator Ideals
, Vol. 16 of Mathematische Monographien, Deutscher Verlag der Wissenschaften.Google Scholar
Pietsch, A. (1980), Weyl numbers and eigenvalues of operators in Banach spaces,
Math. Ann.
247, 149–168.10.1007/BF01364141CrossRefGoogle Scholar
Pietsch, A. (1987),
Eigenvalues and s-Numbers
, Vol. 13 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
Pietsch, A. (2008), Bad properties of the Bernstein numbers,
Stud. Math.
184, 263–269.10.4064/sm184-3-5CrossRefGoogle Scholar
Pietsch, A. (2009), Long-standing open problems of Banach space theory: My personal top ten,
Quaest. Math.
32, 321–337.10.2989/QM.2009.32.3.4.905CrossRefGoogle Scholar
Pinkus, A. (1985),
n-Widths in Approximation Theory
, Vol. 7 of Ergebnisse der Mathematik und ihrer Grenzgebiete / A Series of Modern Surveys in Mathematics, Springer.10.1007/978-3-642-69894-1CrossRefGoogle Scholar
Plaskota, L. (1996),
Noisy Information and Computational Complexity
, Cambridge University Press.10.1017/CBO9780511600814CrossRefGoogle Scholar
Plaskota, L. and Wasilkowski, G. W. (2011), Tractability of infinite-dimensional integration in the worst case and randomized settings,
J. Complexity
27, 505–518.10.1016/j.jco.2011.01.006CrossRefGoogle Scholar
Plaskota, L., Siedlecki, P. and Woźniakowski, H. (2020), Absolute value information for IBC problems,
J. Complexity
56, art. 101427.10.1016/j.jco.2019.101427CrossRefGoogle Scholar
Pozharska, K. and Ullrich, T. (2022), A note on sampling recovery of multivariate functions in the uniform norm,
SIAM J. Numer. Anal.
60, 1363–1384.10.1137/21M1410580CrossRefGoogle Scholar
Rasmussen, C. E. and Williams, C. K. I. (2006),
Gaussian Processes for Machine Learning
, MIT Press.Google Scholar
Rauhut, H. and Ward, R. (2012), Sparse Legendre expansions via ℓ 1-minimization,
J. Approx. Theory
164, 517–533.10.1016/j.jat.2012.01.008CrossRefGoogle Scholar
Rauhut, H. and Ward, R. (2016), Interpolation via weighted ℓ 1 minimization,
Appl. Comput. Harmon. Anal.
40, 321–351.10.1016/j.acha.2015.02.003CrossRefGoogle Scholar
Reimer, M. (2003),
Multivariate Polynomial Approximation
, Vol. 144 of International Series of Numerical Mathematics, Birkhäuser.10.1007/978-3-0348-8095-4CrossRefGoogle Scholar
Rieger, C. and Zwicknagl, B. (2010), Sampling inequalities for infinitely smooth functions, with applications to interpolation and machine learning,
Adv. Comput. Math.
32, 103–129.10.1007/s10444-008-9089-0CrossRefGoogle Scholar
Rivlin, T. J. (1974), The Lebesgue constants for polynomial interpolation, in
Functional Analysis and its Applications
(Garnir, H. G. et al., eds), Springer, pp. 422–437.10.1007/BFb0063594CrossRefGoogle Scholar
Rudelson, M. and Vershynin, R. (2008), On sparse reconstruction from Fourier and Gaussian measurements,
Commun. Pure Appl. Math.
61, 1025–1045.10.1002/cpa.20227CrossRefGoogle Scholar
Schmidt, E. (1907), On the theory of linear and nonlinear integral equations, I: Expansion of arbitrary functions by fixed function systems, II: Solution of the general linear integral equation,
Math. Ann.
63, 433–476.10.1007/BF01449770CrossRefGoogle Scholar
Schumaker, L. L. (1981),
Spline Functions: Basic Theory
, Pure & Applied Mathematics, Wiley-Interscience.Google Scholar
Scott, J. and Tůma, M. (2025), Sparse linear least-squares problems,
Acta Numer.
34, 891–1010.10.1017/S0962492924000059CrossRefGoogle Scholar
Shimodaira, H. (2000), Improving predictive inference under covariate shift by weighting the log-likelihood function,
J. Statist. Plann. Inference
90, 227–244.10.1016/S0378-3758(00)00115-4CrossRefGoogle Scholar
Sickel, W. and Ullrich, T. (2007), Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness,
East J. Approx.
13, 387–425.Google Scholar
Sloan, I. H. (1995), Polynomial interpolation and hyperinterpolation over general regions,
J. Approx. Theory
83, 238–254.10.1006/jath.1995.1119CrossRefGoogle Scholar
Sloan, I. H. and Woźniakowski, H. (1998), When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?,
J. Complexity
14, 1–33.10.1006/jcom.1997.0463CrossRefGoogle Scholar
Sloan, I. H. and Woźniakowski, H. (2018), Multivariate approximation for analytic functions with Gaussian kernels,
J. Complexity
45, 1–21.10.1016/j.jco.2017.11.001CrossRefGoogle Scholar
Sloan, I. H., Wang, X. and Woźniakowski, H. (2004), Finite-order weights imply tractability of multivariate integration,
J. Complexity
20, 46–74.10.1016/j.jco.2003.11.003CrossRefGoogle Scholar
Smolyak, S. A. (1963), Quadrature and interpolation formulas for tensor products of certain classes of functions,
Sov. Math. Dokl.
4, 240–243.Google Scholar
Solomjak, M. and Tichomirov, V. (1967), Some geometric characteristics of the embedding map from
${W}_p^a$
to C
,
Izv. Vysš. Učebn. Zaved Mat.
10, 76–82.Google Scholar
to C
,
Izv. Vysš. Učebn. Zaved Mat.
10, 76–82.Google ScholarSonnleitner, M. and Ullrich, M. (2023), On the power of iid information for linear approximation,
J. Appl. Numer. Anal.
1, 88–126.10.30970/ana.2023.1.88CrossRefGoogle Scholar
Steinwart, I. and Scovel, C. (2012), Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs,
Constr. Approx.
35, 363–417.10.1007/s00365-012-9153-3CrossRefGoogle Scholar
Stesin, M. L. (1975), Aleksandrov diameters of finite-dimensional sets and classes of smooth functions,
Sov. Math. Dokl.
16, 252–256.Google Scholar
Sukharev, A. G. (1978), Optimal method of constructing best uniform approximations for functions of a certain class,
USSR Comput. Math. Math. Phys.
18, 21–31.10.1016/0041-5553(78)90035-6CrossRefGoogle Scholar
Sukharev, A. G. (1979), Optimal numerical integration formulas for some classes of functions of several variables,
Dokl. Akad. Nauk
20, 472–475.Google Scholar
Szegő, G. (1975),
Orthogonal Polynomials
, fourth edition, American Mathematical Society.Google Scholar
Temlyakov, V. N. (1993), On approximate recovery of functions with bounded mixed derivative,
J. Complexity
9, 41–59.10.1006/jcom.1993.1004CrossRefGoogle Scholar
Temlyakov, V. N. (2018a), The Marcinkiewicz-type discretization theorems,
Constr. Approx.
48, 337–369.10.1007/s00365-018-9446-2CrossRefGoogle Scholar
Temlyakov, V. N. (2018b),
Multivariate Approximation
, Vol. 32 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press.10.1017/9781108689687CrossRefGoogle Scholar
Temlyakov, V. N. (2018c), Universal discretization,
J. Complexity
47, 97–109.10.1016/j.jco.2018.02.001CrossRefGoogle Scholar
Temlyakov, V. N. (2021), On optimal recovery in L 2,
J. Complexity
65, art. 101545.10.1016/j.jco.2020.101545CrossRefGoogle Scholar
Temlyakov, V. N. and Ullrich, T. (2021), Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness,
J. Complexity
67, art. 101575.10.1016/j.jco.2021.101575CrossRefGoogle Scholar
Temlyakov, V. N. and Ullrich, T. (2022), Approximation of functions with small mixed smoothness in the uniform norm,
J. Approx. Theory
277, art. 105718.10.1016/j.jat.2022.105718CrossRefGoogle Scholar
Tikhomirov, V. M. (1960), Diameters of sets in functional spaces and the theory of best approximations,
Russ. Math. Surv.
15, 75–111.10.1070/RM1960v015n03ABEH004093CrossRefGoogle Scholar
Tikhomirov, V. M. (1971), Some problems in approximation theory,
Math. Notes
9, 343–350.10.1007/BF01094364CrossRefGoogle Scholar
Tikhomirov, V. M. (1990),
Convex analysis, in Analysis II: Convex Analysis and Approximation Theory
(Gamkrelidze, R. V., ed.), Springer, pp. 1–92.Google Scholar
Traub, J. F. and Werschulz, A. G. (1998),
Complexity and Information
, Lezioni Lincee, Cambridge University Press.Google Scholar
Traub, J. F. and Woźniakowski, H. (1980),
A General Theory of Optimal Algorithms
, ACM Monograph Series, Academic Press.Google Scholar
Traub, J. F. and Woźniakowski, H. (1991), Information-based complexity: New questions for mathematicians,
Math. Intell.
13, 34–43.10.1007/BF03024085CrossRefGoogle Scholar
Traub, J. F. and Woźniakowski, H. (1992), Perspectives on information-based complexity,
Bull. Amer. Math. Soc. (N.S.)
26, 29–52.10.1090/S0273-0979-1992-00240-9CrossRefGoogle Scholar
Traub, J. F., Wasilkowski, G. and Woźniakowski, H. (1988),
Information-Based Complexity
, Academic Press.Google Scholar
Tropp, J. A. (2012), User-friendly tail bounds for sums of random matrices,
Found. Comput. Math.
12, 389–434.10.1007/s10208-011-9099-zCrossRefGoogle Scholar
Ullrich, M. (2020), On the worst-case error of least squares algorithms for L 2-approximation with high probability,
J. Complexity
60, art. 101484.10.1016/j.jco.2020.101484CrossRefGoogle Scholar
Ullrich, M. (2024), Inequalities between s-numbers,
Adv. Oper. Theory
9, art. 82.10.1007/s43036-024-00386-xCrossRefGoogle Scholar
Ullrich, M. (2026), Sampling and entropy numbers in the uniform norm,
J. Complexity
92, art. 101992.10.1016/j.jco.2025.101992CrossRefGoogle Scholar
Vybíral, J. (2007), Sampling numbers and function spaces,
J. Complexity
23, 773–792.10.1016/j.jco.2007.03.011CrossRefGoogle Scholar
Vybíral, J. (2008), Widths of embeddings in function spaces,
J. Complexity
24, 545–570.10.1016/j.jco.2008.01.002CrossRefGoogle Scholar
Vybíral, J. (2014), Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions,
J. Complexity
30, 48–55.10.1016/j.jco.2013.04.003CrossRefGoogle Scholar
Vybíral, J. (2020), A variant of Schur’s product theorem and its applications,
Adv. Math.
368, art. 107140.10.1016/j.aim.2020.107140CrossRefGoogle Scholar
Wainwright, M. J. (2019),
High-Dimensional Statistics: A Non-asymptotic Viewpoint
, Vol. 48 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press.Google Scholar
Wasilkowski, G. W. (1984), Some nonlinear problems are as easy as the approximation problem,
Comput. Math. Appl.
10, 351–363.10.1016/0898-1221(84)90063-4CrossRefGoogle Scholar
Wasilkowski, G. W. and Woźniakowski, H. (2001), On the power of standard information for weighted approximation,
Found. Comput. Math.
1, 417–434.10.1007/s102080010016CrossRefGoogle Scholar
Wasilkowski, G. W. and Woźniakowski, H. (2004), Finite-order weights imply tractability of linear multivariate problems,
J. Approx. Theory
130, 57–77.10.1016/j.jat.2004.06.011CrossRefGoogle Scholar
Wasilkowski, G. W. and Woźniakowski, H. (2007), The power of standard information for multivariate approximation in the randomized setting,
Math. Comp.
76, 965–988.10.1090/S0025-5718-06-01944-2CrossRefGoogle Scholar
Weimar, M. (2012a), The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces,
J. Approx. Theory
164, 1345–1368.10.1016/j.jat.2012.05.016CrossRefGoogle Scholar
Weimar, M. (2012b), Tractability results for weighted Banach spaces of smooth functions,
J. Complexity
28, 59–75.10.1016/j.jco.2011.03.004CrossRefGoogle Scholar
Wendland, H. (2005),
Scattered Data Approximation
, Vol. 17 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press.Google Scholar
Werschulz, A. G. (1991),
The Computational Complexity of Differential and Integral Equations: An Information-Based Approach
, Oxford Mathematical Monographs, Oxford University Press.10.1093/oso/9780198535898.001.0001CrossRefGoogle Scholar
Wojtaszczyk, O. (2003), Multivariate integration in C ∞([0, 1]d) is not strongly tractable,
J. Complexity
19, 638–643.10.1016/S0885-064X(03)00069-4CrossRefGoogle Scholar
Woźniakowski, H. (1999), Why does information-based complexity use the real number model?,
Theor. Comput. Sci.
219, 451–465.10.1016/S0304-3975(98)00300-4CrossRefGoogle Scholar
Woźniakowski, H. (2019), ABC on IBC,
J. Complexity
52, 2–23.10.1016/j.jco.2018.05.001CrossRefGoogle Scholar
Wu, Z. M. and Schaback, R. (1993), Local error estimates for radial basis function interpolation of scattered data,
IMA J. Numer. Anal.
13, 13–27.10.1093/imanum/13.1.13CrossRefGoogle Scholar
Xu, G. (2015), On weak tractability of the Smolyak algorithm for approximation problems,
J. Approx. Theory
192, 347–361.10.1016/j.jat.2014.10.016CrossRefGoogle Scholar
Xu, Y. and Narayan, A. (2023), Randomized weakly admissible meshes,
J. Approx. Theory
285, art. 105835.10.1016/j.jat.2022.105835CrossRefGoogle Scholar
Yao, A. C.-C. (1977), Probabilistic computations: Toward a unified measure of complexity, in
18th Annual Symposium on Foundations of Computer Science (SFCS 1977)
, pp. 222–227.10.1109/SFCS.1977.24CrossRefGoogle Scholar
Zellinger, W., Kindermann, S. and Pereverzyev, S. V. (2023), Adaptive learning of density ratios in RKHS,
J. Mach. Learn. Res.
24, 1–28.Google Scholar
You have
Access
Open access
- 3
- Cited by