Linear Least Squares
2
Linear Least Squares
The linear model is the main technique in regression problems and the primary tool for it is least squares fitting. We minimize a sum of squared errors, or equivalently the sample average of squared errors. That is a natural choice when we're interested in finding the regression function which minimizes the corresponding expected squared error. This chapter presents the basic theory of linear least squares estimation, looking at it with calculus, linear algebra and geometry. It also develops some distribution theory for linear least squares and computational aspects of linear regression. We will draw repeatedly on the material here in later chapters that look at specific data analysis problems.
2.1 Least squares estimates
We begin with observed response values y1, y2, . . . , yn and features zij for i = 1, . . . , n and j = 1, . . . , p. We're looking for the parameter values 1, . . . , p that minimize
n
p
2
S(1, . . . , p) =
yi - zij j .
i=1
j=1
(2.1)
The minimizing values are denoted with hats: ^1, . . . , ^p. To minimize S, we set its partial derivative with respect to each j to 0.
The solution satisfies
n
S = -2
j
i=1
p
yi - zij ^j
j=1
zij = 0,
j = 1, . . . , p.
(2.2)
1
2
2. LINEAR LEAST SQUARES
We'll show later that this indeed gives the minimum, not the maximum or a
saddle point. The p equations in (2.2) are known as the normal equations.
This is due to normal being a synonym for perpendicular or orthogonal, and
not due to any assumption about the normal distribution. Consider the vector
Z j = (z1j, . . . , znj) Rn of values for the j'th feature. Equation (2.2) says
that this feature vector has a dot product of zero with the residual vector having
i'th element ^i = yi -
p j=1
zij
^j
.
Each
feature vector
is orthogonal (normal)
to the vector of residuals.
It is worth while writing equations (2.1) and (2.2) in matrix notation. Though
the transition from (2.1) to (2.2) is simpler with coordinates, our later manip-
ulations are easier in vector form. Let's pack the responses and feature values
into the vector Y and matrix Z via
y1
z11 z12 . . . z1p
y2
z21 z22 . . . z2p
Y
=
...
,
and,
Z
=
...
...
...
...
.
yn
zn1 zn2 . . . znp
We also put = (1, . . . , p) and let ^ denote the minimizer of the sum of squares. Finally let ^ = Y - Z^, the n vector of residuals.
Now equation (2.1) can be written S() = (Y - Z) (Y - Z) and the
normal equations (2.2) become
^ Z = 0
(2.3)
after dividing by -2. These normal equations can also be written Z Z^ = Z Y.
(2.4)
When Z Z is invertible then we find that ^ = (Z Z)-1Z Y.
(2.5)
We'll suppose at first that Z Z is invertible and then consider the singular case
in Chapter 2.7.
Equation (2.5) underlies another meaning of the work `linear' in linear regression. The estimated coefficient ^ is a fixed linear combination of Y , meaning that we get it by multiplying Y by the matrix (Z Z)-1Z . The predicted value
of Y at any new point x0 with features z0 = (x0) is also linear in Y ; it is z0(Z Z)-1Z Y .
Now let's prove that ^ = (Z Z)-1Z Y is in fact the minimizer, not just a
point where the gradient of the sum of squares vanishes. It seems obvious that
a sum of squares like (2.1) cannot have a maximizing . But we need to rule out saddle points too, and we'll also find that ^ is the unique least squares estimator. Since we already found an expression for ^ we prove it is right by expressing a generic Rp as ^ + ( - ^) and then expanding S(^ + ( - ^)). This adding and subtracting technique is often applicable in problems featuring
squared errors.
2.2. GEOMETRY OF LEAST SQUARES
3
Theorem 2.1. Let Z be an n ? p matrix with Z Z invertible, and let Y be an n vector. Define S() = (Y - Z) (Y - Z) and set ^ = (Z Z)-1Z Y . Then S() > S(^) holds whenever = ^.
Proof. We know that Z (Y - Z^) = 0 and will use it below. Let be any point in Rp and let = - ^. Then
S() = (Y - Z) (Y - Z) = (Y - Z^ - Z) (Y - Z^ - Z) = (Y - Z^) (Y - Z^) - Z (Y - Z^) - (Y - Z^)Z + Z Z = S(^) + Z Z.
Thus S() = S(^) + Z 2 S(^). It follows that ^ is a minimizer of S. For uniqueness we need to show that = 0 implies Z = 0. Suppose to the contrary that Z = 0 for = 0. Then we would have Z Z = 0 for = 0, but this contradicts the assumption that Z Z is invertible. Therefore if = ^ then S() = S(^) + Z( - ^) 2 > 0
2.2 Geometry of least squares
Figure xxx shows a sketch to illustrate linear least squares. The vector y = (y1, . . . , yn) is represented as a point in Rn. The set
M = {Z | Rp}
(2.6)
is a p dimensional linear subset of Rn. It is fully p dimensional here because we have assumed that Z Z is invertible and so Z has rank p. Under our model, E(Y ) = Z M.
The idea behind least squares is to find ^ so that y^ = Z^ is the closest point to y from within M. We expect to find this closest point to y by "dropping a perpendicular line" to M. That is, the error ^ = y - y^ should be perpendicular to any line within M. From the normal equations (2.3), we have ^ Z = 0 so ^ is actually perpendicular to every point Z M. Therefore ^ is perpendicular to every line in M.
We can form a right angle triangle using the three points y, y^ and Z for any Rp. Taking = 0 and using Pythagoras' theorem we get
y 2 = ^ 2 + z^ 2.
When the first column of Z consists of 1s then (y?, . . . , y?) = Z(y?, 0, . . . , 0) M and Pythagoras' theorem implies
n
n
n
(yi - y?)2 = (y^i - y?)2 + (yi - y^)2.
i=1
i=1
i=1
(2.7)
4
2. LINEAR LEAST SQUARES
The left side of (2.7) is called the centered sum of squares of the yi. It is n - 1 times the usual estimate of the common variance of the Yi. The equation decomposes this sum of squares into two parts. The first is the centered sum of
squared errors of the fitted values y^i. The second is the sum of squared model
errors. is y?^ =
When the first column of y?. Now the two terms in
Z consists of 1s then (1/n) (2.7) correspond to the sum
n i=1
y^i
=
y?.
That
of squares of the
fitted values y^i about their mean and the sum of squared residuals. We write this as SSTOT = SSFIT + SSRES. The total sum of squares is the sum of squared fits plus the sum of squared residuals.
Some of the variation in Y is `explained' by the model and some of it left
unexplained. The fraction explained is denoted by
R2 = SSFIT = 1 - SSRES .
SSTOT
SSTOT
The quantity R2 is known as the coefficient of determination. It measures how well Y is predicted or determined by Z^. Its nonnegative square root R is called the coefficient of multiple correlation. It is one measure of how well the response Y correlates with the p predictors in Z taken collectively. For the special case of simple linear regression with zi = (1, xi) R2 then (Exercise xxx) R2 is the square of the usual Pearson correlation of x and y.
Equation (2.7) is an example of an ANOVA (short for analysis of variance) decomposition. ANOVA decompositions split a variance (or a sum of squares) into two or more pieces. Not surprisingly there is typically some orthogonality or the Pythagoras theorem behind them.
2.3 Algebra of least squares
The predicted value for yi, using the least squares estimates, is y^i = Zi^. We can write the whole vector of fitted values as y^ = Z^ = Z(Z Z)-1Z Y . That is y^ = Hy where
H = Z(Z Z)-1Z .
Tukey coined the term "hat matrix" for H because it puts the hat on y. Some simple properties of the hat matrix are important in interpreting least squares.
By writing H2 = HH out fully and cancelling we find H2 = H. A matrix H with H2 = H is called idempotent. In hindsight, it is geometrically obvious that we should have had H2 = H. For any y Rn the closest point to y inside of M is Hy. Since Hy is already in M, H(Hy) = Hy. That is H2y = Hy for any y and so H2 = H. Clearly Hk = H for any integer k 1.
The matrix Z Z is symmetric, and so therefore is (Z Z)-1. It follows that the hat matrix H is symmetric too. A symmetric idempotent matrix such as H is called a perpendicular projection matrix.
Theorem 2.2. Let H be a symmetric idempotent real valued matrix. Then the eigenvalues of H are all either 0 or 1.
2.4. DISTRIBUTIONAL RESULTS
5
Proof. Suppose that x is an eigenvector of H with eigenvalue , so Hx = x. Because H is idempotent H2x = Hx = x. But we also have H2x = H(Hx) = H(x) = 2x. Therefore x = 2x. The definition of eigenvector does not allow x = 0 and so we must have 2 = . Either = 0 or = 1.
Let H = P P where the columns of P are eigenvectors pi of H for i =
1, . . . , n. Then H =
n i=1
ipipi,
where
by
Theorem
2.2
each
i
is
0
or
1.
With
no loss of generality, we can arrange for the ones to precede the zeros. Suppose
that there are r ones. Then H =
r i=1
pipi
.
We
certainly
expect
r
to
equal
p
here. This indeed holds. The eigenvalues of H sum to r, so tr(H) = r. Also
tr(H) = tr(Z(Z Z)-1Z ) = tr(Z Z(Z Z)-1) = tr(Ip) = p. Therefore r = p and
H=
p i=1
pipi
where
pi
are
mutually
orthogonal
n
vectors.
The prediction for observation i can be written as y^i = Hi y where Hi is
the i'th row of the hat matrix. The i'th row of H is simply zi(Z Z)-1Z and the ij element of the hat matrix is Hij = zi(Z Z)-1zj. Because Hij = Hji the
contribution of yi to y^j equals that of yj to y^i. The diagonal elements of the
hat matrix will prove to be very important. They are
Hii = zi(Z Z)-1zi.
(2.8)
We are also interested in the residuals ^i = yi - y^i. The entire vector of
residuals may be written ^ = y - y^ = (I - H)y. It is easy to see that if
H is a PPM, then so is I - H. Symmetry is trivial, and (I - H)(I - H) =
I - H - H + HH = I - H.
The model space M = {Z | Rp} is the set of linear combinations of
columns of Z. A typical entry of M is
p j=1
j
Z
j
.
Thus
M
is
what
is
known
as the column space of Z, denoted col(Z). The hat matrix H projects vectors
onto col(Z). The set of vectors orthogonal to Z, that is with Zv = 0, is a linear
subspace of Rn, known as the null space of Z. We may write it as M or as
null(Z). The column space and null spaces are orthogonal complements. Any
v Rn can be uniquely written as v1 + v2 where v1 M and v2 M. In
terms of the hat matrix, v1 = Hv and v2 = (I - H)v.
2.4 Distributional results
We continue to suppose that X and hence Z is a nonrandom matrix and that Z has full rank. The least squares model has Y = Z + . Then
^ = (Z Z)-1Z Y = (Z Z)-1(Z Z + ) = + (Z Z)-1Z . (2.9)
The only randomness in the right side of (2.9) comes from . This makes it easy to work out the mean and variance of ^ in the fixed x.
Lemma 2.1. If Y = Z + where Z is nonrandom and Z Z is invertible and E() = 0, then
E(^) = .
(2.10)
6
2. LINEAR LEAST SQUARES
Proof. E(^) = + (Z Z)-1Z E() = .
The least squares estimates ^ are unbiased for as long as has mean zero. Lemma 2.1 does not require normally distributed errors. It does not even make any assumptions about var(). To study the variance of ^ we will need assumptions on var(), but not on its mean.
Lemma 2.2. If Y = Z + where Z is nonrandom and Z Z is invertible and var() = 2I, for 0 2 < , then
var(^) = (Z Z)-12.
(2.11)
Proof. Using equation (2.9),
var(^) = (Z Z)-1Z var()Z(Z Z)-1 = (Z Z)-1Z 2I Z(Z Z)-1 = (Z Z)-12,
(2.12)
after a particularly nice cancellation.
We will look at and interpret equation (2.12) for many specific linear models. For now we notice that it holds without regard to whether is normally distributed or even whether it has mean 0.
Up to now we have studied the mean and variance of the estimate of . Next we turn our attention to 2. The key to estimating 2 is the residual vector ^.
Lemma 2.3. Under the conditions of Lemma 2.2, E(^ ^) = (n - p)2. For p < n the estimate
s2 = 1 n-p
n
(Yi - zi^)2
i=1
(2.13)
satisfies E(s2) = 2.
Proof. Recall that ^ = (I - H). Therefore E(^ ^) = E( (I - H)) = tr((I - H)I2) = (n - p)2. Finally s2 = ^ ^/(n - p).
Now we add in the strong assumption that N (0, 2I). Normally distributed errors make for normally distributed least squares estimates, fits and residuals.
Theorem 2.3. Suppose that Z is an n by p matrix of real values, Z Z is invertible, and Y = Z + where N (0, 2I). Then
^ N (, (Z Z)-12), y^ N (Z, H2), ^ N (0, (I - H)2),
where H = Z(Z Z)-1Z . Furthermore, ^ is independent of ^ and of y^.
2.4. DISTRIBUTIONAL RESULTS
7
Proof. Consider the vector
^ (Z Z)-1Z
v = y^ = H Y Rp+2n.
^
I -H
The response Y has a multivariate normal distribution and so therefore does v. Hence each of ^, y^, and ^ is multivariate normal.
The expected value of v is
(Z Z)-1Z
E(v) = H Z = HZ = Z
I -H
(I - H)Z
0
because HZ = Z, establishing the means listed above for ^, y^ and ^. The variance of ^ is (Z Z)-12 by Lemma 2.2. The variance of y^ is var(y^) =
Hvar(Y )H = H(2I)H = H2 because H is symmetric and idempotent. Similarly ^ = (I - H)(Z + ) = (I - H) and so var(^) = (I - H)(2I)(I - H) = (I - H)2 because I - H is symmetric and idempotent.
We have established the three distributions displayed but have yet to prove the claimed independence. To this end
cov(^, ^) = (Z Z)-1Z (2I)(I - H) = (Z Z)-1(Z - HZ) 2 = 0
because Z = HZ. Therefore ^ and ^ are uncorrelated and hence independent because v has a normal distribution. Similarly cov(y^, ^) = H(I - H) 2 = (H - HH )2 = 0 establishing the second and final independence claim.
We can glean some insight about the hat matrix from Theorem 2.3. First because var(y^i) = 2Hii we have Hii 0. Next because var(^) = 2(1 - Hii) we have 1 - Hii 0. Therefore 0 Hii 1 holds for i = 1, . . . , n.
Theorem 2.4. Assume the conditions of Theorem 2.3, and also that p < n.
Let
s2
=
1 n-p
n i=1
(Yi
- zi^)2.
Then
(n - p)s2 22(n-p).
(2.14)
Proof. First
(n - p)s2 = (Y - Z^) (Y - Z^) = Y (I - H)Y = (I - H).
The matrix I - H can be written I - H = P P where P is orthogonal and = diag(1, . . . , n). From I - H = (I - H)2 we get i {0, 1}. Let = P N (0, 2I). Then (I - H) = 22(k) where k is the number of i = 1, that is k = tr(I - H). Therefore
k = n-tr(H) = n-tr(Z(Z Z)-1Z ) = n-tr((Z Z)-1Z Z) = n-tr(Ip) = n-p.
8
2. LINEAR LEAST SQUARES
Equation (2.14) still holds trivially, even if = 0. The theorem statement excludes the edge case with n = p because s2 is then not well defined (zero over
zero).
Very often we focus our attention on a specific linear combination of the
components of . We write such a combination as c where c is a p ? 1 row
vector. Taking c = (0, . . . , 0, 1, 0, . . . 0) with the 1 in the j'th place gives c = j. If for instance cj = 0, then we question whether feature j helps us predict Y . More generally, parameter combinations like 2 - 1 or 1 - 22 + 3 can be studied by making a judicious choice of c. Taking c = z0 makes c the expected value of Y when the feature vector is set to z0 and taking c = z0 - z0 lets us study the difference between E(Y ) at features z0 and z0.
For any such vector c, Theorem 2.3 implies that c^ N (c, c(Z Z)-1c 2). We ordinarily don't know 2 but can estimate it via s2 from (2.13). In later
chapters we will test whether c takes a specific value c0, and form confidence intervals for c using Theorem 2.5.
Theorem 2.5. Suppose that Y N (Z, 2I) where Z is an n ? p matrix, Z Z
is invertible, and > 0.
Let ^ = (Z
Z )-1 Z
Y
and s2
=
1 n-p
(Y
- Z^)
(Y
- Z^).
Then for any nonzero 1 ? p (row) vector c,
c^ - c s c(Z Z)-1c t(n-p).
(2.15)
Proof. Let U = (c^ - c)/( c(Z Z)-1c ). Then U N (0, 1). Let V = s2/2,
so V 2(n-p)/(n - p). Now U is a function of ^ and V is a function of ^. Therefore U and V are independent. Finally
c^ - c
(c^-c)
c(Z Z)-1c
U
= s c(Z Z)-1c
s/
= V
t(n-p)
by the definition of the t distribution.
Theorem 2.5 is the basis for t tests and related confidence intervals for linear models. The recipe is to take the estimate c^ subtract the hypothesized parameter value c and then divide by an estimate of the standard deviation of c^.
Having gone through these steps we're left with a t(n-p) distributed quantity. We will use those steps repeatedly in a variety of linear model settings.
Sometimes Theorem 2.5 is not quite powerful enough. We may have r dif-
ferent linear combinations of embodied in an r ? p matrix C and we wish to
test whether C = C0. We could test r rows of C individually, but testing them all at once is different and some problems will require such a simultaneous
test. Theorem 2.6 is an r dimensional generalization of Theorem 2.5.
Theorem 2.6. Suppose that Y N (Z, 2I) where Z is an n ? p matrix, Z Z
is invertible, and > 0.
Let ^ = (Z
Z )-1 Z
Y
and s2
=
1 n-p
(Y
- Z^)
(Y
- Z^).
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- extending linear regression weighted least squares
- restricted least squares hypothesis testing and
- regression estimation least squares and maximum likelihood
- lecture 4 multivariate regression model in matrix form
- week 5 simple linear regression princeton
- multiple linear regression mlr handouts
- linear least squares
- chapter 2 linear regression models ols assumptions and
- lecture 2 linear regression a model for the mean
- chapter 1 linear regression with 1 predictor
Related searches
- how to graph least squares regression line
- equation of least squares regression line calculator
- slope of the least squares regression line
- least squares regression line example
- linear least squares regression equation
- linear least squares regression formula
- weighted least squares linear regression
- linear least squares fit calculator
- linear least squares matlab
- linear least squares regression calculator
- linear algebra least squares example
- linear least squares equation