Sequential Approximation of Functions in Sobolev Spaces Using Random Samples

doi:10.1007/s42967-019-00028-7

Communications on Applied Mathematics and Computation ›› 2019, Vol. 1 ›› Issue (3): 449-466.doi: 10.1007/s42967-019-00028-7

• ORIGINAL PAPER • 上一篇下一篇

Sequential Approximation of Functions in Sobolev Spaces Using Random Samples

Kailiang Wu, Dongbin Xiu

Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA

收稿日期:2018-08-27 修回日期:2018-12-03 出版日期:2019-09-20 发布日期:2019-09-09
通讯作者: Dongbin Xiu, Kailiang Wu E-mail:xiu.16@osu.edu;wu.3423@osu.edu

Sequential Approximation of Functions in Sobolev Spaces Using Random Samples

Kailiang Wu, Dongbin Xiu

Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA

Received:2018-08-27 Revised:2018-12-03 Online:2019-09-20 Published:2019-09-09

摘要/Abstract

摘要： We present an iterative algorithm for approximating an unknown function sequentially using random samples of the function values and gradients. This is an extension of the recently developed sequential approximation (SA) method, which approximates a target function using samples of function values only. The current paper extends the development of the SA methods to the Sobolev space and allows the use of gradient information naturally. The algorithm is easy to implement, as it requires only vector operations and does not involve any matrices. We present tight error bound of the algorithm, and derive an optimal sampling probability measure that results in fastest error convergence. Numerical examples are provided to verify the theoretical error analysis and the effectiveness of the proposed SA algorithm.

关键词: Approximation theory, Sequential approximation, Randomized algorithm, Sobolev space, Optimal sampling probability measure

Abstract: We present an iterative algorithm for approximating an unknown function sequentially using random samples of the function values and gradients. This is an extension of the recently developed sequential approximation (SA) method, which approximates a target function using samples of function values only. The current paper extends the development of the SA methods to the Sobolev space and allows the use of gradient information naturally. The algorithm is easy to implement, as it requires only vector operations and does not involve any matrices. We present tight error bound of the algorithm, and derive an optimal sampling probability measure that results in fastest error convergence. Numerical examples are provided to verify the theoretical error analysis and the effectiveness of the proposed SA algorithm.

Key words: Approximation theory, Sequential approximation, Randomized algorithm, Sobolev space, Optimal sampling probability measure

Kailiang Wu, Dongbin Xiu. Sequential Approximation of Functions in Sobolev Spaces Using Random Samples[J]. Communications on Applied Mathematics and Computation, 2019, 1(3): 449-466.

参考文献

1. Brezinski, C., Redivo-Zaglia, M.:Convergence acceleration of Kaczmarz's method. J. Eng. Math. 93, 3-19 (2015)
2. Chen, X., Powell, A.M.:Almost sure convergence of the Kaczmarz algorithm with random measurements. J. Fourier Anal. Appl. 18, 1195-1214 (2012)
3. Cheney, E.W.:Introduction to Approximation Theory. McGraw-Hill, New York (1966)
4. Davis, P.J.:Interpolation and Approximation. Dover, New York (1975)
5. Eldar, Y.C., Needell, D.:Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma. Numer. Algorithm 58(2), 163-177 (2011)
6. Genz, A.:Testing multidimensional integration routines. In:Proceedings of International Conference on Tools, Methods and Languages for Scientific and Engineering Computation, pp. 81-94. Elsevier North-Holland, Inc. (1984)
7. Liu, J., Wright, S.J.:An accelerated randomized Kaczmarz algorithm. Math. Comput. 85(297), 153- 178 (2016)
8. Liu, J.S.:Monte Carlo Strategies in Scientific Computing. Springer, New York (2008)
9. Needell, D.:Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50(2), 395-403 (2010)
10. Powell, M.J.D.:Approximation Theory and Methods. Cambridge University Press, Cambridge (1981)
11. Rivlin, T.J.:An Introduction to the Approximation of Functions. Dover Publication Inc, New York (1969)
12. Shin, Y., Wu, K., Xiu, D.:Sequential function approximation with noisy data. J. Comput. Phys. 371, 363-381 (2018)
13. Shin, Y., Xiu, D.:A randomized algorithm for multivariate function approximation. SIAM J. Sci. Comput. 39(3), A983-A1002 (2017)
14. Strohmer, T., Vershynin, R.:A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262-278 (2009)
15. Wallace, T., Sekmen, A.:Acceleration of Kaczmarz using orthogonal subspace projections. In:Biomedical Sciences and Engineering Conference (BSEC), Oak Ridge, Tennessee, USA, May 21-23, 2013. pp. 1-4. IEEE (2013)
16. Wu, K., Shin, Y., Xiu, D.:A randomized tensor quadrature method for high dimensional polynomial approximation. SIAM J. Sci. Comput. 39, A1811-A1833 (2017)
17. Wu, K., Xiu, D.:Sequential function approximation on arbitrarily distributed point sets. J. Comput. Phys. 354, 370-386 (2018)
18. Wu, K., Xiu, D.:Numerical aspects for approximating governing equations using data. J. Comput. Phys. 384, 200-221 (2019)
19. Zouzias, A., Freris, N.M.:Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34(2), 773-793 (2013)

Sequential Approximation of Functions in Sobolev Spaces Using Random Samples

Sequential Approximation of Functions in Sobolev Spaces Using Random Samples

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价