Revision 4775287a8e1222466b0f3e38cebdd16c71704539 (click the page title to view the current version)

Learning and Proof

Changes from 4775287a8e1222466b0f3e38cebdd16c71704539 to current

title: Learning and Proof
categories: lecture

# Reading

+ Steinert, M., & Leifer, L. J. (2012). 'Finding One's Way': Re-Discovering a Hunter-Gatherer Model based on Wayfaring. International Journal of Engineering Education, 28(2), 251.
+ Ma 2004:Ch 5.1

# Learning and Study Technique

## Learning Outcomes.

1.  The Learning Outcome is **not** a set of well-defined procedures
    to be copied.
2.  Textbook procedures work on textbook problems.
3.  We need the theoretical understanding to adapt existing theory to
    new situations.

Hence, *aim for understanding over working code*.

## Constructivist Learning Theory

1.  Learning is **constructed by the learner**.
2.  Knowledge has to be reinterpreted in your own personal context
    - based on experience
    - ... and on ambition
    - ... and on background knowledge

Hence, seek to extend concepts and techniques with which
*you are familiar*.

## Learning is Design

1.  Learning is no different from design and development.
2.  There is always some problem or situation that we need to make sense
3.  In design, there is an ill-defined problem to comprehend.
4.  In learning, there is a body of knowledge to make sense of.

## The Hunter-Gatherer Model

1.  There are many good models to explain how we design, and how we
2.  E.g. Simon, Gadamer, Schön
3.  The Hunter-Gatherer Model of Steinert and Leifer.
4.  **Hunt** for the next big idea.
    +  Look for clues, interpret the clues, guess, test your hunches, 
       discover new clues, and iterate.
6.  Then **gather** the ideas
    + skin and partition the beast
    + assemble the ideas into a prototype/proof/presentation 
      to bring home.
7.  Big ideas in learning are known as threshold concepts,
    + tricky to learn
    + but once learnt they explain and give meaning to a large body
      of theory and knowledge
    + approach difficult concepts from different angles
    + test (intermediate) ideas, through implementation, argument,
      prediction, or otherwise

# Relative Pose

## Repetition 

### 3D Motion

+ Rotation by angle $\theta$ around the vector $\omega$ is given
  by $R=e^{\hat\omega\theta}$ assuming $\omega$ has unit length.

**Rodrigues' formula** (2.16)

$$e^{\hat\omega} =
  I + \frac{\hat\omega}{||\omega||}\sin(||\omega||)
    + \frac{\hat\omega^2}{||\omega||^2}(1-\cos(||\omega||))$$

See [Angular Motion]() for a more comprehensive summary.

### Basic Result on Relative Pose

+ Theorem 5.5

$$E = U\mathsf{diag}\{\sigma,\sigma,0\}V^T,$$
where $U,V\in\mathsf{SO}(3)$

+ Tricky proof.  Do not spend too much time on this.

  (\hat T_1,R_1) &=
  (UR_Z(+\frac\pi2)\Sigma U^T, UR_Z(+\frac\pi2)V^T)
  (\hat T_2,R_2) &=
  (UR_Z(-\frac\pi2)\Sigma U^T, UR_Z(-\frac\pi2)V^T)
$$R_Z(+\frac\pi2) = 
\begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}
is a rotation by $\pi/2$ radians around the $z$-axis.

+ Note that there are two solutions from one $U\Sigma V^T$ decomposition.
+ Are there more solutions?
+ $E = \hat TR$ where $(T,R)$ is the transformation between camera frames.
+ $E = U\mathsf{diag}\{\sigma,\sigma,0\}V^T,$
  where $U,V\in\mathsf{SO}(3)$
+ $(\hat T,R) = (UR_Z(\pm\frac\pi2)\Sigma U^T, UR_Z(\pm\frac\pi2)V^T)$
  $R_Z(\theta)$ is a rotation around the $z$-axis by an angle $\theta$

