Can querying "TriScatteredInterp" be as fast as "griddedInterpolant"?

Hi, im wondering why querying the TriScatteredInterpolant is so much slower and so much more size dependent than griddedInterpolant. Is there a way to have the fast performance of the griddedinterpolant for scattered data interpolation?

For illustrative purpose consider this example, where i create a gridded and a scattered interpolant for a smaller grid and a larger grid

[x1 x2 x3]=ndgrid(1:30,1:30,1:30);
[y1 y2 y3]=ndgrid(1:100,1:100,1:100);
x4=(x1+x2+x3);
y4=(y1+y2+y3);
LLip1  = griddedInterpolant(x1,x2,x3,x4)  ;
LLip2  = griddedInterpolant(y1,y2,y3,y4)  ;
LLip4  = TriScatteredInterp(y1(:),y2(:),y3(:),y4(:))  ;
LLip3  = TriScatteredInterp(x1(:),x2(:),x3(:),x4(:))  ;
display('small gridded')
tic; for i=1:100; LLip(2.5,3.4,3.2); end; toc
display('large gridded')
tic; for i=1:100; LLip2(2.5,3.4,3.2); end; toc
display('small scattered')
tic; for i=1:100; LLip3(2.5,3.4,3.2); end; toc
display('large scattered')
tic; for i=1:100; LLip4(2.5,3.4,3.2); end; toc

Output (matlab 2012a64bit): small gridded Elapsed time is 0.002512 seconds. large gridded Elapsed time is 0.002306 seconds. small scattered Elapsed time is 0.281428 seconds. large scattered Elapsed time is 9.635930 seconds.

(In my application in fact, similaly to the example, my data is not properly scattered. It merely has ragged edges, like

3   2   1   NaN
2   1   NaN NaN
1   NaN NaN NaN

i thought about using the griddedinterpolant when possible and using the sctatteredInerpolant only for the edges, i.e. when the gridded would return NaN, but a fast triscatteredinterp would make things easier...)

Answer 1

[Matt J]

Is there a way to have the fast performance of the griddedinterpolant for scattered data interpolation?

I doubt it. gridded interpolation is fundamentally easier because data neighbors that participate in interpolation at a given point are easy to find due to their plaid arrangement. Additionally, the interpolation operations are tensorially separable.

Conversely, with scattered interpolation, it's harder to figure out which neighbours should participate. E.g., TriScatteredInterp uses a Delaunay triangulation to determine this. Additionally, the interpolation is not tensorially separable in the scattered case.

[Matt J]

People seem pretty happy with this, though

http://www.mathworks.com/matlabcentral/fileexchange/4551-inpaintnans

[dominik]

Matt, Thanks for your replys!!

Unfortunatley, your pessimistic view seems to make sense.

The inpaint functions seems useful to fill NaNs in a matrix. Yet im not concerned about filling the NaNs, they are no errors, they meant to be NaNs. What i want to do is interpolate between the non-NaN elements of the matrix. Using the matrix from above ans an example, i want to interpolate at points like the ones marked by the xs and ys.

3 y 2 x 1  NaN
   y  x
2   1  NaN NaN
  x
1  NaN NaN NaN

using scatteredInterp can do but is slow (given a much larger matrix). griddedinterpolant works on the ys but yields NaN for the xs.

[Matt J]

Yes, but inpaint_nans is claimed to be able to extrapolate reasonably into the NaNs. Could you use it to fill the NaNs with non-Nans and then do a gridded interpolation once the NaNs are filled in?

[dominik]

The problem with that in my case is that my function goes towards infinity, and indeed is no defined where there are NaNs. Hence extrapolating to these points doesnt make much sense. So any value i put there is arbitrary, whereas triangualar interpolation should give me a good approximation. Think

   .1   1  1e4

    1  1e4 NaN 
      x
   1e4 NaN NaN

Then approximating at point x with triangular interpolation seems sensible. But i dont know what i would get if i had some extrapolated value in place of the NaN (NaN=undefined area of the function).

But maybe ill simply have to live with that imprecision.

[Matt J]

The problem with that in my case is that my function goes towards infinity, and indeed is no defined where there are NaNs.

How do you know it goes to infinity if you don't have a closed-form expression for what the image values are samples of? Or, if you do have a closed form expression, why not evaluate that at whatever locations you want, instead of interpolating?

[dominik]

Hey Matt, thanks for making the effort to try to understand my problem!

Well, unfortunatley I dont have a closed from solution, but i know the domain where the function is defined. And I can evaluate the function at any point using a complicate algorithm (basically solving a huge system of nonlinear equations). But this is very (prohibitively) time consuming (so i want to get the values of the function on some grid and then use an interpolant to save time).

By taking samples closer and closer to the boarder of the domain i observed the function seems to go to infinity (and this matches the intuition of what the function should do).

[Matt J]

Ah well. The partitioned approach you talked about in your post seems like the best one, then.