# 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 t
he simplest. YOU KNOW ONLY LINES. Eschew curves. And more degree i
s 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 s
paces.



## 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 backgr
ound should be white. Not in between like grey. This method is fan
tastic for categorical data like that.

P.S. It seems that anime-style drawings are categorical data. Near
est 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 som
e 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 in
f. 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 p
ixel 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 fun
ction, 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 migh
t 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 met
hod might result in blurry outcome. Because it uses grey too, not
only black & white.

But on average, this results in better outcomes than nearest neigh
bor 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) abo
ve, 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.




## Misc -- mpv.conf

Set these:

``````````````````````````````````````````````````````````````````
scale=nearest
cscale=nearest
tscale=nearest
dscale=nearest
``````````````````````````````````````````````````````````````````

or these:

``````````````````````````````````````````````````````````````````
scale=bilinear
cscale=bilinear
tscale=linear
dscale=bilinear
``````````````````````````````````````````````````````````````````

or mix them.