[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Adaptive Sparse Approximations of Scattered Data

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

In this paper, two adaptive approximations, i.e., sparse residual tree (SRT) and sparse residual forest (SRF), are proposed for multivariate scattered data. SRT not only leads to sparse and stable approximations in areas where the data is sufficient or redundant, but also points out the possible local regions where the data is inadequate. And SRF is a combination of SRT predictors to improve the approximation accuracy and stability according to the error characteristics of SRTs. The hierarchical parallel SRT algorithm is based on both tree decomposition and adaptive radial basis function (RBF) explorations, whereby for each child a sparse and proper RBF refinement is added to the approximation by minimizing the norm of the residual inherited from its parent. The convergence results are established for both SRTs and SRFs. The worst case time complexity of SRTs is \(\mathcal {O}(N\log _2N)\) for the initial work and \(\mathcal {O}(\log _2N)\) for each prediction, meanwhile, the worst case storage requirement is \(\mathcal {O}(N\log _2N)\), where the N data points can be arbitrary distributed. Numerical experiments are performed for several illustrative examples.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

References

  1. Akbilgic, O., Bozdogan, H., Balaban, M.E.: A novel hybrid RBF neural networks model as a forecaster. Stat. Comput. 24, 365–375 (2014)

    Article  MathSciNet  Google Scholar 

  2. Babuška, I., Melenk, J.M.: The partition of unity method. Int. J. Numer. Methods Eng. 40, 727–758 (1997)

    Article  MathSciNet  Google Scholar 

  3. Beatson, R.K., Cherrie, J.B., Mouat, C.T.: Fast fitting of radial basis functions: methods based on preconditioned GMRES iteration. Adv. Comput. Math. 11, 253–270 (1999)

    Article  MathSciNet  Google Scholar 

  4. Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18, 509–517 (1975)

    Article  Google Scholar 

  5. Breiman, L.: Random forests. Mach. Learn. 45, 5–32 (2001)

    Article  Google Scholar 

  6. Cavoretto, R., De Rossi, A.: Adaptive meshless refinement schemes for RBF-PUM collocation. Appl. Math. Lett. 90, 131–138 (2019)

    Article  MathSciNet  Google Scholar 

  7. Davydov, O., Oanh, D.T.: On the optimal shape parameter for Gaussian radial basis function finite difference approximation of the Poisson equation. Comput. Math. Appl. 62, 2143–2161 (2011)

    Article  MathSciNet  Google Scholar 

  8. De Marchi, S., Martinez, A., Perracchione, E., Rossini, M.: RBF-based partition of unity methods for elliptic PDEs: adaptivity and stability issues via variably scaled kernels. J. Sci. Comput. 79(1), 321–344 (2019)

    Article  MathSciNet  Google Scholar 

  9. Dong, Z., Georgoulis, E.H., Levesley, J., Usta, F.: A multilevel sparse kernel-based stochastic collocation finite element method for elliptic problems with random coefficients. Comput. Math. Appl. 76(8), 1950–1965 (2018)

    Article  MathSciNet  Google Scholar 

  10. Fei, B., Liu, J.: Binary tree of SVM: a new fast multiclass training and classification algorithm. IEEE Trans. Neural Netw. 17, 696–704 (2006)

    Article  Google Scholar 

  11. Floater, M.S., Iske, A.: Multistep scattered data interpolation using compactly supported radial basis functions. J. Comput. Appl. Math. 73, 65–78 (1996)

    Article  MathSciNet  Google Scholar 

  12. Fornberg, B., Flyer, N.: A Primer on Radial Basis Functions with Applications to the Geosciences. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2015)

    Book  Google Scholar 

  13. Francis, J., Narcowich, J.D.W., Wendland, H.: Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting. Math. Comput. 74, 743–763 (2005)

    MathSciNet  MATH  Google Scholar 

  14. Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. 3, 209–226 (1977)

    Article  Google Scholar 

  15. Georgoulis, E., Levesley, J., Subhan, F.: Multilevel sparse kernel-based interpolation. SIAM J. Sci. Comput. 35, A815–A831 (2012)

    Article  MathSciNet  Google Scholar 

  16. Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013)

    MATH  Google Scholar 

  17. Hady, M.F.A., Schwenker, F., Palm, G.: Semi-supervised learning for tree-structured ensembles of RBF networks with Co-Training. Neural Netw. 23, 497–509 (2010)

    Article  Google Scholar 

  18. Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84–90 (1960)

    Article  MathSciNet  Google Scholar 

  19. Heryudono, A., Larsson, E., Ramage, A., Von Sydow, L.: Preconditioning for radial basis function partition of unity methods. J. Sci. Comput. 67(3), 1089–1109 (2016)

    Article  MathSciNet  Google Scholar 

  20. Larsson, E., Shcherbakov, V., Heryudono, A.: A least squares radial basis function partition of unity method for solving PDEs. SIAM J. Sci. Comput. 39, A2538–A2563 (2017)

    Article  MathSciNet  Google Scholar 

  21. Luo, X., Lu, Z., Xu, X.: Reproducing kernel technique for high dimensional model representations (HDMR). Comput. Phys. Commun. 185(12), 3099–3108 (2014)

    Article  Google Scholar 

  22. Madych, W.R.: An estimate for multivariate interpolation II. J. Approx. Theory 142, 116–128 (2006)

    Article  MathSciNet  Google Scholar 

  23. Narcowich, F.J., Ward, J.D., Wendland, H.: Refined error estimates for radial basis function interpolation. Constr. Approx. 19, 541–564 (2003)

    Article  MathSciNet  Google Scholar 

  24. Rieger, C., Zwicknagl, B.: Sampling inequalities for infinitely smooth functions, with applications to interpolation and machine learning. Adv. Comput. Math. 32, 103–129 (2010)

    Article  MathSciNet  Google Scholar 

  25. Schaback, R.: Error estimates and condition numbers for radial basis function interpolation. Adv. Comput. Math. 3, 251–264 (1995)

    Article  MathSciNet  Google Scholar 

  26. Usta, F., Levesley, J.: Multilevel quasi-interpolation on a sparse grid with the Gaussian. Numer. Algorithms 77(3), 793–808 (2018)

    Article  MathSciNet  Google Scholar 

  27. Wendland, H.: Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics 17. Cambridge University Press, Cambridge (2005)

    Google Scholar 

  28. Wendland, H., Rieger, C.: Approximate interpolation with applications to selecting smoothing parameters. Numer. Math. 101, 729–748 (2005)

    Article  MathSciNet  Google Scholar 

  29. Wu, Z., Schaback, R.: Local error estimates for radial basis function interpolation of scattered data. IMA J. Numer. Anal. 13, 13–27 (1993)

    Article  MathSciNet  Google Scholar 

  30. Xu, X., Luo, X., Lu, Z.: A numerical meshless method of soliton-like structures model via an optimal sampling density based kernel interpolation. Comput. Phys. Commun. 192, 12–22 (2015)

    Article  MathSciNet  Google Scholar 

  31. Zhong, D., Wang, L., Bi, L.: Implicit surface reconstruction based on generalized radial basis functions interpolant with distinct constraints. Appl. Math. Model. 71, 408–420 (2019)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Control and Systems Engineering, School of Management and Engineering, Nanjing University, Nanjing, 210008, China

    Xin Xu & Xiaopeng Luo

  2. Department of Chemistry, Princeton University, Princeton, NJ, 08544, USA

    Xin Xu & Xiaopeng Luo

Authors
  1. Xin Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaopeng Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

X.X. acknowledges financial support from the National Natural Science Foundation of China (Grant No. 62003159) and the Natural Science Foundation of Jiangsu Province (Grant No. BK20200332), and X.L. acknowledges financial support while he was at Princeton from the National Science Foundation (Grant No. CHE-1763198)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, X., Luo, X. Adaptive Sparse Approximations of Scattered Data. J Sci Comput 90, 87 (2022). https://doi.org/10.1007/s10915-021-01752-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-021-01752-0

Keywords

Search

Navigation