# 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. YOU KNOW ONLY LINES. Eschew curves. 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 :)
Note that this method is piecewise Affine (similar meaning as flat).
Simple and based.
## 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* (or A^t if it doesn't have complex numbers).
(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, in fact 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.