Matrix search by optimization
I am looking for an algorithm to solve the following problem:
I have two sets of vectors and I want to find the matrix that best approximates the transformation from input vectors to output vectors.
vectors are 3x1, so a 3x3 matrix.
This is a common problem. My particular problem is that I have a set of RGB colors and another set that contains the color I want. I am trying to find an RGB conversion to RGB that will give me colors closer to what I want.
There is a correspondence between the input and output vectors, so calculating the error function that needs to be minimized is the easy part. But how can I minimize this feature?
source to share
You don't specify the language, but this is how I might address the problem in Matlab.
- v1 is a 3xn matrix containing your input colors in vertical vectors
- v2 is also a 3xn matrix containing your output colors.
Do you want to solve the system
M*v1 = v2 M = v2*inv(v1)
However, v1 is not directly invertible since it is not a square matrix. Matlab will solve this automatically using the mrdivide operation (M = v2 / v1), where M is the best solution.
eg:
>> v1 = rand(3,10);
>> M = rand(3,3);
>> v2 = M * v1;
>> v2/v1 - M
ans =
1.0e-15 *
0.4510 0.4441 -0.5551
0.2220 0.1388 -0.3331
0.4441 0.2220 -0.4441
>> (v2 + randn(size(v2))*0.1)/v1 - M
ans =
0.0598 -0.1961 0.0931
-0.1684 0.0509 0.1465
-0.0931 -0.0009 0.0213
This gives a more linguistic agnostic solution on how to solve the problem.
source to share
This is a classic linear algebra problem, and the search term is "multiple linear regression".
I've had to code some variations of this many times over the years. For example, the code for calibrating digitizer tablets or stylus touchscreen uses the same math.
Here's the math:
Let p be the input vector and q the corresponding output vector.
The required transformation is a 3x3 matrix; call it A .
For one input and output vector p and q, there is an error vector e
e = q - A x p
The squared error magnitude is a scalar value:
e T x e = ( q - A x p ) T x ( q - A x p )
(where the operator T is transposed).
What you really want to minimize is the sum of the e values over the sets:
E = sum ( e )
This minimum satisfies the matrix equation D = 0, where
D (i, j) = partial derivative of E with respect to A (i, j)
Let's say you have N input and output vectors.
Your set of input 3-vectors is a 3xN matrix; Call this matrix P . The i-th column of P is the i-th input vector.
So, a set of output 3-vectors; call this matrix Q .
When you grind all algebra, the solution is
A = Q x P T x ( P x P T) ^ -1
(where ^ -1 is the inverse operator - sorry for the lack of superscripts or indices)
Here's the algorithm:
Create a 3xN P matrix from a set of input vectors.
Create a 3xN Q matrix from a set of output vectors.
Matrix Multiply R = P x Transpose ( P )
Calculate inverse R
Matrix Multiplication A = Q x Transpose ( P ) x Inverse ( R )
using the matrix multiplication and matrix transformation routines of your chosen linear algebra library.
However, the 3x3 affine transformation matrix is capable of scaling and rotating the input vectors, but doesn't do any translation! This may not be enough for your problem. It is usually a good idea to add "1" to the end of each of the 3-vectors to then make a 4-vector and look for the best 3x4 transformation matrix that minimizes the error. It can't hurt; this can only lead to a better fit of the data.
source to share
Some linear algebra should suffice:
Write down the RMS difference between inputs and outputs (the sum of the squares of each difference between each input and output value). I am assuming this is the definition of "best approximation"
This is the quadratic function of your 9 unknown matrix coefficients.
To minimize it, output it for each of them.
You will get a linear system of 9 equations that you must solve to get a solution (unique or spatial diversity depending on the input dataset)
If the difference function is not quadratic, you can do the same, but you must use an iterative method to solve the system of equations.
source to share