# Singular property of E and algorithm
Some properties of the E matrix in two-view motion estimation. Huang and Faugeras 1989.
## Theorem 1
A $3\times 3$ matrix $B$ can be decomposed into $B=TR$, where $T$ is a $3\times 3$ skew-symmetric matrix and R is a $3\times 3$ rotation matrix (orthogonal matrix), if and only if one of its singular values is zero and the other two are eqaul.

### Proof
#### Necessity
Assume that $B=TR$, where $T$ is a skew-symmetric matrix and $R$ is a rotation. Then we can find an orthonormal matrix Q such that [[1]](https://en.wikipedia.org/wiki/Skew-symmetric_matrix#Spectral_theory)

$$ T = Q^\intercal
\begin{bmatrix}
0 & \phi & 0\\
-\phi & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
Q
$$
where $\phi$ is a real constant. Thus

$$
B^\intercal B = R^\intercal T^\intercal TR = R^\intercal
Q^\intercal
\begin{bmatrix}
\phi^2 & 0 & 0\\
0 & \phi^2 & 0\\
0 & 0 & 0
\end{bmatrix}
Q R
$$
The singular values of $B$ are $\phi^2$, $\phi^2$ and $0$.

#### Sufficiency
Assume one of the singular values of $B$ is zero and the other two are equal. Then

$$
BB^\intercal = P^\intercal
\begin{bmatrix}
\phi^2 & 0 & 0\\
0 & \phi^2 & 0\\
0 & 0 & 0
\end{bmatrix}
P
$$
Let $A = PB = \begin{bmatrix} a_1 \\ a_2 \\ a_3 \end{bmatrix}$, so that
$$
AA^\intercal =
\begin{bmatrix}
\phi^2 & 0 & 0\\
0 & \phi^2 & 0\\
0 & 0 & 0
\end{bmatrix}
$$

we know that
$$
\begin{align*}
a_1 \cdot a_1 &= \phi^2 & a_1 \cdot a_2 &= 0 \\
a_2 \cdot a_2 &= \phi^2 & a_2 \cdot a_3 &= 0 \\
a_3 \cdot a_3 &= 0 & a_3 \cdot a_1 &= 0
\end{align*}
$$

Here we try to build a rotation matrix $A'$ that is based on $A$, letting $A' = \begin{bmatrix} a_1 \\ a_2 \\ a_3' \end{bmatrix}$ where $a_3' = a_1 \times a_2 / \phi$. Notice that $A' / \phi$ is a rotation matrix.

$$
\begin{bmatrix}
\phi^2 & 0 & 0\\
0 & \phi^2 & 0\\
0 & 0 & 0
\end{bmatrix}
A' =
\phi^2 \begin{bmatrix} a_1 \\ a_2 \\ 0 \end{bmatrix}
= \phi^2 A
$$
We can decomposite the matrix

$$
\begin{bmatrix}
\phi^2 & 0 & 0\\
0 & \phi^2 & 0\\
0 & 0 & 0
\end{bmatrix} =
\begin{bmatrix}
0 & -\phi^2 & 0\\
\phi^2 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0\\
-1 & 0 & 0\\
0 & 0 & 1
\end{bmatrix}
$$

Combines the two equation we can get
$$
\begin{equation}
\begin{split}
B = P^\intercal A &= P^\intercal
\frac{1}{\phi^2}
\begin{bmatrix}
\phi^2 & 0 & 0\\
0 & \phi^2 & 0\\
0 & 0 & 0
\end{bmatrix}
A' \\
&= P^\intercal
\frac{1}{\phi^2}
\begin{bmatrix}
0 & -\phi^2 & 0\\
\phi^2 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0\\
-1 & 0 & 0\\
0 & 0 & 1
\end{bmatrix}
A' \\
&= P^\intercal
\frac{1}{\phi^2}
\begin{bmatrix}
0 & -\phi^2 & 0\\
\phi^2 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
P P^\intercal
\begin{bmatrix}
0 & 1 & 0\\
-1 & 0 & 0\\
0 & 0 & 1
\end{bmatrix}
A' \\
&= TR
\end{split}
\end{equation}
$$

where
$$
T = \frac{1}{\phi} P^\intercal
\begin{bmatrix}
0 & -\phi^2 & 0\\
\phi^2 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
P
$$
is a skew-symmetric matrix and
$$
R = P^\intercal
\begin{bmatrix}
0 & 1 & 0\\
-1 & 0 & 0\\
0 & 0 & 1
\end{bmatrix} \frac{1}{\phi} A'
$$
is a orthonormal matrix and thus a rotation matrix.

## Compute F by 8-point algorithm
Define $x^1_i = (x^1_i, y^1_i, 1)^\intercal$ and $x^2_i = (x^2_i, y^2_i, 1)^\intercal$ are the $i$-th corresponding point in two different view. According to F we have,
$$x_i^{2\intercal} F x^1_i = 0$$
We can then build $f = (F_{11}, F_{12}, F_{13}, F_{21}, F_{22}, F_{23}, F_{31}, F_{32}, F_{33})^\intercal$ which is the vector form of $F$ and let

$$
Af = \begin{bmatrix}
x^1_1 x^2_1 & x^2_1 y^1_1 & x^2_1 & y^2_1 x^1_1 & y^2_1 y^1_1 & y^2_1 & x^1_1 & y^1_1 & 1 \\
\vdots &&&&\dots&&&& \vdots\\
x^1_n x^2_n & x^2_n y^1_n & x^2_n & y^2_n x^1_n & y^2_n y^1_n & y^2_n & x^1_n & y^1_n & 1 \\
\end{bmatrix} f = 0
$$

This is a homogeneous set of equations. We can then derive a solution of $f$ given 8 corresponding points ignoring the scale of $f$.

### Enforce singularity constraint
Since $F = [T]_\times R$ and $[T]_\times$ is a skew-symmetric matrix, by theorem 1, we know that one of the singular values of $F$ is zero and the other two are equal. However, in real case, this constraint usually is not satisfied. Therefore,
$$
\min_{F'} ||F-F'||_F
$$
such that $F'$ satisfy the constraint.

With SVD let $F=Udiag(r,s,t)V^\intercal$ where $r\geq s \geq t$, we then set $F' = Udiag(1,1,0)V^\intercal$. Notice that the scale of $F$ or $F'$ does not effect the result.