Page 304 - 35Linear Algebra

304 Least squares and Singular Values

If the vector space W has a notion of lengths of vectors, we can try to
find x that minimizes ||L(x) − v||.

This method has many applications, such as when trying to fit a (perhaps
linear) function to a “noisy” set of observations. For example, suppose we
measured the position of a bicycle on a racetrack once every five seconds.
Our observations won’t be exact, but so long as the observations are right on
average, we can figure out a best-possible linear function of position of the
bicycle in terms of time.
Suppose M is the matrix for the linear function L : U → W in some
bases for U and W. The vectors v and x are represented by column vectors
V and X in these bases. Then we need to approximate

MX − V ≈ 0 .

Note that if dim U = n and dim W = m then M can be represented by
m
n
an m × n matrix and x and v as vectors in R and R , respectively. Thus,
k
⊥
⊥
we can write W = L(U) ⊕ L(U) . Then we can uniquely write v = v + v ,
⊥
⊥
k
with v ∈ L(U) and v ∈ L(U) .
⊥
k
Thus we should solve L(u) = v . In components, v is just V −MX, and
is the part we will eventually wish to minimize.
In terms of M, recall that L(V ) is spanned by the columns of M. (In
⊥
the standard basis, the columns of M are Me 1 , . . ., Me n .) Then v must be
T
perpendicular to the columns of M. i.e., M (V − MX) = 0, or
T
T
M MX = M V.
T
T
Solutions of M MX = M V for X are called least squares solutions to
MX = V . Notice that any solution X to MX = V is a least squares solution.
304