# How To Interpolate
I don't care about complex methods which result in accurate data.
Keep it simple, stupid. So I will post only simple methods.
When you think about simplicity, you can agree that linearity is
the simplest. And more degree is not essentially better because of
Runge's phenomenon.
Suppose that the data set is
f(0) = 1
f(1) = 3
f(2) = 2
f(3) = 5
I will explain with the xy-plane, but you can apply to any other
spaces.
## Nearest Neighbor
f(x)
= 1 ( 0 <= x < 0.5)
= 3 (0.5 <= x < 1.5)
= 2 (1.5 <= x < 2.5)
= 5 (2.5 <= x <= 3 )
This is the simplest method. You almost don't need to compute.
I think that this method would be good if
### 1. The data is categorical
Think of text antialiasing. The text should be dark and the background
should be white. Not in between like grey. This method is fantastic
for categorical data like that.
P.S. It seems that anime-style drawings are categorical data.
Nearest neighborhood method results in better quality. It makes
sense because those use only few colors.
### 2. The function is at least uniformly continuous
If it's Lipschitz continuous, best. To explain what those mean,
(these are not rigorous definitions though)
* Lipschitz continuous: The slope is bounded. dy <= K * dx for some
K>=0.
* Uniformly continuous: The slope doesn't have to be bounded, but
dy itself doesn't go inf. (inf = infinity)
Ex) sqrt(x) isn't Lipschitz continuous since the slope goes inf as
x->0. But it is uniformly continuous since dy itself doesn't go
inf. It's just that dy is much larger than dx where x->0.
Ex) 1/x isn't uniformly continuous since dy goes inf as x->0. Thus
it isn't Lipschitz continuous too.
So these basically mean that if x1, x2 are near, then f(x1), f(x2)
are near, GLOBALLY. If it's locally, that's just the definition of
continuity. This method is good for that kind of situations.
### 3. You don't give a fuck about the quality and just want speed
But remember, this method makes the function into a mosaic. Or a
pixel art. Well, pixel arts are good actually :)
## Linear
f(x)
= 2x + 1 (0 <= x < 1)
= -x + 4 (1 <= x < 2)
= 3x - 4 (2 <= x <= 3)
so that f(0)=1, f(1)=3, f(2)=2, f(3)=5.
For a bilinear version,
f(x0, y0)
= f(x0)_y=y0
= f(y0)_x=x0
where
f(x)_y=y0: X -> F,
f(y)_x=x0: Y -> F,
f(x)_y=y0 = f(x, y0),
f(y)_x=x0 = f(x0, y).
F means a Field. Like C, R, Zp.
This means making two 1-variable functions, not one 2-variable
function, by fixing x=x0 or y=y0. And both are piecewise linear
like f(x) above.
This is simple and best. If the data is not categorical, this might
be the best option. The error depends on f'', i.e. the curvature.
So the error is larger when the function is curvier.
If the data is categorical, like text antialiasing above, this
method might result in blurry outcome. Because it uses grey too.
Not only black & white.
But on average, this results in better outcomes than nearest neighbor
method. And there are still not many calculations.
## Least square
Use only when there is definitely a pattern.
I don't want to explain all those basic(?) linear algebra. So I'll
just write the method.
Suppose you have an overdetermined (more equations than variables)
system,
Ax = b (as a matrix equation).
Then multiply A* (Muh duality).
(A*)Ax = (A*)b
Then multiply the inverse.
x = [(A*)A]^-1 * (A*)b
This is the optimal solution.
Ex) Since the data set (x,f(x)) was (0,1), (1,3), (2,2), (3,5)
above, set
|1 0| |1|
|1 1| |3| |c'|
A = |1 2| , b = |2|, x = |c | . (A is a Vandermonde matrix)
|1 3| |5|
Then with some calculations,
|4 6 | |c'| |11|
|6 14| * |c | = |22| ((A*)Ax = (A*)b)
[4 6 | 11]
[6 14 | 22] (just do some Gaussian elimination)
[1 0 | 1.1]
~ [0 1 | 1.1] (I did it for you guys)
so c'=1.1, c=1.1.
Therefore
f(x)
= cx + c'
= 1.1 * x + 1.1
is the line which minimizes the sum of squared residuals (~errors)
. So use this line to interpolate.
There are things like the error following a normal distribution,
&c. If you want to know those things, read some regression analysis
books. Also, you can use least square for nonlinear cases. But keep
it simple and stay linear until you can't. You can still use those
piecewise linear functions of linear interpolation.