307	RWTH Publication No: 47273        2010        IGPM307.pdf
TITLE	Fast High-Dimensional Approximation with Sparse Occupancy Trees
AUTHORS	Peter Binev, Wolfgang Dahmen, Philipp Lamby
ABSTRACT	This paper is concerned with scattered data approximation in high dimensions: Given a data set X ⊂ Rd of N data points x i along with values y i ∈ R d , i = 1, . . . , N, and viewing the y i as values y i = f (x i ) of some unknown function f , we wish to return for any query point x ∈ Rd an approximation f ̃ (x) to y = f (x). Here the spatial dimension d should be thought of as large. We wish to 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, in the first place, are 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.
KEYWORDS	high-dimensional approximation, non-parametric regression, non-linear approximation, multiresolution tree
DOI	10.1016/j.cam.2010.10.005
PUBLICATION	Journal of computational and applied mathematics 235(8), 2063-2076 (2011)