Direct linear transformation

Example

Suppose that ${\displaystyle k\in \{1,...,N\}}$. Let ${\displaystyle {\mathbf{x}}_k=(x_{1k},x_{2k})\in {\mathbb{R}}^2}$ and ${\displaystyle {\mathbf{y}}_k=(y_{1k},y_{2k},y_{3k})\in {\mathbb{R}}^3}$ be two known vectors, and we want to find the ${\displaystyle 2\times 3}$ matrix ${\displaystyle \mathbf{A}}$ such that

${\displaystyle {\alpha }_k{\mathbf{x}}_k=\mathbf{A}{\mathbf{y}}_k}$

where ${\displaystyle {\alpha }_k\ne 0}$ is the unknown scalar factor related to equation k.

To get rid of the unknown scalars and obtain homogeneous equations, define the anti-symmetric matrix

${\displaystyle \mathbf{H}=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)}$

and multiply both sides of the equation with ${\displaystyle {\mathbf{x}}_k^T\mathbf{H}}$ from the left

${\displaystyle \begin{array}{cc}({\mathbf{x}}_k^T\mathbf{H}){\alpha }_k{\mathbf{x}}_k& =({\mathbf{x}}_k^T\mathbf{H})\mathbf{A}{\mathbf{y}}_k\\ {\alpha }_k{\mathbf{x}}_k^T\mathbf{H}{\mathbf{x}}_k& ={\mathbf{x}}_k^T\mathbf{H}\mathbf{A}{\mathbf{y}}_k\end{array}}$

Since ${\displaystyle {\mathbf{x}}_k^T\mathbf{H}{\mathbf{x}}_k=0,}$ the following homogeneous equations, which no longer contain the unknown scalars, are at hand

${\displaystyle {\mathbf{x}}_k^T\mathbf{H}\mathbf{A}{\mathbf{y}}_k=0}$

In order to solve ${\displaystyle \mathbf{A}}$ from this set of equations, consider the elements of the vectors ${\displaystyle {\mathbf{x}}_k}$ and ${\displaystyle {\mathbf{y}}_k}$ and matrix ${\displaystyle \mathbf{A}}$:

${\displaystyle {\mathbf{x}}_k=\left(\begin{array}{c}{x}_{1k}\\ x_{2k}\end{array}\right)}$, ${\displaystyle {\mathbf{y}}_k=\left(\begin{array}{c}{y}_{1k}\\ y_{2k}\\ y_{3k}\end{array}\right)}$, and ${\displaystyle \mathbf{A}=\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\end{array}\right)}$

and the above homogeneous equation becomes

${\displaystyle 0=a_{11}{x}_{2k}{y}_{1k}-a_{21}{x}_{1k}{y}_{1k}+a_{12}{x}_{2k}{y}_{2k}-a_{22}{x}_{1k}{y}_{2k}+a_{13}{x}_{2k}{y}_{3k}-a_{23}{x}_{1k}{y}_{3k}}$ for ${\displaystyle k=1,\dots ,N.}$

This can also be written in the matrix form:

${\displaystyle 0={\mathbf{b}}_k^T\mathbf{a}}$ for ${\displaystyle k=1,\dots ,N}$

where ${\displaystyle {\mathbf{b}}_k}$ and ${\displaystyle \mathbf{a}}$ both are 6-dimensional vectors defined as

${\displaystyle {\mathbf{b}}_k=\left(\begin{array}{c}{x}_{2k}{y}_{1k}\\ -x_{1k}{y}_{1k}\\ x_{2k}{y}_{2k}\\ -x_{1k}{y}_{2k}\\ x_{2k}{y}_{3k}\\ -x_{1k}{y}_{3k}\end{array}\right)}$ and ${\displaystyle \mathbf{a}=\left(\begin{array}{c}{a}_{11}\\ a_{21}\\ a_{12}\\ a_{22}\\ a_{13}\\ a_{23}\end{array}\right).}$

So far, we have 1 equation and 6 unknowns. A set of homogeneous equations can be written in the matrix form

${\displaystyle \mathbf{0}=\mathbf{B}\mathbf{a}}$

where ${\displaystyle \mathbf{B}}$ is a ${\displaystyle N\times 6}$ matrix which holds the known vectors ${\displaystyle {\mathbf{b}}_k}$ in its rows. The unknown ${\displaystyle \mathbf{a}}$ can be determined, for example, by a singular value decomposition of ${\displaystyle \mathbf{B}}$; ${\displaystyle \mathbf{a}}$ is a right singular vector of ${\displaystyle \mathbf{B}}$ corresponding to a singular value that equals zero. Once ${\displaystyle \mathbf{a}}$ has been determined, the elements of matrix ${\displaystyle \mathbf{A}}$ can rearranged from vector ${\displaystyle \mathbf{a}}$. Notice that the scaling of ${\displaystyle \mathbf{a}}$ or ${\displaystyle \mathbf{A}}$ is not important (except that it must be non-zero) since the defining equations already allow for unknown scaling.

