Solving 3x3 Matrix Q using Nonlinear Least Squares or Cholesky Decomposition

I am trying to solve a system of equations using Cholesky decomposition. I would like to solve for the 3x3 matrix Q given:

$\hat{i_f}^t Q Q^t \hat{i_f} = 1$

$\hat{j_f}^t Q Q^t \hat{j_f} = 1$

$\hat{i_f}^t Q Q^t\hat{j_f} = 0$

where $\hat{i_f}$ and $\hat{j_f}$ are known 3x1 unit vector where $f=1,2,...,F$. Q is the unknown 3x3 matrix.

The literature commonly suggests using a linear method to solve for the 3x3 symmetric matrix $B$ where $B = QQ^t$. Thus the above system becomes:

$\hat{i_f}^t B \hat{i_f} = 1$

$\hat{j_f}^t B \hat{j_f} = 1$

$\hat{i_f}^t B \hat{j_f} = 0$

Notice that B has 6 unknowns due to its symmetric nature. However, it appears impossible to solve for 6 unknowns given 3 equations. Once B is known it is possible to find $Q$ using Cholesky decomposition.

Can anyone offer some advice as to how to solve for B in the above equations? If it helps, I plan on using the software package R to work through this problem. Thanks in advance and let me know if I need to be more clear in my question.

To give context to the problem, I am working on developing a structure from motion code using the R software. There is a wonderful paper that can be found here:

https://people.eecs.berkeley.edu/~yang/courses/cs294-6/papers/TomasiC_Shape%20and%20motion%20from%20image%20streams%20under%20orthography.pdf

that describes the structure from motion problem and a simple means to solve it. However, as my linear algebra is rusty, I am having difficulty solving the above (equation 16 in the referenced paper).

• Someone posted what seemed to be a very helpful answer to this question but now that answer is gone. Is it possible that I deleted it by accident? Hopefully I didn't! Jun 4, 2016 at 20:24
• No, @the_candyman deleted his own answer for some reason. Jun 4, 2016 at 20:55
• thanks @Omnomnomnom for the heads up. You wouldn't have any suggestions for solving this problem would you? Jun 4, 2016 at 23:53

Considering $B$ is a symmetric matrix, there are 6 unknowns. Thus, we need 6 equations. Currently the problem only lists 3 equations. If we write out the 3 equations from the problem in matrix form,

$\begin{bmatrix} i_{1f}&i_{2f}&i_{3f} \end{bmatrix} \begin{bmatrix}B_{11}&B_{12}&B_{13}\\B_{12}&B_{22}&B_{23}\\B_{13}&B_{23}&B_{33}\end{bmatrix} \begin{bmatrix} i_{1f}\\i_{2f}\\i_{3f} \end{bmatrix} =1$

$\begin{bmatrix} j_{1f}&j_{2f}&j_{3f} \end{bmatrix} \begin{bmatrix}B_{11}&B_{12}&B_{13}\\B_{12}&B_{22}&B_{23}\\B_{13}&B_{23}&B_{33}\end{bmatrix} \begin{bmatrix} j_{1f}\\j_{2f}\\j_{3f} \end{bmatrix} =1$

$\begin{bmatrix} i_{1f}&i_{2f}&i_{3f} \end{bmatrix} \begin{bmatrix}B_{11}&B_{12}&B_{13}\\B_{12}&B_{22}&B_{23}\\B_{13}&B_{23}&B_{33}\end{bmatrix} \begin{bmatrix} j_{1f}\\j_{2f}\\j_{3f} \end{bmatrix} =0$

there are not enough equations to solve for B if $f<2$. But if we consider that $f = 1,...,F$ we have an overdetermined system so long as $f > 2$. We can write this system in $Gm = D$ form as:

$G=\begin{bmatrix} i_{11}^2&i_{21}^2&i_{31}^2&2i_{11}i_{21}&2i_{11}i_{31}&2i_{21}i_{31}\\ i_{12}^2&i_{22}^2&i_{32}^2&2i_{12}i_{22}&2i_{12}i_{32}&2i_{22}i_{32}\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ i_{1F}^2&i_{2F}^2&i_{3F}^2&2i_{1F}i_{2F}&2i_{1F}i_{3F}&2i_{2F}i_{3F}\\ j_{11}^2&j_{21}^2&j_{31}^2&2j_{11}j_{21}&2j_{11}j_{31}&2j_{21}j_{31}\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ j_{1F}^2&j_{2F}^2&j_{3F}^2&2j_{1F}j_{2F}&2j_{1F}j_{3F}&2j_{2F}j_{3F}\\ i_{11}j_{11}&i_{21}j_{21}&i_{31}j_{31}&(i_{11}j_{21}+i_{21}j_{11}&(i_{11}j_{31}+i_{31}j_{11})&(i_{21}j_{31}+i_{31}j_{31})\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ i_{1F}j_{1F}&i_{2F}j_{2F}&i_{3F}j_{3F}&(i_{1F}j_{2F}+i_{2F}j_{1F}&(i_{1F}j_{3F}+i_{3F}j_{1F})&(i_{2F}j_{3F}+i_{3F}j_{3F})\\ \end{bmatrix}$

$m=\begin{bmatrix} B_{11}\\B_{22}\\B_{33}\\B_{12}\\B_{12}\\B_{23}\end{bmatrix}$ and $D=\begin{bmatrix} 1\\1\\\vdots\\1\\1\\\vdots\\1\\0\\\vdots\\0\end{bmatrix}$

As stated before, if $F>2$ this produces an overdetermined system and we can approximate $m$ with ordinary least squares

$m=(G^t G)^{-1} G^tD$