Fast high-dimensional approximation with sparse occupancy trees

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:235

Article

Binev, Peter¹  Dahmen, Wolfgang²  Lamby, Philipp¹ 

[1] Univ S Carolina, Interdisciplinary Math Inst, Columbia, SC 29208 USA

[2] Rhein Westfal TH Aachen, Inst Geometr & Prakt Math, D-52056 Aachen, Germany

关键词: High-dimensional approximation;    Non-parametric regression;    Non-linear approximation;    Multiresolution tree;   

DOI  :  10.1016/j.cam.2010.10.005

来源: Elsevier

【 摘 要 】

This paper is concerned with scattered data approximation in high dimensions: Given a data set X subset of R-d of N data points x(i) along with values y(i) is an element of 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 is an element of R-d an approximation (f) over tilde (x) to y = f (x). Here the spatial dimension d should be thought of as large. We emphasize that we do not seek a representation of (f) over tilde in terms of a fixed set of trial functions but define (f) over tilde 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. (C) 2010 Elsevier B.V. All rights reserved.

【 授权许可】

Free