Adaptive Sparse Approximations of Scattered Data

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 O(N log(2) N) for the initial work and O(log(2) N) for each prediction, meanwhile, the worst case storage requirement is O(N log(2) N), where the N data points can be arbitrary distributed. Numerical experiments are performed for several illustrative examples.

Automated summary

This paper proposes two adaptive approximations for multivariate scattered data, namely sparse residual tree (SRT) and sparse residual forest (SRF). SRT provides sparse and stable approximations in areas with sufficient or redundant data, and identifies possible local regions with insufficient data; while SRF combines SRT predictors to enhance approximation accuracy and stability. The hierarchical parallel SRT algorithm is based on tree decomposition and adaptive radial basis function explorations, achieving convergence results with time complexity O(N log(2) N) and worst case storage requirement O(N log(2) N). Numerical experiments validate the effectiveness of the proposed methods.