Sparse residual tree and forest

MaRDI QIDQ6314202zbMATH OpenFDO

Authors Xin Xu, Xiaopeng Luo

Publication date 18 February 2019

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15)

Abstract: Sparse residual tree (SRT) is an adaptive exploration method for multivariate scattered data approximation. It leads to sparse and stable approximations in areas where the data is sufficient or redundant, and points out the possible local regions where data refinement is needed. Sparse residual forest (SRF) is a combination of SRT predictors to further 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 $mathcalO(Nlo{g}_{2}N)$ for the initial work and $mathcalO(lo{g}_{2}N)$ for each prediction, meanwhile, the worst case storage requirement is $mathcalO(Nlo{g}_{2}N)$, where the $N$ data points can be arbitrary distributed. Numerical experiments are performed for several illustrative examples.

This page was built for publication: Sparse residual tree and forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314202)