Paper: R. Hartly, "In Defence of the 8-point Algorithm," GE-Corpoate Research Dev.

Summary

1. The 8-point algorithm is the algorithm that solve Eipolar matrix estimation problem.
2. But it is susceptible to noise.
3. The paper refer to basic 8-point algorithm and it's numerical constraint called The singularity constraint related to Singular Value Decomposition.(Reduce Rank of least singular value)
4. The important sections of this paper are after Section 3. These are the main ideas.
5. Section 4. Condition Number
   1. From Interlacing Property, Symmetric matrix has some relation between eigenvalues of Submatrix.
   2. $trace(A)= \sum_{i=1}^N\lambda_i$
   3. Suppose $X=A^TA$, $X_r$ is the trailing $r\times r$ principal submatrix $A^TA$ and by $\lambda_i(X_r)$ its $i-th$ largest eigenvalue. Thus, $X_9=A^TA$ and $\kappa=\lambda_i(X_9)/\lambda_8(X_9)$.
   4. Suppose we have image point form $u=(100,100,1)$ if $u'=u$. we got some row of equation matrix $A$ like $\bold a_i=u\otimes u'=(10^4, 10^4, 10^2, 10^4, 10^4, 10^2, 10^2, 10^2, 1)$.
   5. Summing over all point correspondences will result in a matrix $A^TA$ for which the diagonal entries are approximately in this portion.
   6. The contribution to the matrix $A^TA$ is of the form $\bold {rr}^T$, which will contain entries ranging between $10^8$ and 1. For instance, the diagonal entries of $A^TA$ will be $(10^8, 10^8, 10^4, 10^8, 10^8, 10^4, 10^4, 10^4, 1)$.
   7. First we consider the eigenvalues of $trace(X_2)=10^4+1$.
   8. Since the matrix is positive semi-definite, both eigenvalues are non-negative, so we may deduce that $\lambda_1(X_2)≤10^4+1$.
   9. From the interlacing Property, we deduce that $$\lambda_8(X_9)≤
   10. $Ah=0$이 안정적인 해를 가지려면, $A^TA$가 보다 좋은 condition number를 가져야 한다.
       1. $||A||F=\Sigma{i=1}^9\sqrt{diag(A^TA)i}=\begin{pmatrix}\Sigma{i=1}^9d_i^2\end{pmatrix}^{1/2}$이기 때문에, $\kappa$가 매우 크면, $d_8$은 Frobenius norm의 매우 작은 영향을 끼친다.
       2. $d_8$이 노이즈에 의하여 변화가 생겨도 $A^TA$에는 상대적으로 작은 변화를 가져온다.
          1. $A^TA=d_1 x_1x_1^T+...+d_8x_8x_8^T+...$에서 $d_8$이 매우 작으면 $x_8x_8^T$의 영향이 작아짐
       3. Condition number가 커지면 $Ah=0$의 해인 $h$의 변화도 커지기 때문에 Least eigenvector에 큰 변화를 가져온다.

Supplimentary

Eigenvalue Interlacing Theorem(Interlacing Property).

Suppose $A\in{\rm I\!R}^{n\times n}$ is symmetric, Let $B\in{\rm I\!R}^{m\times m}$ with $m<n$ be a principal matrix.

Suppose A has eigen values $\lambda_1 ≤... ≤ \lambda_n$ and $\beta_1 ≤... ≤ \beta_m$. Then,

$$ \lambda_k ≤\beta_k ≤\lambda_{k+n-m} \text{ for }k=1,...,m. $$

And if $m=n-1$,

$$ \lambda_1 ≤\beta_1 ≤\lambda_2≤\beta_2≤...≤\beta_{n-1}≤\lambda_n. $$

Proof: WLOG, assume $A=\begin{bmatrix} B & X^T \\X & Z\end{bmatrix}$. Let $\{ x_1, ..., x_n\}$ be eigenvectors of $A$, $\{y_1, ..., y_m\}$ be eigenvectors of $B$. We define the following vector spaces:

$$ V=span(\bold{x_k, ..., x_n}), \ \ W=span(\bold{y_1, ...,y_k}), \tilde{W}\begin{Bmatrix}\begin{pmatrix}\bold w \\ \bold 0\end{pmatrix}\in {\rm I\!R}^{n}, \bold w \in W\end{Bmatrix} $$

Sine $dim(V)=n-k+1$ and $dim(\tilde{W})=dim(W)=k$, there exists $\tilde{w}\in V\cap \tilde W$ and $\tilde{w}=\begin{pmatrix} \bold w \\ \bold 0\end{pmatrix}$ for some $\bold w \in W$. Then

$$ \tilde{\bold w}^TA\tilde{\bold w}=\begin{bmatrix} \bold w^T & \bold 0^T\end{bmatrix} \begin{bmatrix} B & X^T \\ X & Z\end{bmatrix}\begin{bmatrix}\bold w \\ \bold 0\end{bmatrix}=\bold w^T B \bold w $$