… Affine Transformations.
Note to myself (0).
Let’s say here are 2 sets of 2D points and , . Besides, corresponds to for each . What I want here is a nice affine transform that maps each to , such that sum of distances between mapped and is minimised. That is an affine transform that minimise this:
2. go calculus
In order for to take minimal value, it is necessary that is stationary, i.e. all 1st partial derivatives of with respect to must be . Writing down the necessary conditions, I get:
Computing partial derivatives and simplifying (a bit tedious) lead to the 2 separate systems of 1st order equations:
(sums are over i = 0 to n-1).
Solving for gives me what I wanted, the “nice” affine transform.
3. go linear algebra
Let’s imagine an ideal situation where the mapped points coincide with , i.e.
for each . This can be rewritten as 2 systems of equations as follows:
Except for this ideal situation, the equations above do not hold. I cannot equate LHS with RHS.
But the systems can give me a clue for looking at the problem from a different view point. Namely, LHS can be seen as a linear combination of 3 column vectors which spans 3-dimensional subspace of n-dimensional space. RHS is a vector also resides in the same n-dimensional space, but it is not, in general, on the 3-dimensional space spanned by LHS.
In the 3-dimensional space, the closest possible point to RHS is given by orthogonal projection from the RHS vector to the 3-dimensional space spanned by LHS. This projection line must be orthogonal to 3 column vectors of LHS matrix. Putting this condition into math expressions, I get:
These can be rewritten as
Computing matrix products, these equations result in the ones given in section 2.
As a computer programmer myself, a nice thing about this approach is that I can do away with some computation by hand which is a bit error prone, provided that I have a basic matrix operators and solvers at hand. Further more, with Householder transformer at hand, I can even dispose of matrx multiplier, which is my favourite way to go actually.