Optimal data transformation for sparse grids

Bastian Bohn
Rheinische Friedrich-Wilhelms-Universität Bonn
Institute for Numerical Simulation

The nature of the construction of spline-based sparse grid spaces makes them an (almost) optimal candidate for interpolation, regression and quadrature tasks in Sobolev spaces of dominating mixed smoothness. Due to its tensor-product structure, the Sobolev space of mixed smoothness of order $1$ contains functions with kinks which reside in an affine linear subspace perpendicular to a coordinate axis. Therefore, functions of this type can be well-approximated by piecewise-linear splines on sparse grids. Even if the function under consideration employs a jump residing in such an affine linear subspace, a dimension- or space-adaptive sparse grid can be employed to achieve good approximation results with only few basis functions.

However, if the relevant features of a function do not align with the coordinate axes, an approximation by sparse grids is usually not feasible anymore. To remedy this problem, we propose a preprocessing step. To this end, we introduce an optimization algorithm which determines the - in an ANOVA-sense - optimal rotation of a function such that it best suits the sparse grid structure. After applying this rotation the sparse-grid algorithm is able to achieve optimal results if the kinks/jumps of the function at hand reside in perpendicular affine linear subspaces, which do not have to be aligned with the coordinate axes anymore. We will show how a sparse grid least-squares regression algorithm benefits from applying the rotation to the data in numerical examples. Furthermore, we will hint at possible extensions of our method to the case of features residing in non-perpendicular or even non-linear subspaces.

Back to Long Programs