In practice the vectors ${\displaystyle {\mathbf{x}}_k}$ and ${\displaystyle {\mathbf{y}}_k}$ may contain noise which means that the similarity equations are only approximately valid. As a consequence, there may not be a vector ${\displaystyle \mathbf{a}}$ which solves the homogeneous equation ${\displaystyle \mathbf{0}=\mathbf{B}\mathbf{a}}$ exactly. In these cases, a total least squares solution can be used by choosing ${\displaystyle \mathbf{a}}$ as a right singular vector corresponding to the smallest singular value of ${\displaystyle \mathbf{B}.}$

More general cases

The above example has ${\displaystyle {\mathbf{x}}_k\in {\mathbb{R}}^2}$ and ${\displaystyle {\mathbf{y}}_k\in {\mathbb{R}}^3}$, but the general strategy for rewriting the similarity relations into homogeneous linear equations can be generalized to arbitrary dimensions for both ${\displaystyle {\mathbf{x}}_k}$ and ${\displaystyle {\mathbf{y}}_k.}$

If ${\displaystyle {\mathbf{x}}_k\in {\mathbb{R}}^2}$ and ${\displaystyle {\mathbf{y}}_k\in {\mathbb{R}}^q}$ the previous expressions can still lead to an equation

${\displaystyle 0={\mathbf{x}}_k^T\mathbf{H}\mathbf{A}{\mathbf{y}}_k}$ for ${\displaystyle k=1,\dots ,N}$

where ${\displaystyle \mathbf{A}}$ now is ${\displaystyle 2\times q.}$ Each k provides one equation in the ${\displaystyle 2q}$ unknown elements of ${\displaystyle \mathbf{A}}$ and together these equations can be written ${\displaystyle \mathbf{B}\mathbf{a}=\mathbf{0}}$ for the known ${\displaystyle N\times 2q}$ matrix ${\displaystyle \mathbf{B}}$ and unknown 2q-dimensional vector ${\displaystyle \mathbf{a}.}$ This vector can be found in a similar way as before.

In the most general case ${\displaystyle {\mathbf{x}}_k\in {\mathbb{R}}^p}$ and ${\displaystyle {\mathbf{y}}_k\in {\mathbb{R}}^q}$. The main difference compared to previously is that the matrix ${\displaystyle \mathbf{H}}$ now is ${\displaystyle p\times p}$ and anti-symmetric. When ${\displaystyle p>2}$ the space of such matrices is no longer one-dimensional, it is of dimension

${\displaystyle M=\frac{p(p-1)}{2}.}$

This means that each value of k provides M homogeneous equations of the type

${\displaystyle 0={\mathbf{x}}_k^T{\mathbf{H}}_m\mathbf{A}{\mathbf{y}}_k}$ for ${\displaystyle m=1,\dots ,M}$ and for ${\displaystyle k=1,\dots ,N}$

where ${\displaystyle {\mathbf{H}}_m}$ is a M-dimensional basis of the space of ${\displaystyle p\times p}$ anti-symmetric matrices.

Example p = 3

In the case that p = 3 the following three matrices ${\displaystyle {\mathbf{H}}_m}$ can be chosen

${\displaystyle {\mathbf{H}}_1=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& -1\\ 0& 1& 0\end{array}\right)}$, ${\displaystyle {\mathbf{H}}_2=\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 0\\ -1& 0& 0\end{array}\right)}$, ${\displaystyle {\mathbf{H}}_3=\left(\begin{array}{ccc}0& -1& 0\\ 1& 0& 0\\ 0& 0& 0\end{array}\right).}$

In this particular case, the homogeneous linear equations can be written as

${\displaystyle \mathbf{0}=[{\mathbf{x}}_k{]}_{\times }\mathbf{A}{\mathbf{y}}_k}$ for ${\displaystyle k=1,\dots ,N}$

where ${\displaystyle [{\mathbf{x}}_k{]}_{\times }}$ is the matrix representation of the vector cross product. Notice that this last equation is vector valued; the left hand side is the zero element in ${\displaystyle {\mathbb{R}}^3}$.

Each value of k provides three homogeneous linear equations in the unknown elements of ${\displaystyle \mathbf{A}}$. However, since ${\displaystyle [{\mathbf{x}}_k{]}_{\times }}$ has rank = 2, at most two equations are linearly independent. In practice, therefore, it is common to only use two of the three matrices ${\displaystyle {\mathbf{H}}_m}$, for example, for m=1, 2. However, the linear dependency between the equations is dependent on ${\displaystyle {\mathbf{x}}_k}$, which means that in unlucky cases it would have been better to choose, for example, m=2,3. As a consequence, if the number of equations is not a concern, it may be better to use all three equations when the matrix ${\displaystyle \mathbf{B}}$ is constructed.

The linear dependence between the resulting homogeneous linear equations is a general concern for the case p > 2 and has to be dealt with either by reducing the set of anti-symmetric matrices ${\displaystyle {\mathbf{H}}_m}$ or by allowing ${\displaystyle \mathbf{B}}$ to become larger than necessary for determining ${\displaystyle \mathbf{a}.}$