Geodesic
One-sided discretization inequalities and sampling recovery
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 79 (2024) no. 3, pp. 515-545 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Recently, in a number of papers it was understood that results on sampling discretization and universal sampling discretization can successfully be used in the problem of sampling recovery. Moreover, it turns out that it is sufficient to only have a one-sided discretization inequality for some of these applications. This motivated us to write the present paper as a survey, which includes new results, with the focus on the one-sided discretization inequalities and their applications to sampling recovery. In this sense the paper complements the two existing survey papers on sampling discretization (Russian Math. Surveys, 74:4 (2019), 579–630 and J. Complexity, 71 (2022), 101653, 55 pp.). Bibliography: 50 titles.
Keywords: sampling discretization, Nikol'skii's inequality, recovery. 
@article{RM_2024_79_3_a2,
     author = {I. V. Limonova and Yu. V. Malykhin and V. N. Temlyakov},
     title = {One-sided discretization inequalities and sampling recovery},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {515--545},
     year = {2024},
     volume = {79},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2024_79_3_a2/}
}
TY  - JOUR
AU  - I. V. Limonova
AU  - Yu. V. Malykhin
AU  - V. N. Temlyakov
TI  - One-sided discretization inequalities and sampling recovery
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2024
SP  - 515
EP  - 545
VL  - 79
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/RM_2024_79_3_a2/
LA  - en
ID  - RM_2024_79_3_a2
ER  - 
%0 Journal Article
%A I. V. Limonova
%A Yu. V. Malykhin
%A V. N. Temlyakov
%T One-sided discretization inequalities and sampling recovery
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2024
%P 515-545
%V 79
%N 3
%U http://geodesic.mathdoc.fr/item/RM_2024_79_3_a2/
%G en
%F RM_2024_79_3_a2
I. V. Limonova; Yu. V. Malykhin; V. N. Temlyakov. One-sided discretization inequalities and sampling recovery. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 79 (2024) no. 3, pp. 515-545. http://geodesic.mathdoc.fr/item/RM_2024_79_3_a2/

[1] F. Bartel, M. Schäfer, and T. Ullrich, “Constructive subsampling of finite frames with applications in optimal function recovery”, Appl. Comput. Harmon. Anal., 65 (2023), 209–248 | DOI | MR | Zbl

[2] J. Bourgain and M. Lewko, “Sidonicity and variants of Kaczmarz's problem”, Ann. Inst. Fourier (Grenoble), 67:3 (2017), 1321–1352 | DOI | MR | Zbl

[3] M. Dolbeault and A. Cohen, “Optimal pointwise sampling for $L^2$ approximation”, J. Complexity, 68 (2022), 101602, 12 pp. | DOI | MR | Zbl

[4] A. Cohen and G. Migliorati, “Optimal weighted least-squares methods”, SMAI J. Comput. Math., 3 (2017), 181–203 | DOI | MR | Zbl

[5] F. Dai, E. Kosov, and V. Temlyakov, “Some improved bounds in sampling discretization of integral norms”, J. Funct. Anal., 285:4 (2023), 109951, 40 pp. ; (2022 (v2 – 2023)), 46 pp., arXiv: 2208.09762v1 | DOI | MR | Zbl

[6] F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, and S. Tikhonov, “Entropy numbers and Marcinkiewicz-type discretization”, J. Funct. Anal., 281:6 (2021), 109090, 25 pp. ; Entropy numbers and Marcinkiewicz-type discretization theorem, 2020, 27 pp., arXiv: 2001.10636v1 | DOI | MR | Zbl

[7] F. Dai, A. Prymak, V. N. Temlyakov, and S. Yu. Tikhonov, “Integral norm discretization and related problems”, Russian Math. Surveys, 74:4 (2019), 579–630 ; (2018 (v3 – 2019)), 51 pp., arXiv: 1807.01353v1 | DOI | MR | Zbl

[8] F. Dai and V. N. Temlyakov, “Sampling discretization of integral norms and its application”, Proc. Steklov Inst. Math., 319 (2022), 97–109 | DOI | MR | Zbl