> There exist exactly two relative poses $(R,T)$ with $R\in\mathsf{SO}(3)$
  and $T\in\mathbb{R}^3$ corresponding to a nonzero essential matrix
  [Theorem 5.7]

## Proofs and Understanding

### Theorem 5.7
The Proof of Theorem 5.7 depends on Lemma 5.6.

+ **Demo** read the proof (debrief?)
1. Look at the main result, that is the theorem first;
do we understand what the theorem says?
2.  Note that the proof references Lemma 5.6, so let's
consider the proof of the lemma as an example.

### Lemma 5.6

> If $\hat T$ and $\hat TR$ are both skew-symmetric for $R\in\mathrm{SO}(3)$,
  then $R$ is a rotation by angle $\pi$ around $T$.

+ **Demo** read the proof (debrief?)
+ Skew-symmetry gives $(\hat TR)^T=-\hat TR$
+ We also have $(\hat TR)^T=R^T\hat T^T=-R^T\hat T$
+ Hence $\hat TR = R^T\hat T$,
+ and since $R^T=R^{-1}$, we have 
  $$R\hat TR=\hat T$$
+ Write $R=e^{\hat\omega\theta}$ for some $\omega$ of unit length and some 
  $\theta$, to get
  $$e^{\hat\omega\theta}\hat Te^{\hat\omega\theta}=\hat T$$
+ multiply by $\omega$
  $$e^{\hat\omega\theta}\hat Te^{\hat\omega\theta}\omega=\hat T\omega$$
  This represents a stationary rotation of the vector $\hat T\omega$.

Note that $\omega$ is stationary under rotation by $R$, and hence
it is an eigenvector associated with eigenvalue 1.
Furthermore, it is the only such eigenvector, and $\hat T\omega$
cannot be such.  Hence $\hat T\omega=T\times\omega=0$.
This is only possible if $T\sim\omega$, and since $\omega$ has
unit length, we get 
$$\omega = \pm\frac{T}{||T||}$$

We now know that $R$ has to be a rotation around $T$, and therefore
$R$ and $T$ commute.  This can be checked in Rodrigues' formula
(Theorem 2.9). 

Hence $R^2\hat T = \hat T$.
This looks like two half-round rotations to get back to start.
If $\hat T$ had been a vector or a matrix of full rank, we would
have been done.  However, with the skew-symmetric $\hat T$ there
is a little more fiddling.

# Debrief

We discussed the proof of Theorem 5.7 in the briefing.  After having proved the theorem, the proof gives the two formulæ for calculating $(\hat T,R)$ without saying how, and I could not see straight away how the author reasoned.

This kind of result is usually proved easily by showing that the solution is valid.  That is, we take the postulated expressions
$$\hat T = U R_+ \Sigma U^T$$
$$R = UR_+ V^T$$
and insert into the expression $E=\hat TR$.  If the formula is correct, we should then get $E=U\Sigma V^T$ to match the definition of  $U$, $\Sigma$, and $V$.  This gives us
$$\hat TR = U R_+ \Sigma U^T\cdot UR_+ V^T$$

+ This is not entirely unlike $E=U\Sigma V^T$, but we have two many factors.
+ Looking up SVD on wikipedia, we learn that when we decompose a real matrix $E$ (as opposed to a complex matrix), both $U$ and $V$ will be ortogonal.  Hence $U^TU=I$.

Thus we can simplify to get
$$\hat TR = U R_+ \Sigma R_+ V^T$$

+ We still have some superfluous rotation matrices.

Let's look at the middle part $R_+ \Sigma R_+$.  Inserting actual matrices, this is
  0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 
  1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 
  0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 
\end{bmatrix} = 
  -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 0
\end{bmatrix} = -\Sigma
Hence $\hat TR = -U\Sigma V^T$ which is correct up to a scalar factor, which is as good as it gets.

We can make the same argument with a rotation of minus ninety degrees instead of plus ninety degrees, and we can also make it for the other two formulæ on page 122 in Ma (2004), using different rotations in $\hat T$ and  $R$.