Linear Interpolation (Interpolation, part I)

In a couple of different occasions I discussed the topic of interpolation, without really going into the details. Lately, I had to interpolate data and that got me interested (again) in interpolation; and I think I should share some of the things I learned.

In this first post (of a series), let us begin by the simplest interpolation of all (after constant interpolation): linear interpolation.

OK. So let us say we have a series of points, \{(x_i,y_i)\}_{i=1}^n coming from an unknown function y(x). (Of course, the following will generalize to any number of dimensions, but for the sake of simplicity, let us only consider time-series like data in two dimensions.) The goal of interpolation is to find a function \hat{y}(x) that yields a verisimilar approximation of y(x) (for various definitions of verisimilar). However, unlike fitting (a.k.a regression), the function \hat{y}(x) is not allowed to merely pass though the points while minimizing some average error; it must pass by the known points. That is, \hat{y}(x_i)=y_i if (x_i,y_i) is a known point.

The simplest possible such function is to use the last known value as an approximation. That is, \hat{y}(x)=x_i if x_i\leqslant{x}<x_{i+1}. Of course, it doesn't do that well, because it does not yield a smooth, pleasing curve, but a rather blockish approximation. We can refine this to "nearest neighbor" where \hat{y}(x) returns the y_j such that j=\arg\min \|x-x_j\|, that is, the y-value from the closest x_j in the series.

Next in complexity comes linear interpolation where we draw (virtually) a line between two consecutive points, and it is this line that will serve as an approximation to the underlying (and unknown) function that yielded the data points.

The schoolbook expression for a straight line is given by

\hat{y}(x)=a+bx,

where a is the base and b the slope. In the case of linear interpolation, the base and slope are determined by the points (x_i,y_i) and (x_{i+1},y_{i+1}), with x_i\leqslant{x}\leqslant{x_{i+1}}. We can rewrite the above as

\displaystyle\hat{y}(x)=y_i+\left(\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\right)(x-x_i),

where \displaystyle\left(\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\right) is the slope.

We can rearrange the equation slightly to get

\displaystyle\hat{y}(x)=y_i+\left(\frac{x-x_i}{x_{i+1}-x_i}\right)(y_{i+1}-y_i).

Now, the equation becomes the base, y_i, plus a smooth (but linear) variation between y_i and y_{i+1} controlled by x: a mix of y_i and y_{i+1}. Indeed: let’s get that result differently. Suppose we rewrite the linear interpolation as a blending of y_i and y_{i+1}:

\hat{y}(x)=(1-\alpha_x)y_i + \alpha_{x}y_{i+1},

where 0\leqslant\alpha_x\leqslant{1}. If put \displaystyle \alpha_x=\frac{x-x_i}{x_{i+1}-x_i}, we can expand the above to:

\displaystyle\hat{y}(x)=\left(1-\frac{x-x_i}{x_{i+1}-x_i}\right)y_i + \left(\frac{x-x_i}{x_{i+1}-x_i}\right)y_{i+1},

\displaystyle= y_i-\left(\frac{x-x_i}{x_{i+1}-x_i}\right)y_i+\left(\frac{x-x_i}{x_{i+1}-x_i}\right)y_{i+1}

\displaystyle= y_i + \left(\frac{x-x_i}{x_{i+1}-x_i}\right)(y_{i+1}-y_i).

So either way we look at it, we arrive at the same equation.

*
* *

Of course there are better ways of drawing a line between two points. Interpolation may be used to fill a continuum or only to get a few more points. The above formula is quite efficient enough to get just a few more points; maybe not so much to get a large number of points. In fact, I’m not sure what would be most (computationally efficient) way of generating a very large number of points between two known points. Likely precompute the slope and iterate varying only x using a finite-difference like method.

*
* *

Linear interpolation is simple, maybe too simple; as is has quite a limited expressiveness. Functions that we hypothesize to be smooth are rendered as a piecewise linear function, and for many applications, it creates objectionable artifacts (images linearly interpolated are ugly). Of course, a smooth interpolation that not only uses (x_i,y_i) and (x_{i+1},y_{i+1}) but also their neighbors ( (x_{i-1},y_{i-1}), (x_{i+2},y_{i+2}), etc., ) could capture more information about the (unknown) function and yield a smoother approximation.

Well, maybe we could fit something more flexible than a straight line through the points… maybe some polynomial?

To be continued…

3 Responses to Linear Interpolation (Interpolation, part I)

  1. […] a previous entry, we had a look at linear interpolation and concluded that we should prefer some kind of smooth […]

  2. […] previous posts, we discussed linear and cubic interpolation. So let us continue where we left the last […]

  3. […] the last four installments of this series, we have seen linear interpolation, cubic interpolation, […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: