Geodesic
Sparse sampling recovery in integral norms on some function classes
Sbornik. Mathematics, Tome 215 (2024) no. 10, pp. 1406-1425 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper is a direct followup of a recent paper of the author. We continue to analyze approximation and recovery properties with respect to systems satisfying the universal sampling discretization property and a special unconditionality property. In addition, we assume that the subspace spanned by our system satisfies some Nikol'skii-type inequalities. We concentrate on recovery with an error measured in the $L_p$-norm for $2\le p<\infty$. We apply a powerful nonlinear approximation method — the Weak Orthogonal Matching Pursuit (WOMP), also known under the name of the Weak Orthogonal Greedy Algorithm (WOGA). We establish that the WOMP based on good points for $L_2$-universal discretization provides good recovery in the $L_p$-norm for $2\le p<\infty$. For our recovery algorithms we obtain both Lebesgue-type inequalities for individual functions and error bounds for special classes of multivariate functions. We combine two deep and powerful techniques — Lebesgue-type inequalities for the WOMP and the theory of universal sampling discretization — in order to obtain new results on sampling recovery. Bibliography: 19 titles.
Keywords: sampling discretization, universality, recovery. 
@article{SM_2024_215_10_a4,
     author = {V. N. Temlyakov},
     title = {Sparse sampling recovery in integral norms on some function classes},
     journal = {Sbornik. Mathematics},
     pages = {1406--1425},
     year = {2024},
     volume = {215},
     number = {10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2024_215_10_a4/}
}
TY  - JOUR
AU  - V. N. Temlyakov
TI  - Sparse sampling recovery in integral norms on some function classes
JO  - Sbornik. Mathematics
PY  - 2024
SP  - 1406
EP  - 1425
VL  - 215
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/SM_2024_215_10_a4/
LA  - en
ID  - SM_2024_215_10_a4
ER  - 
%0 Journal Article
%A V. N. Temlyakov
%T Sparse sampling recovery in integral norms on some function classes
%J Sbornik. Mathematics
%D 2024
%P 1406-1425
%V 215
%N 10
%U http://geodesic.mathdoc.fr/item/SM_2024_215_10_a4/
%G en
%F SM_2024_215_10_a4
V. N. Temlyakov. Sparse sampling recovery in integral norms on some function classes. Sbornik. Mathematics, Tome 215 (2024) no. 10, pp. 1406-1425. http://geodesic.mathdoc.fr/item/SM_2024_215_10_a4/

[1] J. Bourgain, “An improved estimate in the restricted isometry problem”, Geometric aspects of functional analysis, Lecture Notes in Math., 2116, Springer, Cham, 2014, 65–70 | DOI | MR | Zbl

[2] 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 | DOI | MR | Zbl

[3] F. Dai and V. Temlyakov, “Universal sampling discretization”, Constr. Approx., 58:3 (2023), 589–613 | DOI | MR | Zbl

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

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

[6] R. A. DeVore and V. N. Temlyakov, “Some remarks on greedy algorithms”, Adv. Comput. Math., 5:2–3 (1996), 173–187 | DOI | MR | Zbl

[7] Dinh Dũng, V. Temlyakov and T. Ullrich, Hyperbolic cross approximation, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer, Cham, 2018, xi+218 pp. | DOI | MR | Zbl

[8] I. Haviv and O. Regev, “The restricted isometry property of subsampled Fourier matrices”, Geometric aspects of functional analysis, Lecture Notes in Math., 2169, Springer, Cham, 2017, 163–179 | DOI | MR | Zbl

[9] T. Jahn, T. Ullrich and F. Voigtlaender, Sampling numbers of smoothness classes via $\ell^1$-minimization, arXiv: 2212.00445v1

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

[11] E. D. Livshitz and V. N. Temlyakov, “Sparse approximation and recovery by greedy algorithms”, IEEE Trans. Inform. Theory, 60:7 (2014), 3989–4000 ; arXiv: 1303.3595v1 | DOI | MR | Zbl

[12] G. Pisier, “Remarques sur un résultat non publié de B. Maurey”, Seminaire d'analyse fonctionalle, Exp. No. V, v. 1980–1981, École Polytechnique, Centre de Mathématiques, Palaiseau, 1981, 12 pp. | MR | Zbl

[13] S. B. Stechkin, “On absolute convergence of orthogonal series”, Dokl. Akad. Nauk SSSR, 102 (1955), 37–40 (Russian) | MR | Zbl

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

[15] V. Temlyakov, Greedy approximation, Cambridge Monogr. Appl. Comput. Math., 20, Cambridge Univ. Press, Cambridge, 2011, xiv+418 pp. | DOI | MR | Zbl

[16] V. N. Temlyakov, “Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness”, Sb. Math., 206:11 (2015), 1628–1656 ; arXiv: 1412.8647v1 | DOI | MR | Zbl

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

[18] V. Temlyakov, Sparse sampling recovery by greedy algorithms, arXiv: 2312.13163v2

[19] 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