Minimizing the Frobenius norm for projecting on the essential space

266 Views Asked by At

In order to understand the eight-point algorithm I have some trouble with the proof of theorem 0.3 from https://cs.gmu.edu/~kosecka/it835/lect4.pdf in the first step.

The idea is to show that for a real matrix $F$, with SVD $F=U\operatorname{diag}(\lambda_1,\lambda_2,\lambda_3)V^T$ any essential matrix minimizing $\| E-F\|_f^2$ (Frobenius norm), has to have a solution of the form $U\operatorname{diag}(\sigma,\sigma,0)V^T =E$. In the proof it says that $$\lVert E-F\rVert_f^2=\operatorname{trace}(\Sigma_\lambda^2)+\operatorname{trace}(\Sigma^2)-2\operatorname{trace}(P\Sigma Q^T\Sigma_\lambda),$$

where $\Sigma_\lambda = \operatorname{diag}(\lambda_1,\lambda_2,\lambda_3)$, and $P,Q$ are rotation matrices with entries $p_{ij},q_{ij}$ respectively. From there on it is clear that in order to minimize the norm, we have to make $\operatorname{trace}(P\Sigma Q^T\Sigma_\lambda)$ as big as possible. But they are stating that the trace is equal to $$\sigma\bigl(\lambda_1(p_{11}q_{11}+p_{12}q_{12})+\lambda_2(p_{21}q_{21}+p_{22}q_{22})\bigr),$$ whereas I get $$\sigma\bigl(\lambda_1(p_{11}q_{11}+p_{12}q_{12})+\lambda_2(p_{21}q_{21}+p_{22}q_{22})+\lambda_3(p_{31}q_{31}+p_{32}q_{32})\bigr)$$ as a solution. My idea was that maybe $(p_{31}q_{31}+p_{32}q_{32})$ has to be $0$ if we choose the two terms by $\lambda_1$ and $\lambda_2$ to be $1$ (would make sense since $\lambda_1\geq\lambda_2\geq \lambda_3$). But i am not sure, why it has to be this way. \ Furthermore I am not sure, why $(p_{11}q_{11}+p_{12}q_{12})\leq 1$ and $(p_{21}q_{21}+p_{22}q_{22})\leq 1$ have to hold for the rotation matrices $P,Q$.

1

There are 1 best solutions below

0
On BEST ANSWER

I finally found a workaround:

according to the Eckart-Young-Mirsky theorem, the Frobenius norm $$\parallel F'-F\parallel_f^2$$ is minimized by a rank$-2$ matrix $F'$ for $F'=U\Sigma_\lambda'V^T$, where $\Sigma_\lambda'=diag(\lambda_1,\lambda_2,0)$. Thus the norm considered previously is minimized for $$\min_{E\in\mathcal{E}}\parallel E-F\parallel_f^2=\parallel\min_{E\in\mathcal{E}}\parallel E-F'\parallel_f^2-F\parallel_f^2$$ where $\mathcal{E}$ is the essential space. This means, that we are trying to minimize $\parallel E-F'\parallel_f^2$, which is just the same as in the proof above, but with the difference that we have to maximize the trace of $$P\Sigma Q^T\Sigma_\lambda'.$$ This is the same as $\sigma(\lambda_1(p_{11}q_{11}+p_{12}q_{12})+\lambda_2(p_{21}q_{21}+p_{22}q_{22}))$. Then we can continue as in the original proof.