[9] F. Dai and V. Temlyakov, Universal discretization and sparse sampling recovery, 2023, 40 pp., arXiv: 2301.05962

[10] F. Dai and V. Temlyakov, Lebesgue-type inequalities in sparse sampling recovery, 2023, 25 pp., arXiv: 2307.04161v1

[11] F. Dai and V. Temlyakov, “Random points are good for universal discretization”, J. Math. Anal. Appl., 529:1 (2024), 127570, 28 pp. ; (2023), 35 pp., arXiv: 2301.12536v2 | DOI | MR | Zbl

[12] Dinh Düng, “Reconstruction and one-sided approximation of periodic functions of several variables”, Soviet Math. Dokl., 42:1 (1991), 68–71 | MR | Zbl

[13] Dinh Dũng, V. Temlyakov, and T. Ullrich, Hyperbolic cross approximation, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer, Cham, 2018, xi+218 pp. ; 2016 (v3 – 2017), 182 pp., arXiv: 1601.03978v2 | DOI | MR | Zbl

[14] M. Dolbeault, D. Krieg, and M. Ullrich, “A sharp upper bound for sampling numbers in $L_2$”, Appl. Comput. Harmon. Anal., 63 (2023), 113–134 | DOI | MR | Zbl

[15] D. Freeman and D. Ghoreishi, “Discretizing $L_p$ norms and frame theory”, J. Math. Anal. Appl., 519:2 (2023), 126846, 17 pp. | DOI | MR | Zbl

[16] E. D. Gluskin, “Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces”, Math. USSR-Sb., 64:1 (1989), 85–96 | DOI | MR | Zbl

[17] T. Jahn, T. Ullrich, and F. Voigtlaender, “Sampling numbers of smoothness classes via $\ell^1$-minimization”, J. Complexity, 79 (2023), 101786, 35 pp. ; (2022 (v3 – 2023)), 26 pp., arXiv: 2212.00445v1 | DOI | MR | Zbl

[18] L. Kämmerer, T. Ullrich, and T. Volkmer, “Worst-case recovery guarantees for least squares approximation using random samples”, Constr. Approx., 54:2 (2021), 295–352 | DOI | MR | Zbl

[19] B. Kashin, S. Konyagin, and V. Temlyakov, “Sampling discretization of the uniform norm”, Constr. Approx., 57:2 (2023), 663–694 | DOI | MR | Zbl

[20] B. Kashin, E. Kosov, I. Limonova, and V. Temlyakov, “Sampling discretization and related problems”, J. Complexity, 71 (2022), 101653, 55 pp. | DOI | MR | Zbl

[21] B. S. Kashin and V. N. Temlyakov, “The volume estimates and their applications”, East J. Approx., 9:4 (2003), 469–485 | MR | Zbl

[22] J. Kiefer and J. Wolfowitz, “The equivalence of two extremum problems”, Canadian J. Math., 12 (1960), 363–366 | DOI | MR | Zbl

[23] E. Kosov and V. Temlyakov, “Sampling discretization of the uniform norm and applications”, J. Math. Anal. Appl., 538:2 (2024), 128431, 25 pp. ; (2024 (v1 – 2023)), 36 pp., arXiv: 2306.14207 | DOI | MR

[24] E. D. Kosov and V. N. Temlyakov, Bounds for the sampling discretization error and their applications to universal sampling discretization, 2024 (v1 – 2023), 36 pp., arXiv: 2312.05670v2

[25] D. Krieg, K. Pozharska, M. Ullrich, and T. Ullrich, Sampling recovery in $L_2$ and other norms, 2023, 32 pp., arXiv: 2305.07539v3

[26] D. Krieg, K. Pozharska, M. Ullrich, and T. Ullrich, Sampling projections in the uniform norm, 2024, 18 pp., arXiv: 2401.02220

[27] D. Krieg and M. Ullrich, “Function values are enough for $L_2$-approximation”, Found. Comput. Math., 21:4 (2021), 1141–1151 | DOI | MR | Zbl

[28] D. Krieg and M. Ullrich, “Function values are enough for $L_2$-approximation: Part II”, J. Complexity, 66 (2021), 101569, 14 pp. | DOI | MR | Zbl

