Sparse residual tree and forest
This work addresses the problem of efficient and accurate data approximation for researchers and practitioners dealing with multivariate scattered data, representing an incremental improvement through hybrid methods.
The paper introduces Sparse Residual Tree (SRT) and Sparse Residual Forest (SRF) for multivariate scattered data approximation, achieving sparse and stable approximations with worst-case time complexity of O(N log N) for initial work and O(log N) for predictions, and storage of O(N log N).
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 $\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.