Sequential Approximation of Functions in Sobolev Spaces Using Random Samples
Tóm tắt
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.
Tài liệu tham khảo
Brezinski, C., Redivo-Zaglia, M.: Convergence acceleration of Kaczmarz’s method. J. Eng. Math. 93, 3–19 (2015)
Chen, X., Powell, A.M.: Almost sure convergence of the Kaczmarz algorithm with random measurements. J. Fourier Anal. Appl. 18, 1195–1214 (2012)
Cheney, E.W.: Introduction to Approximation Theory. McGraw-Hill, New York (1966)
Davis, P.J.: Interpolation and Approximation. Dover, New York (1975)
Eldar, Y.C., Needell, D.: Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss lemma. Numer. Algorithm 58(2), 163–177 (2011)
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)
Liu, J., Wright, S.J.: An accelerated randomized Kaczmarz algorithm. Math. Comput. 85(297), 153–178 (2016)
Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2008)
Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50(2), 395–403 (2010)
Powell, M.J.D.: Approximation Theory and Methods. Cambridge University Press, Cambridge (1981)
Rivlin, T.J.: An Introduction to the Approximation of Functions. Dover Publication Inc, New York (1969)
Shin, Y., Wu, K., Xiu, D.: Sequential function approximation with noisy data. J. Comput. Phys. 371, 363–381 (2018)
Shin, Y., Xiu, D.: A randomized algorithm for multivariate function approximation. SIAM J. Sci. Comput. 39(3), A983–A1002 (2017)
Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262–278 (2009)
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)
Wu, K., Shin, Y., Xiu, D.: A randomized tensor quadrature method for high dimensional polynomial approximation. SIAM J. Sci. Comput. 39, A1811–A1833 (2017)
Wu, K., Xiu, D.: Sequential function approximation on arbitrarily distributed point sets. J. Comput. Phys. 354, 370–386 (2018)
Wu, K., Xiu, D.: Numerical aspects for approximating governing equations using data. J. Comput. Phys. 384, 200–221 (2019)
Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34(2), 773–793 (2013)