Advanced Search
Article Contents
Article Contents

Exact asymptotic orders of various randomized widths on Besov classes

  • * Corresponding author

    * Corresponding author
This work is supported by National Nature Science Foundation of China [Grant Nos.11271199, 11671213]
Abstract Full Text(HTML) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 41A46, 41A63; Secondary: 65C05, 65D99.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [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. BinevA. CohenW. 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. BinevA. CohenW. Dahmen and R. DeVore, Classification algorithms using adaptive partitioning, Ann. Statist., 42 (2014), 2141-2163.  doi: 10.1214/14-AOS1234.
    [4] P. BinevA. CohenW. DahmenR. DeVore and V. Temlyakov, Universal algorithms for learning theory. I. Piecewise constant functions, J. Mach. Learn. Res., 6 (2005), 1297-1321. 
    [5] G. ByrenheidR. 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. CohenW. 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. DeVoreG. KerkyacharianD. 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. DonohoI. M. JohnstoneG. 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. KorneichukExact 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. TraubG. W. Wasilkowski and  H. WoźniakowskiInformation-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.
  • 加载中

Article Metrics

HTML views(1451) PDF downloads(188) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint