Linear Algebra. Polynoms. Interpolation. Least squares

Want become an expert in Computer Vision & Object Detection?

Subscribe on New Practical Course

In this part of lectures we will talk about simplest “ml models” — polynoms.

that’s it — polynom

But alone polynoms is just some function, so we will also talk about Interpolation of them and will try to make ith with Least Squares method.

Let’s start from looking at magic:

Blue — polynom of 1st order, Green — polynom of 2nd order. Resulting Polynom coeffs [34. 2.11 3.14]

As we see we could interpolate our 2nd order polynom equation very precise(green line totaly cover red line).
With polynom of N order you can interpolate almost any function. The only exception is periodic functions because polynom is not periodic.

So what we can do with this thing? — For example we can use it to find out tone maping curves filter from two images.

This is per channel curves filter that u can find almost in any photo editor

This filter create function that modifies image per level + global values. This one of the filter that doesn’t decrese quality of photo(because this functions are continous, and thus very precise. the only limitation is a computer float size)

as we see images almost the same

So after we see these examples, let’s try to understand how interpolation works.
First of all, you should know that interpolation is basicaly any algorithm that trying to create new data from already seen data. So any ML algorithm is interpolation. Your brain working interpolating data every second of your life.
The only difereтсу between all of them is the level of difficulty.

Today we will talk about Least Square method, which we will be calculating using simple matrix operations(as basically all things in ML, if something is not matrix operation — that’s very bad, cause we cant use GPU on full power)

Our least squares interpolation can be defined as a system of m linear equations and n coefficents with m > n:

X — is Vandermonde matrix of our matrix x, which is basicaly geometric progression of value at every position. So if we have value 3 and 3rd order polynom then Vandermonde series for it will be 1, 3, 9, 27.

Our solution lies in solving this minimization problem

Which gives us equasion

In the code we can see small part that normilise input, we can pass it if norm images to [0,1] before running interpolation.

And for the end simple way to use interpolation to get style from image without it prior

So now you can try to make your own instagram filters just with few lines of code, or copy style of other.

Code

You can run all this code in Google Colab

Support

Become a Patron and support our community to make more interesting articles & tutorials

More cool things about Linear Algebra

Linear Algebra. Points matching with SVD in 3D space

Linear Algebra. SVD and PCA