MarkusSparse Grid Methods
The search for interesting variable stars, the discovery of relations between geomorphological properties, satellite observations and mineral concentrations, and the analysis of biological networks all require the solution of a large number of complex learning problems with large amounts of data. A major computational challenge faced in these investigations is posed by the curse of dimensionality. A well known aspect of this curse is the exponential dependence of the size of regular grids on the dimension of the domain. This makes traditional finite element approaches infeasible for high-dimensional domains. It is less known that this curse also affects computations of radial basis function approximations – in a slightly more subtle way. Sparse grid functions can deal with the major problems of the curse of dimensionality. As they are the superposition of traditional finite element spaces, many well-known algorithms can be generalized to the sparse grid context. Sparse grids have been successfully used to solve partial differential equations in the past and, more recently, have been shown to be competitive for learning problems as well. The talk will provide a general introduction to the major properties of sparse grids and will discuss connections with kernel based methods and parallel learning algorithms. It will conclude with a short review over some recent work on algorithms based on the combination technique.
Author: Markus Hegland, Australian National University Anu