Errors .edu



3 Least Squares Problems and QR Factorizations

In this chapter we look at least squares problems and the related problem of finding the QR factorization of a matrix. In addition to providing a method for solving least squares problems, QR factorizations also provide an alternative to Gaussian elimination for solving linear equations. We begin with a discussion of least squares problems and their solution via orthogonal projections.

3.1 Projection on a Line and Reflection Across a Hyperplane.

The simplest least squares problem is the projection of a point on a line through the origin and the related reflection of a point across the hyperplane H orthogonal to L. The problem is the following.

Projection on a Line. Given a line L through the origin and a point b, find the point w on the line that is closest to b. w is called the orthogonal projection of b on L.

As the picture at the right suggests, the vector from b to w is orthogonal (or perpendicular) to L which is why w is called the orthogonal projection of b onto L. In this chapter we simply call w the projection of b onto L with orthogonal being understood.

We mean "closest" in the sense of the usual sense of distance between two points. If u = and v =  are two points (or vectors) then the distance d(u, v), between them is simply the square root of the sum of the squares of the difference between corresponding coordinates, i.e.

(1) d(u, v) =

= || u – v ||2 =

The distance between u and v is just the Euclidean norm of the difference u – v = . In this chapter the only norm we shall be working with is the Euclidean norm, so we shall drop the subscript two on ||  ||2. As indicated in (1), the distance between two points can also be written in terms of the dot product of vectors defined by

(2) u.v = u1v1 + uv2 + … + unvn = = uTv

There is the following connection between the dot product and norm.

(3) u.u = (u1)2 + (u2)2 + … + (un)2 = || u ||2

Note that a line L through the origin is just the set of all multiples w = xa of any point a on L. So the problem can be restated as follows.

Projection on a Line (restatement). Given vectors a =  and b = , find the multiple w = xa of a that is closest to b.

In order to make use of the fact that the vector from w to b is orthogonal to L (or a), recall that two vectors u and v are orthogonal if u.v = 0. To see this note that

(4) u.v = (length of u) (length of v) (cosine of the angle between u and v)

= || u || || v || cos (

where ( is the angle between u and v. In particular, u and v will be perpendicular, or orthogonal, if ( = (/2 which occurs if cos ( = 0. Thus u and v will be orthogonal if u.v = 0. That leads to the following theorem.

Theorem 1. Let a and b be given vectors. If x is a number such that b – xa is orthogonal to a, then || b - xa || ( || b – ya || for all numbers y, i.e. w = xa is the projection of b on the line through a.

Proof. Using (3) and the distributive property of dot products one has

|| b – ya ||2 = (b – ya) . (b – ya) = (b – xa + (y-x)a) . (b – xa + (y-x)a)

= (b – xa ) . (b – xa ) + 2(y-x)(b – xa ) . a + ((y-x)a) . ((y-x)a)

= || b - xa ||2 + 2(y-x)(b – xa ) . a + || (y-x)a ||2

In particular, if b – xa is orthogonal to a holds then

|| b – ya ||2 = || b - xa ||2 + || (y-x)a ||2

This last relationship can be regarded as an application of the Phythagorean theorem. It follows that || b - xa ||2 ( || b – ya ||2 and the theorem follows. //

Using Theorem 1 we have the following formula for the projection of a point on a line.

Theorem 2. The projection of b on the line through a is given by

(5) w = a = Pb

where

(6) P = aaT = matrix for the projection onto the line through a.

Proof. It follows from Theorem 1, that w = xa satisfies (b – xa ) . a = 0 which implies x(a . a) = a . b or x  =   which proves the first equality in (5). To prove the second, note that

a = a(aTb) = (aaT)b = Pb

which proves the theorem. //

Example 1. Find the projection of on the line through . Also find the matrix P for the projection on the line through .

In this case a = and b = . So

w = a = = =

P = aaT = (3, 1) =

As a check

Pb = = =

Note that in general the projection P satisfies

P2 = P PT = P

If L is a line through the origin then the hyperplane H orthogonal to L consists of all points u such that the line from the origin to u is perpendicular to L. If L = {xa: x is a real number} consists of all multiple of a, then H = {v: a . v = 0} consists of all vectors v orthogonal to a. If L is a line in the plane, then H is the line through the origin perpendicular to L. If L is a line in three dimensions, then H is the plane through the origin perpendicular to L. If L is a line in four dimensions, then H is the three dimensional hyperplane through the origin perpendicular to L.

It follows from Theorem 2 that

b - a = (I – P)b = Qb = projection of b onto H, where

Q = I - P = matrix for the projection onto H

b - 2 a = (I – 2P)b = Fb = reflection of b across H, where

F = I - 2P = matrix for the reflection across H

Note that

Q2 = Q QT = Q

F2 = F F-1 = F FT = F F-1 = FT

A matrix R is called orthogonal if R-1 = RT. It follows that an (orthogonal) reflection across a hyperplane is orthogonal.

Example 2. Find the projection of onto the line H perpendicular to the vector and the matrix Q for the projection onto H. Find the reflection of across H and the matrix F for this reflection across H.

projection of on H = b - a = - =

Q = I - P = - =

reflection of across H = b - 2 a = - 2 =

F = I - 2P = - =

The following theorem shows that orthogonal matrices are distance preserving.

Theorem 3. Suppose Q is orthogonal. Then for all x and y one has

(7) (Qx) . (Qy) = x . y

(8) || Qx || = || x ||

(9) d(Qx, Qy) = d(x, y)

Proof. For a general matrix A one has x . (Ay) = (ATx) . y. Therfore (Qx) . (Qy) = (QTQx) . y. Since QT = Q-1 the relation (7) follows. Putting y = x in (7) gives || Qx ||2 = || x ||2 and (8) follows. Replacing x by x – y in (9) gives || Qx – Qy || = || x – y || and (9) follows. //

Theorem 4. Suppose Q and R are orthogonal. Then so are QR and Q-1.

Proof. (QR)-1 = R-1Q-1 = RTQT = (QR)T which shows QR is orthogonal. To show Q-1 is orthogonal we must show (Q-1)-1 = (Q-1)T. However (Q-1)-1 = Q so we must show Q = (Q-1)T. If we take the relation Q-1 = QT and transpose both sides we get (Q-1)T = (QT)T. However, (QT)T = Q so we get (Q-1)T = Q which what was desired. //

-----------------------

b- ax

ya- xa

b - ay

xy

w = xa

L

b

w

L

b

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download