August  2020, 19(8): 3957-3971. doi: 10.3934/cpaa.2020175

Exact asymptotic orders of various randomized widths on Besov classes

1. 

Mathematics and Science College, Shanghai Normal University, Shanghai 200234, China

2. 

School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China

* Corresponding author

Received  April 2019 Revised  September 2019 Published  May 2020

Fund Project: This work is supported by National Nature Science Foundation of China [Grant Nos.11271199, 11671213]

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: Liqin Duan, Peixin Ye. Exact asymptotic orders of various randomized widths on Besov classes. Communications on Pure & Applied Analysis, 2020, 19 (8) : 3957-3971. doi: 10.3934/cpaa.2020175
References:
[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.   Google Scholar

[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.  Google Scholar

[3]

P. BinevA. CohenW. Dahmen and R. DeVore, Classification algorithms using adaptive partitioning, Ann. Statist., 42 (2014), 2141-2163.  doi: 10.1214/14-AOS1234.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[17] N. Korneichuk, Exact Constants in Approximation Theory, Cambridge Univesity Press, Cambridge, 1991.  doi: 10.1017/CBO9781107325791.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[20]

P. Mathé, s-Numbers in information-based complexity, J. Complexity, 6 (1990), 41-66.  doi: 10.1016/0885-064X(90)90011-2.  Google Scholar

[21]

P. Mathé, Random approximation of Sobolev imbeddings, J. Complexity, 7 (1991), 261-281.  doi: 10.1016/0885-064X(91)90036-W.  Google Scholar

[22]

P. Mathé, Approximation Theory of Stochastic Numerical Methods, Habilitationsschrift, Fachbereich Mathematik, Freie Universität Berlin, 1994. Google Scholar

[23]

S. M. Nikolskii, Approximation of Functions of Several Variables and Imbeddings Theorems, Springer-Verlag, Berlin, 1975.  Google Scholar

[24]

G. Pietsch, Operator Ideals, Deut Verlag Wissenschaften, Berlin, 1978.  Google Scholar

[25]

A. Pinkus, N-widths in Approximation Theory, Springer, New York, 1985.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[30]

V. N. Temlyakov, Approximation of Periodic Functions, Nova Science, New York, 1993.  Google Scholar

[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.  Google Scholar

[32]

V. M. Tikhomirov, Best methods of approximation of differentiable functions in the space $C[-1, 1]$, Mat. Sb., 80 (1969), 290-304.   Google Scholar

[33] J. F. TraubG. W. Wasilkowski and H. Woźniakowski, Information-based Complexity, Academic Press, New York, 1988.   Google Scholar
[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.  Google Scholar

show all references

References:
[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.   Google Scholar

[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.  Google Scholar

[3]

P. BinevA. CohenW. Dahmen and R. DeVore, Classification algorithms using adaptive partitioning, Ann. Statist., 42 (2014), 2141-2163.  doi: 10.1214/14-AOS1234.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[17] N. Korneichuk, Exact Constants in Approximation Theory, Cambridge Univesity Press, Cambridge, 1991.  doi: 10.1017/CBO9781107325791.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[20]

P. Mathé, s-Numbers in information-based complexity, J. Complexity, 6 (1990), 41-66.  doi: 10.1016/0885-064X(90)90011-2.  Google Scholar

[21]

P. Mathé, Random approximation of Sobolev imbeddings, J. Complexity, 7 (1991), 261-281.  doi: 10.1016/0885-064X(91)90036-W.  Google Scholar

[22]

P. Mathé, Approximation Theory of Stochastic Numerical Methods, Habilitationsschrift, Fachbereich Mathematik, Freie Universität Berlin, 1994. Google Scholar

[23]

S. M. Nikolskii, Approximation of Functions of Several Variables and Imbeddings Theorems, Springer-Verlag, Berlin, 1975.  Google Scholar

[24]

G. Pietsch, Operator Ideals, Deut Verlag Wissenschaften, Berlin, 1978.  Google Scholar

[25]

A. Pinkus, N-widths in Approximation Theory, Springer, New York, 1985.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[30]

V. N. Temlyakov, Approximation of Periodic Functions, Nova Science, New York, 1993.  Google Scholar

[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.  Google Scholar

[32]

V. M. Tikhomirov, Best methods of approximation of differentiable functions in the space $C[-1, 1]$, Mat. Sb., 80 (1969), 290-304.   Google Scholar

[33] J. F. TraubG. W. Wasilkowski and H. Woźniakowski, Information-based Complexity, Academic Press, New York, 1988.   Google Scholar
[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.  Google Scholar

[1]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168

[2]

Mikil Foss, Joe Geisbauer. Higher differentiability in the context of Besov spaces for a class of nonlocal functionals. Evolution Equations & Control Theory, 2013, 2 (2) : 301-318. doi: 10.3934/eect.2013.2.301

[3]

Nguyen Thi Hoai. Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 495-512. doi: 10.3934/naco.2020040

[4]

Martin Hanke, William Rundell. On rational approximation methods for inverse source problems. Inverse Problems & Imaging, 2011, 5 (1) : 185-202. doi: 10.3934/ipi.2011.5.185

[5]

Per Christian Moan, Jitse Niesen. On an asymptotic method for computing the modified energy for symplectic methods. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 1105-1120. doi: 10.3934/dcds.2014.34.1105

[6]

Kersten Schmidt, Ralf Hiptmair. Asymptotic boundary element methods for thin conducting sheets. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 619-647. doi: 10.3934/dcdss.2015.8.619

[7]

Martha Garlick, James Powell, David Eyre, Thomas Robbins. Mathematically modeling PCR: An asymptotic approximation with potential for optimization. Mathematical Biosciences & Engineering, 2010, 7 (2) : 363-384. doi: 10.3934/mbe.2010.7.363

[8]

Thierry Paul, Mario Pulvirenti. Asymptotic expansion of the mean-field approximation. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 1891-1921. doi: 10.3934/dcds.2019080

[9]

Dejian Chang, Huili Liu, Jie Xiong. A branching particle system approximation for a class of FBSDEs. Probability, Uncertainty and Quantitative Risk, 2016, 1 (0) : 9-. doi: 10.1186/s41546-016-0007-y

[10]

Shouming Zhou. The Cauchy problem for a generalized $b$-equation with higher-order nonlinearities in critical Besov spaces and weighted $L^p$ spaces. Discrete & Continuous Dynamical Systems, 2014, 34 (11) : 4967-4986. doi: 10.3934/dcds.2014.34.4967

[11]

Caojin Zhang, George Yin, Qing Zhang, Le Yi Wang. Pollution control for switching diffusion models: Approximation methods and numerical results. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3667-3687. doi: 10.3934/dcdsb.2018310

[12]

Jake Bouvrie, Boumediene Hamzi. Kernel methods for the approximation of some key quantities of nonlinear systems. Journal of Computational Dynamics, 2017, 4 (1&2) : 1-19. doi: 10.3934/jcd.2017001

[13]

Ariadna Farrés, Àngel Jorba. On the high order approximation of the centre manifold for ODEs. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 977-1000. doi: 10.3934/dcdsb.2010.14.977

[14]

Martin Redmann, Peter Benner. Approximation and model order reduction for second order systems with Levy-noise. Conference Publications, 2015, 2015 (special) : 945-953. doi: 10.3934/proc.2015.0945

[15]

Niranjan Balachandran, Atreyee Kundu, Debasish Chatterjee. Randomized algorithms for stabilizing switching signals. Mathematical Control & Related Fields, 2019, 9 (1) : 159-174. doi: 10.3934/mcrf.2019009

[16]

Marcel Oliver. The Lagrangian averaged Euler equations as the short-time inviscid limit of the Navier–Stokes equations with Besov class data in $\mathbb{R}^2$. Communications on Pure & Applied Analysis, 2002, 1 (2) : 221-235. doi: 10.3934/cpaa.2002.1.221

[17]

Anderson L. A. de Araujo, Marcelo Montenegro. Existence of solution and asymptotic behavior for a class of parabolic equations. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1213-1227. doi: 10.3934/cpaa.2021017

[18]

Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145

[19]

Shalva Amiranashvili, Raimondas  Čiegis, Mindaugas Radziunas. Numerical methods for a class of generalized nonlinear Schrödinger equations. Kinetic & Related Models, 2015, 8 (2) : 215-234. doi: 10.3934/krm.2015.8.215

[20]

Siting Liu, Levon Nurbekyan. Splitting methods for a class of non-potential mean field games. Journal of Dynamics & Games, 2021, 8 (4) : 467-486. doi: 10.3934/jdg.2021014

2020 Impact Factor: 1.916

Metrics

  • PDF downloads (136)
  • HTML views (68)
  • Cited by (0)

Other articles
by authors

[Back to Top]