Plane Fitting with Linear Least Squares

[mnb96]

Hello,
I am trying to figure out how to fit a plane passing through the origin in \mathbf{R}^3, given a cloud of N points.
The points are vectors of the form (x_1^{(k)}, x_2^{(k)}, x_3^{(k)}) , where k stands for the k-th point. I want to minimize the sum of squared distances point-plane.

What I came out with was the following:
- solve a 3x3 homogeneous linear system AX=0 in which the (i,j) element of A is:

\sum_{k=1}^N x_i^{(k)} x_j^{(k)}

Now I have two questions:

1) I have read somewhere that this turns out to be an eigenvalues problem. Basically I need to find the eigen-values/vectors in order to solve the system. Why?

2) I found another method which instead builds a rectangular Nx4 matrix in which, in the first column there are all the x's of the points, in the second column all the y's, in the third all the z's, and in the fourth all 1's. Then they compute the SVD and extract (I think) the last column of the rightmost output matrix. Why does that work? What's the difference?

 

[TrentFGuidry]

It sounds like you are describing a multiple linear regression problem.

f_i = a₁x_i + a₂y_i + a₃z_i

Where x_i, y_i, and z_i are the points and f_i is the observed function values.

To solve this, you can create a matrix Z with the following values:

x₁ y₁ z₁
x₂ y₂ z₂
x₃ y₃ z₃
.
.
.
x_n y_n z_n

You can also create a vector Y with the following values:

f₁
f₂
f₃
.
.
.
f_n

After creating the Z matrix and Y column vector, the regressed A vector can be found by solving:

Z^TZA = Z^TY

I have a longer post on this, with a derivation of that equation, and source code that I released to the public domain at http://www.trentfguidry.net/post/2009/07/19/Linear-and-Multiple-Linear-Regression-in-C.aspx"

 

[TrentFGuidry]

As for the eigenvalues/eigenvectors, I believe that you have to do that for an SVD decomposition, which is a way of solving the above matrix equation.

Another approach to solving the above equation is to use a different approach, such as an LU decomposition. The potential problem with an LU decomposition is that a singular matrix could result. If that occurs, then the problem cannot be solved using an LU decomposition and something else, like an SVD decomposition, would have to be used.

Fortunately, there are a lot of problems where singular matrices are a rare occurrence and the simpler and faster LU decomposition approach works. LU decomposition does not require eigenvalues/eigenvectors.

For part 2, you describe a Z matrix with ones in it. That Z matrix has constants that can offset it from the origin. For that case, you are regressing the function shown below.

f_i = a₀ + a₁x_i + a₂y_i + a₃z_i

If you want to force it through the origin, get rid of the column with all ones in it.