Linear Algebra Topics - Computer Graphics and Geometric Modeling - page 56

Equation (1.28) is trying to find the minimum for

n

Â

2

[ ]

( ) -

aa + a a + ... + a a b .

11 i 2 2 i m mi i

i = 1

To put it another way, we are trying to find the m-plane X in R m+1 through the origin
defined by an equation of the form

(1.29)

ax + a x + ... + a x - x

1 0

=

11 2 2 mm m +

that best fits the data points p i = (a 1i ,a 2i ,...,a mi ,b i ) ΠR m+1

in the sense that the sum

of the distances of the points p i to X is a minimum.

1.11.6. Theorem. If the matrix A in the linear least squares approximation problem
above has rank m, then there is a unique solution a 0 defined by

- 1

( )

+

() =

T T

() a = A b A AA b .

0

Proof. This is clear from the definition of the generalized inverse and Corollary
1.11.4(2). The uniqueness follows from the fact that the kernel of the linear transfor-
mation associated to A is 0 .

We need to point out that the planes defined by equation (1.29) are a subset of all
the m-planes through the origin, so that our particular approximation problem had
a bias built into it. Here is the usual statement of the unbiased general problem. One
uses squares of the distances to avoid having to deal with square roots. The mini-
mization problem has the same answer in either case.

The linear least squares approximation problem: Given a set of points p i in R m+1 find
the m-plane X in R m+1 with the property that the sum of the squares of the distances of
the points p i to X is a minimum.

Because of the bias in the allowed solution to our approximation problem,
Theorem 1.11.6 does not always solve the general problem. For example, consider the
points (-1,1), (-1,2), (-1,3), (1,1), (1,2), and (1,3) in R 2 . The line that best approxi-
mates this data is clearly the vertical line x = 0. Theorem 1.11.6 would give us simply
the point (0,0). The reason for this is that the vertical line does not have an equation
of the form (1.29). Of course, Theorem 1.11.6 does give the expected answer “most”
of the time but one must make sure that this answer does not lie in the set of planes
excluded by equation (1.29).
There is another special case where Theorem 1.11.6 does not give a satisfactory
answer, namely, in the case where b is zero and we have a homogeneous equation

x0 A = . (1.30)

A homogeneous equation like (1.30) always has a solution x = 0 . This is what Theorem
1.11.6 would give us. Of course, this is the uninteresting solution and we are proba-
bly looking for a nonzero solution. We will be able to use Theorem 1.11.6 if we rewrite