3d extrapolation of smooth function

I have a 3d set of evenly spaced points, at which I would like to evaluate some function. Evaluation of the function is costly. I am using a binary search to find the value of the function at each point, but my ability to bound the value (obviously?) impacts the speed in which I can find a sufficiently accurate answer. The function values are relatively smooth in my space, which means that I can try and bound the evaluation of a particular value by using values in the local neighborhood. Any suggestions?

For example I might have the following values, spaced evenly as such (in 2d for simplicity):

    1 2 3
    4 5 6
    7 8 x

What function could I use to evaluate x?

Alternatively I might have

1 2 3 4
4 5 6 7
8 9 x

Which is similar to above, but just goes to point out that I might not always be dealing with a corner.

Thanks! Jim

[Matt J]

Wouldn't we have to study the specific form of your function in order to derive a valid bound for it?

[Jim Hokanson]

My question was more so aimed at existing, generic methods, for extrapolating in 3d, given some assumptions about smoothness. In 1d interp1 will extrapolate. In 2d, I can use the fit function from the curve fitting toolbox. I could also use interp2 but it wouldn't be able to take advantage of neighboring information such as is presented in my examples.

What about in 3d?

Answer 1

[Matt J]

See also the various 'inpaint_nan' contributions on the FEX:

http://www.mathworks.com/matlabcentral/fileexchange/27994

Answer 2

[Image Analyst]

Well in 1D, like your example, I'd use sgolay() - the Savitzky Golay filter. But in 3D, I don't know.

So to make sure I understand the situation let me try to visualize an example. Let's say you have a 3D volumetric array, like a CT or MRI image of a skull. You have an X, a Y, and a Z coordinate and the array at that location has a value. But let's say you had only half a skull and you want to extrapolate based on the curvature of the existing half skull to complete the skull in 3D. So you'd have all the x,y,z coordinates and values for all those coordinates. Maybe it's not a medical image but it's some sort of 3D array. So is that basically what you're wanting to do?

[Jim Hokanson]

In this case I am running a neural model and trying to determine threshold in a 3d space. At any given new point I am trying to find threshold, and the closer I am to the answer when I start, the less halving I need to do.

[Image Analyst]

What are you starting with? Do you have a 3D array of numbers, or an analytical formula F(x,y,z)? Or both? If you have the function, just plug in the extrapolated coordinates. If you have an empirical, experimentally measured numerical array but no underlying analytical formula then you basically have to make some kind of educated guess at what the values would be, or maybe first what the formula would be so you can then guess at the values.

Answer 3

[Matt J]

If you're trying to grow the array by extrapolation, a linear algebraic cubic spline extrapolation approach is given below. It employs a couple of my FEX files

http://www.mathworks.com/matlabcentral/fileexchange/26292-regular-control-point-interpolation-matrix-with-boundary-conditions

http://www.mathworks.com/matlabcentral/fileexchange/25969-efficient-object-oriented-kronecker-product-manipulation

And now the code:

 N=10; %array dimension;

%%In 1D

fakedata=(1:N).'; %to be extrapolated

spline_samples=[1 4 1]/6;

E=interpMatrix(spline_samples,'max',N+2);  %extrapolation operator
 E(:,2)=E(:,1)+E(:,2);
 E(:,end-1)=E(:,end)+E(:,end-1);
 E(:,[1,end])=[];

   F=E(2:end-1,:);  %fitting operator

extrapolated1D=E*(F\fakedata),

%%Generalization to 3D

fakedata=rand(N,N,N); 

F3=KronProd({F},[1 1 1]);
E3=KronProd({E},[1 1 1]);

extrapolated3D=E3*(F3\fakedata);