Prof Markus Hegland Dr Steve Roberts
Consider an example of describing the price of a house as a function of the number of rooms, the build of house, location, accessibility and parameters describing the neighbourhood. Such a function is useful to estimate the value of a house new on the market. A practical available data set, the Boston Housing Data contains 14 parameters from the 1977 US Census. In choosing a function class one needs to consider the complexity of function evaluation, the approximation power, and the complexity of the class.
In this project we will study an approximation class, the sparse grids, which balance these requirements. Consider first the one-dimensional case of real functions. The linear space of piece-wise linear functions ( V_m ) (with grid spacing [1/m] defined on a uniform grid) lead to functions which are very fast to evaluate, are continuous and have good approximation power for twice continuously differentiable (C2) functions. The so-called hat-functions (which are Lagrangian, i.e., they equal 1 in one grid point and zero in all the others) form a convenient basis of ( V_m ).
From this one-dimensional case one derives a class for multidimensional functions using the tensor product basis where the basis functions in d dimensions are products of basis functions in one dimension. This is a choice which is very popular in surface fitting, and the finite element method in general and has been used numerous times for 2 and 3 dimensional problems. However, this turns out to be an impractical choice in high dimensions.
Suppose we have a grid with m basis functions in (every) one dimension, then there would be m^d tensor basis functions for a d-dimensional space. The approximation of C2 functions is proportional to m^{-2}, independent of the dimension. In this case one can improve any given approximation by a factor of 4 by doubling the number of basis functions in all dimensions. This would increase the number of tensor product basis functions by a factor of 2^{14} = 16,384. Note that the smallest (nontrivial) space of tensor product piecewise linear functions has dimension 2^{14}, the case of 16 grid points in each dimension would lead to a 16^{14} = 2^{56} 7210^{15} dimensional function space and the storage of a general function in that space would require 72 10^{15} parameters which is beyond what any current storage space can handle. This is why tensor product basis functions, and in general, piecewise multi-linear functions have not been used for high-dimensional functions.
Sparse grids are "low"-dimensional subspaces of this tensor-product space. They filter out multi-dimensional high-frequency or strongly oscillating terms which do not contribute much to the approximation power of the functions. They are based on hierarchical basis functions, which, like wavelets, resolve the function both in space and in the scale domain, and consequently, the coefficients of these basis functions are much smaller for the basis functions associated with small scales than for the ones associated with large scales. This effect is strongly amplified in higher dimensions and the case of products of functions of small scales. The sparse grid function spaces are obtained from the tensor product space by setting all coefficients which are bound to be small for any C2 function to zero. This leads to a space, which, instead of having m^d dimensions, has asymptotically in m only log2(m)^{d-1} m dimensions. The approximation error for C2 functions in this space drops from O(m-2) to O(log2(m){d-1}m{-2}) (asymptotically in m). This sparse grid function space has been introduced several times since the 1960s but has made its debut as a computational tool to solve partial differential equations in 1991 by Zenger. It has been shown that these sparse grid spaces are flexible enough to deal with problems of up to around d=10 dimensions.
Here is a range of possible projects. Please come and talk to us about them and other possibilities.
Investigating the use of Sparse Grids to approximate high dimensional functions
Investigating the use of Sparse Grids for Probability Density Estimation
Producing histogram estimates of high dimensional data sets provides an important application of sparse grid techniques. There are opportunities for mathematical analysis as well as practical implementation issues.