Hi,anyone has a recommendation for a decent n-dimension (greater than 3) interpolation method (and maybe some code...).K.

Maybe radial basis functions are a start. Maybe also Scilab http://www.openeering.com/sites/default ... ab.pdfHere is meshless for option pricing: http://www.wilmott.com/pdfs/101117_pena.pdf//Depending on the complexity, access to a nd class (e.g. Boost multiarray) it should be possible to write your own interpolators.

thanks.I was going for a Nearest-neighbor interpolation as it seems the less complex one to implement.also, my points are close to each other (from a MC simulation effectively).

What is the number of points and dimension? Each technique has a preferred range.If dimensionality is still low (4-7, with some directions with little variation), why then not classical regression?Whatever the approximator, if you can first of all use quasi MC to spread samples evenly and thus get better coverage. You could also use automatic differentiation to add gradients locally to NNI (that's dimensionality-proof) or better drive RBFs/kernel regression.There are also techniques to limit the amount of terms in a multidimensional Fourier expansion, but here it starts to get complicated.

well, thank you all Quartz, Outrun, Daniel for your answers.First, I'll try and give some context:I have 5 dimensions. The grid is quite massive.Actually, it's the interpolation on the d0 absorption density matrix given by Doust (in his paper no-arbitrage SABR). I also generated by a MC method. So we have sigma, beta, nu, rho, time dimensions and an impressive amount of data.Linear interp is actually not a problem (again given the nature of the data on which I interpolate). But I found some ordering + nearest neighbourhood method which works okay. The RBF is a bit far fetch (although nice). So I will have a look at Outrun's recommendation on NN.of course any code or paper handy is welcome...

I reckon the CERN Root guys must have something (?) http://root.cern.ch/root/html/RooDataHist.html HD5?http://en.wikipedia.org/wiki/Hierarchical_Data_Format(just a guess on my part)

that's quite true actually!// Perform boundary safe 'intOrder'-th interpolation of weights in dimension 'dim'// at current value 'xvalthis might be very helpful.

yeah, again to reiterate an idea which work somehow ok-ish: just re-order the n-vectors and iterate (quite quickly) to find the closest available point... after that you can look at the neighbour points and start to apply some interpolation technique....mind you this is quite a useful and interesting topic.

Do you want something like this in nd?

@outrun that looks like a smart idea. let me try this and revert.

Linear regression is good but you might want to weight the regression samples by the inverse of the distance from the unknown target point to the known grid samples to ensure the interpolated value approaches to the known value when the target approaches a known point. Weighted linear interpolation will also implicitly handle some kinds of nonlinearities (or non-coplanarities) in the function surface.One tricky bit about hi-D cubes is that the diagonally-opposite corner of the cube may be farther from the target point than some of the points in adjacent cubes. In fact, in the case of N=5, some points 2 cubes away can be closer than the opposite diagonal! A target point that falls near a grid point might be best interpolated using points from a multi-D cross (e.g., {[0,0,+1],[0,0,-1],[0,+1,0],[0,-1,0],[+1,0,0],[-1,0,0]})

QuoteOriginally posted by: Traden4AlphaOne tricky bit about hi-D cubes is that the diagonally-opposite corner of the cube may be farther from the target point than some of the points in adjacent cubes. In fact, in the case of N=5, some points 2 cubes away can be closer than the opposite diagonal! A target point that falls near a grid point might be best interpolated using points from a multi-D cross (e.g., {[0,0,+1],[0,0,-1],[0,+1,0],[0,-1,0],[+1,0,0],[-1,0,0]})Or one might use more isotropic (near spherical) cells from the start, although indexing might become a bit tricky and one needs to handle boundaries, unless periodicity is there. Kelvin/Weaire-Phelan structure structure for 3 dimensions, other sphere packings to get a bit higher. Which brings you quickly to qMC again