Fast high-dimensional approximation with sparse occupancy trees

This paper is concerned with scattered data approximation in high dimensions: Given a data set X⊂RdX⊂Rd of NN data points xixi along with values yi∈Rd′yi∈Rd′, i=1,…,Ni=1,…,N, and viewing the yiyi as values yi=f(xi)yi=f(xi) of some unknown function ff, we wish to return for any query point x∈Rdx∈Rd an approximation f̃(x) to y=f(x)y=f(x). Here the spatial dimension dd should be thought of as large. We emphasize that we do not seek a representation of f̃ in terms of a fixed set of trial functions but define f̃ through recovery schemes which are primarily designed to be fast and to deal efficiently with large data sets. For this purpose we propose new methods based on what we call sparse occupancy trees and piecewise linear schemes based on simplex subdivisions.