Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness

V. N. Temlyakov

Sbornik. Mathematics, Tome 206 (2015) no. 11, pp. 1628-1656

Résumé

Our main interest in this paper is to study some approximation problems for classes of functions with mixed smoothness. We use a technique based on a combination of results from hyperbolic cross approximation, which were obtained in 1980s–1990s, and recent results on greedy approximation to obtain sharp estimates for best $m$-term approximation with respect to the trigonometric system. We give some observations on the numerical integration and approximate recovery of functions with mixed smoothness. We prove lower bounds, which show that one cannot improve the accuracy of sparse grids methods with $\asymp 2^nn^{d-1}$ points in the grid by adding $2^n$ arbitrary points. In the case of numerical integration these lower bounds provide the best available lower bounds for optimal cubature formulae and for sparse grids based cubature formulae. Bibliography: 31 titles.

Détail

Keywords: nonlinear approximation, sparse approximation, trigonometric system, constructive methods.

Bibliographie

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

[2] V. N. Temlyakov, “Greedy algorithms in Banach spaces”, Adv. Comput. Math., 14:3 (2001), 277–292 | DOI | MR | Zbl

[3] V. N. Temlyakov, “Weak greedy algorithms”, Adv. Comput. Math., 12:2-3 (2000), 213–227 | DOI | MR | Zbl

[4] V. N. Temlyakov, “Sparse approximation and recovery by greedy algorithms in Banach spaces”, Forum Math. Sigma, 2 (2014), e12, 26 pp. ; IMI preprint 2013:09, 2013, 27 pp.; 2013, arXiv: 1303.6811v1 | DOI | MR | Zbl

[5] S. B. Stechkin, “Ob absolyutnoi skhodimosti ortogonalnykh ryadov”, Dokl. AN SSSR, 102 (1955), 37–40 | MR | Zbl

[6] R. S. Ismagilov, “Diameters of sets in normed linear spaces and the approximation of functions by trigonometric polynomials”, Russian Math. Surveys, 29:3 (1974), 169–186 | DOI | MR | Zbl

[7] V. E. Maiorov, “Trigonometric diameters of the Sobolev classes $W^r_p$ in the space $L_q$”, Math. Notes, 40:2 (1986), 590–597 | DOI | MR | Zbl

[8] R. A. DeVore, V. N. Temlyakov, “Nonlinear approximation by trigonometric sums”, J. Fourier Anal. Appl., 2:1 (1995), 29–48 | DOI | MR | Zbl

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

[10] Y. Makovoz, “On trigonometric $n$-widths and their generalization”, J. Approx. Theory, 41:4 (1984), 361–366 | DOI | MR | Zbl

[11] È. S. Belinskii, “Approximation by a “floating” system of exponentials on classes of smooth periodic functions”, Math. USSR-Sb., 60:1 (1988), 19–27 | DOI | MR | Zbl

[12] E. S. Belinskii, “Decomposition theorems and approximation by a “floating” system of exponentials”, Trans. Amer. Math. Soc., 350:1 (1998), 43–53 | DOI | MR | Zbl

[13] V. N. Temlyakov, “Approximation of periodic functions of several variables by bilinear forms”, Math. USSR-Izv., 28:1 (1987), 133–150 | DOI | MR | Zbl

[14] B. S. Kashin, V. N. Temlyakov, “On best $m$-term approximations and the entropy of sets in the space $L^1$”, Math. Notes, 56:5 (1994), 1137–1157 | DOI | MR | Zbl

[15] V. N. Temlyakov, “Nonlinear Kolmogorov widths”, Math. Notes, 63:6 (1998), 785–795 | DOI | DOI | MR | Zbl

[16] V. N. Temlyakov, “An inequality for the entropy numbers and its application”, J. Approx. Theory, 173 (2013), 110–121 | DOI | MR | Zbl

[17] S. J. Dilworth, D. Kutzarova, V. N. Temlyakov, “Convergence of some greedy algorithms in Banach spaces”, J. Fourier Anal. Appl., 8:5 (2002), 489–505 | DOI | MR | Zbl

[18] V. N. Temlyakov, “Greedy-type approximation in Banach spaces and applications”, Constr. Approx., 21:2 (2005), 257–292 | DOI | MR | Zbl

[19] A. S. Romanyuk, “Best $M$-term trigonometric approximations of Besov classes of periodic functions of several variables”, Izv. Math., 67:2 (2003), 265–302 | DOI | DOI | MR | Zbl

[20] V. N. Temlyakov, “Approximation of functions with a bounded mixed derivative”, Proc. Steklov Inst. Math., 178 (1989), 1–121 | MR | Zbl

[21] V. N. Temlyakov, Approximation of periodic functions, Comput. Math. Anal. Ser., Nova Sci. Publ., Commack, NY, 1993, x+419 pp. | MR | Zbl

[22] V. N. Temlyakov, “Estimates of the asymptotic characteristics of classes of functions with bounded mixed derivative or difference”, Proc. Steklov Inst. Math., 189 (1990), 161–197 | MR | Zbl

[23] M. J. Donahue, C. Darken, L. Gurvits, E. Sontag, “Rate of convex approximation in non-Hilbert spaces”, Constr. Approx., 13:2 (1997), 187–220 | DOI | MR | Zbl

[24] E. S. Belinskii, “Approximation of functions of several variables by trigonometric polynomials with given number of harmonics, and estimates of $\varepsilon$-entropy”, Anal. Math., 15:2 (1989), 67–74 | DOI | MR | Zbl

[25] V. N. Temlyakov, “An inequality for trigonometric polynomials and its application for estimating the entropy numbers”, J. Complexity, 11:2 (1995), 293–307 | DOI | MR | Zbl

[26] V. N. Temlyakov, “Cubature formulas, discrepancy, and nonlinear approximation”, J. Complexity, 19:3 (2003), 352–391 | DOI | MR | Zbl

[27] V. N. Temlyakov, “On a way of obtaining lower estimates for the errors of quadrature formulas”, Math. USSR-Sb., 71:1 (1992), 247–257 | DOI | MR | Zbl

[28] Dinh Dũng, T. Ullrich, “Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square”, Math. Nachr., 288:7 (2015), 743–762 | DOI | MR | Zbl

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

[30] V. N. Temlyakov, “Approximate recovery of periodic functions of several variables”, Math. USSR-Sb., 56:1 (1987), 249–261 | DOI | MR | Zbl

[31] V. N. Temlyakov, “An inequality for trigonometric polynomials and its application for estimating the Kolmogorov widths”, East J. Approx., 2:2 (1996), 253–262 | MR | Zbl