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 am performing orthogonal distance regression on a set of points to find the best fit plane. I am using the method described on this page http://www.infogoaround.org/JBook/LSQ_Plane.html

The problem is that I end up with a linear homogenous system of the form:

Ax = 0

And I don't know a good computational way to solve this. (The author of the webpage says it is just an eigenvalue problem, but that looks nothing like an eigenvalue problem to me.)

A is a symmetric 3x3 matrix. I am writing some code to solve this (custom system so I can't use matrix libraries) and I'm not sure the best way to do it.

I would think there is a better/easier/more efficient method than Gauss-Jordan, but I don't know what that would be.

SVD seems to be promising, but the Wikipedia page makes it seem too intimidating to program!

Thanks

share|improve this question
    
Could you make explicit what $A$ is? If it is $3\times 3$, then solving the system should be fairly easy. –  Pedro Tamaroff Oct 4 '12 at 1:47
    
Are you looking for all x that solve this? you know x=0 is one solution right? –  Bitwise Oct 4 '12 at 1:56
    
A = {{Σ xi xi, Σ xi yi, Σ xi zi}, {Σ yi xi, Σ yi yi, Σ yi zi}, {Σ zi xi, Σ zi yi, Σ zi, zi}} for a set of n coordinates {xi, yi, zi} –  Nick Oct 4 '12 at 1:57
    
@Bitwise, I mention at the top of my post that I am trying to find a best-fit plane for a collection of points. So I'm afraid the trivial solution won't help me. –  Nick Oct 4 '12 at 1:58
    
X is in the span of eigenvectors which are associated with 0 eigenvalues. –  Tpofofn Oct 4 '12 at 1:59
add comment

2 Answers

up vote 2 down vote accepted

To regard the question about how is this an eigenvalue question:

Consider $B=\{e_{1},e_{2},e_{3}\}$ the standard basis of $\mathbb{R}^{3}$ and define $T:\mathbb{R}^{3}\to\mathbb{R}^{3}$ by $T(v):=Av$

You are looking for $ker(T)$ by definition.

Since $A$ is symmetric it is also diagonisable, if $v_{1},v_{2},v_{3}$ are independent eigenvector of $A$ then in the basis $B'=\{v_{1},v_{2},v_{3}\}$ you get the system $Dx=0$ where $D=diag(\lambda_{1},\lambda_{2},\lambda_{3})$ where $\lambda_{i}$ are the eigenvalues of $A$. Of course this system is very easy to solve.

You can always go back and write the solutions you found as a linear combination of the elements of $B$ (you can build a $3\times3$ matrix that takes vector written as linear combination of elements of $B'$ and gives you the vector written as linear combination of elements of $B$).

This also gives an algorithm (though I don't know about efficacy) , note that there is a closed formula to calculate the roots of a polynomial of degree $3$, but I think calculating the corresponding eigenvectors is as difficult as solveing the original question so I won't try this method.

share|improve this answer
    
@Peter - thanks, I should not trust Lyx corrections anymore –  Belgi Oct 4 '12 at 2:02
    
No problem. I had missed an "o", though. –  Pedro Tamaroff Oct 4 '12 at 2:18
add comment

I am the author of the mentioned article at infogoaround.org. You can solve the eigen pair problem via the power method. If you still want the solution, let me know. I can send you a C program to solve the dominant eigen pair.

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.