Determine in an interpolation the contribution of each node nearby

Hello,

I applied an interpolation using the cubic spline on a set of points. Is there any possible way I can find the contribution of the neighbouring nodes to the interpolation in the location I'm on? I know all nodes affects the interpolation but basically I want to find for each node, what are the most significant nodes that are mostly affecting the interpolation.

Thank you

Answer 1

[John D'Errico]

The most significant nodes? The nearest neighbors to a given point. Beyond that, the significance will die off, probably exponentially in some way, though it will oscillate.

But what you ask is actually moderately easy. A cubic spline is linear in the values of the functions at the nodes. That is, you can solve for the coefficients of the cubic spline using a linear system of equations. Therefore, those coefficients are a linear function of the values of y at each data point. And then the prediction itself? Again, a linear combination of the coefficients, where the linear combination is itself not linear, but you don't really care about that. This tells you that you can do exactly what you are asking for in a simple way.

For example, consider the set of points

x = 1:10;
y = sin(x); % y can be ANYTHING you want here.

We could build a cubic spline on that support using spline.

spl = spline(x,y);

But now, suppose we were to perturb one data point, say, at x == 4? At that point, suppose we were to perturb the spline so at that point, we now have y(4)+dy? Leave ALL of the other data points alone.

The new spline, passing through that point will be just additive, as a sum of two splines.

y4p = zeros(size(x));
y4p(4) = 1;
spl4 = spline(x,y4p);
fnplt(spl4)
hold on
plot(x,y4p,'ro')
grid on

That is the perturbation introduced into a spline, as a function of a unit perturbation, applied at the point x==4.

Can you see that the influence of that point, on any point near it dies off as you move away from x==4? But as well, EVERY point has SOME influence on the value of the spline at all locations.

I think (hope) you can visualize how it will work. In fact, you could even build up the complete spline as a sum of terms like that. Think in terms of Green's functions. You can see there how each data point contributes to the value of the interpolant at any intermediate point. For example, try this:

nx = numel(x);
G = cell(1,nx);
for i = 1:nx
  y0 = zeros(1,nx);
  y0(i) = 1;
  G{i} = spline(x,y0);
end

Now we have a set of unit splines, that again, we should be able to build the complete spline from, IF we wanted to do so. But in terms of the contribution of any data point to some intermediate location x, we can now try this:

N = 100;
X = linspace(x(1),x(end),N);
nodalinfluence = zeros(nx,N);
for i = 1:nx
  nodalinfluence(i,:) = fnval(G{i},X);
end
% normalize the influences
nodalinfluence = abs(nodalinfluence)./sqrt(sum(nodalinfluence.^2,1));
mesh(nodalinfluence')
xlabel 'Node'
ylabel 'x'
view(20,70)

I'm not sure if that is what you would be asking for. But it should show the relative contribution of the value at each node to the interpolated function value at any given point along the curve.

This is different from modeling tools like pchip or makima, since they are nonlinear in a sense. Those tools will have ONLY the immediate 2 neighbors on both sides of a given point as being of influence, but even there, the relative influence is highest for the immediate neighbors, and it will decrease for the next pair of points further away. Again though, those tools are nonlinear functions of the value of the curve at any node, so you will not find some nice additive process like a Green's function.

[Marc Abdel Nour]

Thank you so much for your help, but i have one more question.

In my code, I'm trying to interpolate only on the nodes that I have then calculate the error between the original function and the interpolated one on each node, so in that case my 'x' (x are the points in your code) are equal to number of nodes. So when I tried it on my code, it seems that mostly the only contribution is the node itself. I can't find this true, or maybe am i confused?

[Walter Roberson]

If I understand correctly you have a known point and you are asking to do spline interpolation at that point (taking into account the surrounding points), and you want to calculate the difference between the known point and the value that would be calculated for the same point?

If so, then the difference is expected to be small, and of course the point itself would register as the major influence at the same location.

Now if you were to do a spline interpolation based upon the data without the query point, and compare that to the actual known value there, that could potentially be interesting...

[John D'Errico]

You are confused. Interpolation ALWAYS returns exactly the original function value at EVERY data point. That is a basic characteristic of interpolation. As such, the ONLY point that has an influence on the value of the function is that point itself.

Interpolation is NOT smoothing. It is NOT approximation, where it changes the value of your function at the original data points.

Walter's comment gets at the idea of a "leave-one-out" cross-validation scheme, where you could use a spline to predict a missing point, where you delete each data point in turn and build a spline that interpolates the remainder of the points. But that is very different from a spline interpolant.

So even if you look at the code I wrote in my answer, if you looked very carefully, you would see an influence of 1 at every data point at the location of that data point, and at that point, every other data point has an influence of exactly 0. This was no mistake. Again, interpolation means exactly that.

Unfortunately, many people talk about interpolation, when in fact, they really mean modeling, smoothing, and approximation of some sort.

For example, we could consider the question of a straight line fit to a set of data, where now every data point has a non-zero influence on the value of the function at any point along the curve. Again, that is a case of approximation, NOT interpolation. Do not get them confused.

[Marc Abdel Nour]

Okay, I think things are clearer for me.

Thank you for your time and your assistance, was really helpful.

[Walter Roberson]

Interpolation could potentially differ slightly due to round-off error, depending on the implementation.

Answer 2

[Walter Roberson]

As an approximation, and restricted to the case where the x coordinates of the spline are strictly increasing:

If you were to interp1() the query x coordinate against the indices of the x coordinates asking for 'nearest'

num_x = length(spline)x);
query_y = interp1(spline_x, spline_y, 'spline')
idx = interp1(spline_x, 1:num_x, query_x, 'nearest');

Now for idx > 1 & idx < num_x then spline_x(idx-1), spline_x(idx), spline_x(idx+1) and corresponding y values are three nearest nodes. From there you could calculate the distance between spline_x, spline_y to those three points, and use some kind of inverse distance to get weighting factors to give you an idea of how much the nodes contributed.

This will not be exact: to be exact you should take into account the derivative conditions.

Perhaps there is a better way by using spline() and pulling apart the piecewise polynomial.

@John D&#39;Errico knows splines much better than I do.