27
$\begingroup$

What is the preferred and efficient approach for interpolating multidimensional data?

Things I'm worried about:

  1. performance and memory for construction, single/batch evaluation
  2. handling dimensions from 1 to 6
  3. linear or higher-order
  4. ability to obtain gradients (if not linear)
  5. regular vs scattered grid
  6. using as Interpolating Function, e.g. to find roots or to minimize
  7. extrapolation capabilities

Is there efficient open-source implementation of this?

I had partial luck with scipy.interpolate and kriging from scikit-learn.

I did not try splines, Chebyshev polynomials, etc.

Here is what I found so far on this topic:

Python 4D linear interpolation on a rectangular grid

Fast interpolation of regularly sampled 3D data with different intervals in x,y, and z

Fast interpolation of regular grid data

What method of multivariate scattered interpolation is the best for practical use?

$\endgroup$
6
  • 1
    $\begingroup$ What do you want your interpolation for? How is your input data? I don't think that the dimensionality changes a lot the problem. $\endgroup$
    – nicoguaro
    Mar 11, 2015 at 11:14
  • 2
    $\begingroup$ Unfortunately, multivariate interpolation isn't as cut and dried as univariate. For instance, in 1D, you can choose arbitrary interpolation nodes (as long as they are mutually distinct) and always get a unique interpolating polynomial of a certain degree. Already in 2D, this is not true, and you may not have a well-defined polynomial interpolation problem depending on how you choose your nodes. So in short, you have to give us more information on the structure of your data to get useful input. $\endgroup$
    – cfh
    Mar 11, 2015 at 13:39
  • 1
    $\begingroup$ Here's a survey on multivariate polynomial approximation, if you want to pursue that approach: Gasca & Sauer, "Polynomial interpolation in several variables", 2000 citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – cfh
    Mar 11, 2015 at 13:56
  • 3
    $\begingroup$ Chebyshev polynomials on a sparse (e.g. Smolyak) grid are very fast for higher dimensions. The gridpoints are a predetermined subset of the Chebyshev points. Some implementations: tasmanian.ornl.gov , ians.uni-stuttgart.de/spinterp/about.html , github.com/EconForge/Smolyak $\endgroup$ Mar 12, 2015 at 6:37
  • 1
    $\begingroup$ You could try something like Delaunay tessellation on the manifold. $\endgroup$ Mar 13, 2015 at 20:44

1 Answer 1

18
$\begingroup$

For the first part of my question, I found this very useful comparison for performance of different linear interpolation methods using python libraries:

http://nbviewer.ipython.org/github/pierre-haessig/stodynprog/blob/master/stodynprog/linear_interp_benchmark.ipynb

Below is list of methods collected so far.

Standart interpolation, structured grid:

http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.ndimage.interpolation.map_coordinates.html

http://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.RegularGridInterpolator.html

https://github.com/rncarpio/linterp/

Unstructured (scattered) grid:

http://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.LinearNDInterpolator.html#scipy.interpolate.LinearNDInterpolator

http://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.griddata.html

http://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.Rbf.html

2 large projects that include interpolation:

https://github.com/sloriot/cgal-bindings (parts of CGAL, licensed GPL/LGPL)

https://www.earthsystemcog.org/projects/esmp/ (University of Illinois-NCSA License ~= MIT + BSD-3)

Sparse grids:

https://github.com/EconForge/Smolyak

https://github.com/EconForge/dolo/tree/master/dolo/numeric/interpolation

http://people.sc.fsu.edu/~jburkardt/py_src/sparse_grid/sparse_grid.html

https://aerodynamics.lr.tudelft.nl/~rdwight/work_sparse.html

https://pypi.python.org/pypi/puq

Kriging (Gaussian Process):

http://scikit-learn.org/stable/modules/generated/sklearn.gaussian_process.GaussianProcess.html

https://github.com/SheffieldML/GPy

https://software.sandia.gov/svn/surfpack/trunk/

http://openmdao.org/dev_docs/_modules/openmdao/lib/surrogatemodels/kriging_surrogate.html

General GPL licensed:

https://github.com/rncarpio/delaunay_linterp

Tasmanian

The Toolkit for Adaptive Stochastic Modeling and Non-Intrusive Approximation - is a robust library for high dimensional integration and interpolation as well as parameter calibration.

Python binding for Tasmanian:

https://github.com/rncarpio/py_tsg

https://github.com/sloriot/cgal-bindings (parts of CGAL, licensed GPL/LGPL)

$\endgroup$
7
  • 2
    $\begingroup$ I'll add that the very excellent DAKOTA package from sandia has all of the above methods implemented and many more, and it does provide python bindings. It might not be the easiest to get up and running, but it is top notch and gives a lot of options, and is worth checking out. $\endgroup$
    – Aurelius
    Mar 23, 2015 at 15:07
  • $\begingroup$ @Aurelius can you please point to interpolation/approximation routines within DAKOTA? I have experience with that package but only noticed surfpack (already ref-d above) for kriging. $\endgroup$
    – den.run.ai
    Mar 23, 2015 at 15:39
  • $\begingroup$ ok, I found it - dakota.sandia.gov/sites/default/files/docs/6.0/html-ref/… $\endgroup$
    – den.run.ai
    Mar 23, 2015 at 15:42
  • $\begingroup$ @Aurelius all dakota approximation models are in surfpack $\endgroup$
    – den.run.ai
    Mar 24, 2015 at 15:03
  • $\begingroup$ This is bloody ace; well done! $\endgroup$
    – Astrid
    Sep 11, 2016 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.