[29] I. V. Limonova, “Exact discretization of the $L_2$-norm with negative weight”, Math. Notes, 110:3 (2021), 458–462 | DOI | MR | Zbl

[30] I. Limonova and V. Temlyakov, “On sampling discretization in $L_2$”, J. Math. Anal. Appl., 515:2 (2022), 126457, 14 pp. | DOI | MR | Zbl

[31] D. S. Lubinsky, “Marcinkiewicz–Zygmund inequalities: methods and results”, Recent progress in inequalities, Math. Appl., 430, Kluwer Acad. Publ., Dordrecht, 1998, 213–240 | DOI | MR | Zbl

[32] A. A. Lunin, “Operator norms of submatrices”, Math. Notes, 45:3 (1989), 248–252 | DOI | MR | Zbl

[33] A. W. Marcus, D. A. Spielman, and N. Srivastava, “Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem”, Ann. of Math. (2), 182:1 (2015), 327–350 | DOI | MR | Zbl

[34] N. Nagel, M. Schäfer, and T. Ullrich, “A new upper bound for sampling numbers”, Found. Comput. Math., 22:2 (2022), 445–468 | DOI | MR | Zbl

[35] E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Math., 1349, Springer-Verlag, Berlin, 1988, vi+113 pp. | DOI | MR | Zbl

[36] E. Novak and H. Woźniakowski, Tractability of multivariate problems, v. I, EMS Tracts Math., 6, Linear information, Eur. Math. Soc. (EMS), Zürich, 2008, xii+384 pp. | DOI | MR | Zbl

[37] E. Novak and H. Woźniakowski, Tractability of multivariate problems, v. II, EMS Tracts Math., 12, Standard information for functionals, Eur. Math. Soc. (EMS), Zürich, 2010, xviii+657 pp. | DOI | MR | Zbl

[38] E. Novak and H. Woźniakowski, Tractability of multivariate problems, v. III, EMS Tracts Math., 18, Standard information for operators, Eur. Math. Soc. (EMS), Zürich, 2012, xviii+586 pp. | DOI | MR | Zbl

[39] G. Pisier, “On uniformly bounded orthonormal Sidon systems”, Math. Res. Lett., 24:3 (2017), 893–932 | DOI | MR | Zbl

[40] K. Pozharska and T. Ullrich, “A note on sampling recovery of multivariate functions in the uniform norm”, SIAM J. Numer. Anal., 60:3 (2022), 1363–1384 | DOI | MR | Zbl

[41] V. N. Temlyakov, “On approximate recovery of functions with bounded mixed derivative”, J. Complexity, 9:1 (1993), 41–59 | DOI | MR | Zbl

[42] V. N. Temlyakov, “The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials”, Jaen J. Approx., 9:1 (2017), 37–63 | MR | Zbl

[43] V. N. Temlyakov, “The Marcinkiewicz-type discretization theorems”, Constr. Approx., 48:2 (2018), 337–369 | DOI | MR | Zbl

[44] V. Temlyakov, Multivariate approximation, Cambridge Monogr. Appl. Comput. Math., 32, Cambridge Univ. Press, Cambridge, 2018, xvi+534 pp. | DOI | MR | Zbl

[45] V. Temlyakov, “On optimal recovery in $L_2$”, J. Complexity, 65 (2021), 101545, 11 pp. | DOI | MR | Zbl

[46] V. N. Temlyakov, “On universal sampling recovery in the uniform norm”, Proc. Steklov Inst. Math., 323 (2023), 206–216 | DOI | MR | Zbl

[47] V. Temlyakov, Sparse sampling recovery in integral norms on some function classes, 2024, 25 pp., arXiv: 2401.14670

[48] V. Temlyakov and T. Ullrich, “Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness”, J. Complexity, 67 (2021), 101575, 19 pp. | DOI | MR | Zbl

[49] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Comput. Sci. Sci. Comput., Academic Press, Inc., Boston, MA, 1988, xiv+523 pp. | MR | Zbl

[50] A. Zygmund, Trigonometric series, v. I, 2nd ed., Cambridge Univ. Press, New York, 1959, xii+383 pp. | MR | Zbl