Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a several 3D vectors $X_{i}$ which lay approximately in a plane. Now I need to find a single vector, which is normal (as much as possible) to all of them.

For two vectors, I can use a cross product to obtain such vector.

For multiple vectors, I found this formula:

$$\left( \sum_{i=1}^{n} X_{i}X_{i}^{\textbf{T}} \right)u=0$$

Here $u$ is the desired vector (null vector of a covariance matrix).

Question: What is the reason behind this formula?

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

The formula you found will have no solution unless all the $X_i$ are actually in the same plane! Instead, you should find the $u$ that minimizes $u^T\big(\sum\limits_{i=1}^n X_i X_i^T\big)u$. This is the least-squares solution to requiring $X_i^Tu = 0$ for all $X_i$ (I can elaborate on this if you want). The desired $u$ is the eigenvector corresponding to the smallest eigenvalue of $\sum\limits_{i=1}^n X_i X_i^T$.

Define the $3\times n$ matrix $X$ whose columns are the vectors $X_i$. Then $\sum\limits_{i=1}^n X_iX_i^T=XX^T$, so we're trying to minimize $u^TXX^Tu=\lVert X^Tu\rVert^2$ for a unit vector $u\in\mathbb R^3$. The solution is the eigenvector of $XX^T$ corresponding to the smallest eigenvalue; equivalently, the right singular vector of $X^T$ ($=$ the left singular vector of $X$) corresponding to the smallest singular value. Finding singular vectors of $X$ is more numerically stable than computing $XX^T$ and finding its eigenvectors, so using the SVD is recommended.

share|improve this answer
    
The vectors are indeed not in the same plane and the system $Ax=0$ is regular, having only one solution which is the undesirable one ($x=\vec{0}$). From what I've read, the least-squares solution is also the right singular vector corresponding to the smallest singular value in SVD of $A$. I think this is the same as the eigenvector corresponding to smallest eigenvalue of $A$. Is that correct? –  Libor Jan 30 '13 at 9:50
    
@Libor: Almost. See my edit. Computing the SVD of $A=XX^T$ instead of of $X$, as in your comment, would also work, but that's no better than computing the eigendecomposition. –  Rahul Jan 30 '13 at 19:08
    
Thanks. Both methods work as you said, so I have chosen the one you provided as more numerically stable. Just if you are curious: I have used the method to automatically straighten panoramic image mosaics like this one. –  Libor Jan 30 '13 at 22:08
add comment

You can think of the eigen-vectors of the covariance matrix as spanning the vector field, and therefore you choose the null vector which is orthogonal to the said field.

The method is called Principal Component Analysis (PCA) and wikipedia has a bit more about the derivation.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.