We study the efficiency of the approximation of the functions from the Besov space $ B_{p\theta}^\Omega(\mathbf{T}^d) $ in the norm of $ L_q(\mathbf{T}^d) $ by various random methods. We determine the exact asymptotic orders of Kolmogorov widths, linear widths, and Gel'fand widths of the unit ball of $ B_{p\theta}^\Omega(\mathbf{T}^d) $ in $ L_q(\mathbf{T}^d) $. Our results show that the convergence rates of the randomized linear and Gel'fand methods are faster than the deterministic counterparts in some cases. The maximal improvement can reach a factor $ n^{-1/2} $ roughly.
Citation: |
[1] | T. I. Amanov, Representation and imbedding theorems for the function spaces $S_{p, \theta}^rB(\mathbf{R}_n), $ $S_{p, \theta}^{*r}B(0\leq x_j\leq2\pi, \, j = 1, \ldots, n)$, Trudy Mat. Inst. Akad. Nauk SSSR, 77 (1965), 5-34. |
[2] | P. Binev, A. Cohen, W. Dahmen and R. DeVore, Universal algorithms for learning theory. II. Piecewise polynomial functions, Constr. Approx., 26 (2007), 127-152. doi: 10.1007/s00365-006-0658-z. |
[3] | P. Binev, A. Cohen, W. Dahmen and R. DeVore, Classification algorithms using adaptive partitioning, Ann. Statist., 42 (2014), 2141-2163. doi: 10.1214/14-AOS1234. |
[4] | P. Binev, A. Cohen, W. Dahmen, R. DeVore and V. Temlyakov, Universal algorithms for learning theory. I. Piecewise constant functions, J. Mach. Learn. Res., 6 (2005), 1297-1321. |
[5] | G. Byrenheid, R. J. Kunsch and V. K. Nguyen, Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness, J. Complexity, 46 (2018), 90-102. doi: 10.1016/j.jco.2017.12.002. |
[6] | A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and $k$-term approximation, J. Amer. Math. Soc., 22 (2009), 211-231. doi: 10.1090/S0894-0347-08-00610-3. |
[7] | R. DeVore, G. Kerkyacharian, D. Picard and V. Temlyakov, Approximations methods for supervised learning, Found. Comput. Math., 6 (2006), 3-58. doi: 10.1007/s10208-004-0158-6. |
[8] | D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582. |
[9] | D. L. Donoho, I. M. Johnstone, G. Kerdyacharian and D. Picard, Density estimation by wavelet thresholding, Ann. Statist., 24 (1996), 508-539. doi: 10.1214/aos/1032894451. |
[10] | G. S. Fang and L. Q. Duan, The complexity of function approximation on Sobolev spaces with bounded mixed derivative by the linear Monte Carlo methods, J. Complexity, 24 (2008), 398-409. doi: 10.1016/j.jco.2007.11.001. |
[11] | G. S. Fang and P. X. Ye, Integration error for multivariate functions from anisotropic classes, J. Complexity, 19 (2003), 610-627. doi: 10.1016/S0885-064X(03)00012-8. |
[12] | G. S. Fang and P. X. Ye, Computational complexity in worst, stochastic and average case setting on functional approximation problem of multivariate, Acta Math. Sci., 25 (2005), 439-448. doi: 10.1016/S0252-9602(05)60007-0. |
[13] | O. V. Fedunyk, Linear widths of the classes $B_{p, \theta}^\Omega$ of periodic functions of many variables in the space $L_q$, Ukr. Math. J., 58 (2006), 103-117. doi: 10.1007/s11253-006-0053-1. |
[14] | E. M. Galeev, Kolmogorov widths of classes of periodic functions of many variables $\tilde{W}_p^\alpha$ and $\tilde{H}_p^\alpha$ in the space $L_q$, Izv. Akad. Nauk SSSR Ser. Mat., 49 (1985), 916-934. |
[15] | S. Heinrich, Lower bounds for the complexity of Monte Carlo function approximation, J. Complexity, 8 (1992), 277-300. doi: 10.1016/0885-064X(92)90027-9. |
[16] | S. Heinrich, Random approximation in numerical analysis, in Functional Analysis: Proceedings of the Essen Conference, Lect. Notes in Pure and Appl. Math., (eds. K. D. Bierstedt, J. Bonet and J. Horvath, et al.), Boca Raton: Chapman and Hall/CRC, Vol. 150, (1994), 123–171. |
[17] | N. Korneichuk, Exact Constants in Approximation Theory, Cambridge Univesity Press, Cambridge, 1991. doi: 10.1017/CBO9781107325791. |
[18] | Y. M. Liu and H. Y. Wang, Convergence order of wavelet thresholding estimator for differential operators on Besov spaces, Appl. Comput. Harmon. Anal., 32 (2012), 342-356. doi: 10.1016/j.acha.2011.07.003. |
[19] | G. G. Lorentz, M. von Golitschek and Yu. Makovoz, Constructive Approximation: Advanced Problems, Springer Grundlehren, vol. 304, Springer, Berlin, Heidelberg, 1996. doi: 10.1007/978-3-642-60932-9. |
[20] | P. Mathé, s-Numbers in information-based complexity, J. Complexity, 6 (1990), 41-66. doi: 10.1016/0885-064X(90)90011-2. |
[21] | P. Mathé, Random approximation of Sobolev imbeddings, J. Complexity, 7 (1991), 261-281. doi: 10.1016/0885-064X(91)90036-W. |
[22] | P. Mathé, Approximation Theory of Stochastic Numerical Methods, Habilitationsschrift, Fachbereich Mathematik, Freie Universität Berlin, 1994. |
[23] | S. M. Nikolskii, Approximation of Functions of Several Variables and Imbeddings Theorems, Springer-Verlag, Berlin, 1975. |
[24] | G. Pietsch, Operator Ideals, Deut Verlag Wissenschaften, Berlin, 1978. |
[25] | A. Pinkus, N-widths in Approximation Theory, Springer, New York, 1985. |
[26] | S. Smale and D. X. Zhou, Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc., 41 (2004), 279–305. doi: 10.1090/S0273-0979-04-01025-0. |
[27] | S. Smale and D. X. Zhou, Learning theory estimates via integral operators and their approximations, Constr. Approx., 26 (2007), 153-172. doi: 10.1007/s00365-006-0659-y. |
[28] | Y. S. Sun and H. P. Wang, Representation and approximation of multivariate periodic functions with bounded mixed moduli of smoothness, Proc. Steklov Inst. Math., 219 (1997), 350-371. |
[29] | S. A. Stasyuk, Best approximations and Kolmogorov and trigonometric widths of the classes $B_{p, \theta}^\Omega$ of periodic functions of many variables, Ukr. Math. J., 56 (2004), 1849-1863. doi: 10.1007/s11253-005-0155-1. |
[30] | V. N. Temlyakov, Approximation of Periodic Functions, Nova Science, New York, 1993. |
[31] | V. M. Tikhomirov, Diameters of sets in function spaces and the theory of best approximations, Uspekhi Mat. Nauk, 15 (1960), 81-120. doi: 10.1070/RM1960v015n03ABEH004093. |
[32] | V. M. Tikhomirov, Best methods of approximation of differentiable functions in the space $C[-1, 1]$, Mat. Sb., 80 (1969), 290-304. |
[33] | J. F. Traub, G. W. Wasilkowski and H. Woźniakowski, Information-based Complexity, Academic Press, New York, 1988. |
[34] | G. Q. Xu, The $n$-widths for a generalized periodic Besov classes, Acta Math. Sci., 25 (2005), 663-671. doi: 10.1016/S0252-9602(17)30206-0. |