The purpose of Proofs involving ordinary least squares page is to provide supplementary materials for the ordinary least squares article, reducing the load of the main article with mathematics and improving its accessibility, while at the same time retaining the completeness of exposition.
Derivation of the normal equations Define the i {\displaystyle i} th residual to be
r i = y i − ∑ j = 1 n X i j β j . {\displaystyle r_{i}=y_{i}-\sum _{j=1}^{n}X_{ij}\beta _{j}.}
Then the objective S {\displaystyle S} can be rewritten
S = ∑ i = 1 m r i 2 . {\displaystyle S=\sum _{i=1}^{m}r_{i}^{2}.}
Given that S is convex, it is minimized when its gradient vector is zero (This follows by definition: if the gradient vector is not zero, there is a direction in which we can move to minimize it further – see maxima and minima.) The elements of the gradient vector are the partial derivatives of S with respect to the parameters:
∂ S ∂ β j = 2 ∑ i = 1 m r i ∂ r i ∂ β j ( j = 1 , 2 , … , n ) . {\displaystyle {\frac {\partial S}{\partial \beta _{j}}}=2\sum _{i=1}^{m}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}\qquad (j=1,2,\dots ,n).}
The derivatives are
∂ r i ∂ β j = − X i j . {\displaystyle {\frac {\partial r_{i}}{\partial \beta _{j}}}=-X_{ij}.}
Substitution of the expressions for the residuals and the derivatives into the gradient equations gives
∂ S ∂ β j = 2 ∑ i = 1 m ( y i − ∑ k = 1 n X i k β k ) ( − X i j ) ( j = 1 , 2 , … , n ) . {\displaystyle {\frac {\partial S}{\partial \beta _{j}}}=2\sum _{i=1}^{m}\left(y_{i}-\sum _{k=1}^{n}X_{ik}\beta _{k}\right)(-X_{ij})\qquad (j=1,2,\dots ,n).}
Thus if β ^ {\displaystyle {\widehat {\beta }}} minimizes S, we have
2 ∑ i = 1 m ( y i − ∑ k = 1 n X i k β ^ k ) ( − X i j ) = 0 ( j = 1 , 2 , … , n ) . {\displaystyle 2\sum _{i=1}^{m}\left(y_{i}-\sum _{k=1}^{n}X_{ik}{\widehat {\beta }}_{k}\right)(-X_{ij})=0\qquad (j=1,2,\dots ,n).}
Upon rearrangement, we obtain the normal equations:
∑ i = 1 m ∑ k = 1 n X i j X i k β ^ k = ∑ i = 1 m X i j y i ( j = 1 , 2 , … , n ) . {\displaystyle \sum _{i=1}^{m}\sum _{k=1}^{n}X_{ij}X_{ik}{\widehat {\beta }}_{k}=\sum _{i=1}^{m}X_{ij}y_{i}\qquad (j=1,2,\dots ,n).}
The normal equations are written in matrix notation as
( X T X ) β ^ = X T y {\displaystyle (\mathbf {X} ^{\mathrm {T} }\mathbf {X} ){\widehat {\boldsymbol {\beta }}}=\mathbf {X} ^{\mathrm {T} }\mathbf {y} } (where XT is the matrix transpose of X). The solution of the normal equations yields the vector β ^ {\displaystyle {\widehat {\boldsymbol {\beta }}}} of the optimal parameter values.
Derivation directly in terms of matrices The normal equations can be derived directly from a matrix representation of the problem as follows. The objective is to minimize
S ( β ) = ‖ y − X β ‖ 2 = ( y − X β ) T ( y − X β ) = y T y − β T X T y − y T X β + β T X T X β . {\displaystyle S({\boldsymbol {\beta }})={\bigl \|}\mathbf {y} -\mathbf {X} {\boldsymbol {\beta }}{\bigr \|}^{2}=(\mathbf {y} -\mathbf {X} {\boldsymbol {\beta }})^{\rm {T}}(\mathbf {y} -\mathbf {X} {\boldsymbol {\beta }})=\mathbf {y} ^{\rm {T}}\mathbf {y} -{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {y} -\mathbf {y} ^{\rm {T}}\mathbf {X} {\boldsymbol {\beta }}+{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {X} {\boldsymbol {\beta }}.}
Here ( β T X T y ) T = y T X β {\displaystyle ({\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {y} )^{\rm {T}}=\mathbf {y} ^{\rm {T}}\mathbf {X} {\boldsymbol {\beta }}} has the dimension 1x1 (the number of columns of y {\displaystyle \mathbf {y} } ), so it is a scalar and equal to its own transpose, hence β T X T y = y T X β {\displaystyle {\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {y} =\mathbf {y} ^{\rm {T}}\mathbf {X} {\boldsymbol {\beta }}}
and the quantity to minimize becomes
S ( β ) = y T y − 2 β T X T y + β T X T X β . {\displaystyle S({\boldsymbol {\beta }})=\mathbf {y} ^{\rm {T}}\mathbf {y} -2{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {y} +{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {X} {\boldsymbol {\beta }}.}
Differentiating this with respect to β {\displaystyle {\boldsymbol {\beta }}} and equating to zero to satisfy the first-order conditions gives
− X T y + ( X T X ) β = 0 , {\displaystyle -\mathbf {X} ^{\rm {T}}\mathbf {y} +(\mathbf {X} ^{\rm {T}}\mathbf {X} ){\boldsymbol {\beta }}=0,}
which is equivalent to the above-given normal equations. A sufficient condition for satisfaction of the second-order conditions for a minimum is that X {\displaystyle \mathbf {X} } have full column rank, in which case X T X {\displaystyle \mathbf {X} ^{\rm {T}}\mathbf {X} } is positive definite.
Derivation without calculus When X T X {\displaystyle \mathbf {X} ^{\rm {T}}\mathbf {X} } is positive definite, the formula for the minimizing value of β {\displaystyle {\boldsymbol {\beta }}} can be derived without the use of derivatives. The quantity
S ( β ) = y T y − 2 β T X T y + β T X T X β {\displaystyle S({\boldsymbol {\beta }})=\mathbf {y} ^{\rm {T}}\mathbf {y} -2{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {y} +{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}\mathbf {X} {\boldsymbol {\beta }}}
can be written as
⟨ β , β ⟩ − 2 ⟨ β , ( X T X ) − 1 X T y ⟩ + ⟨ ( X T X ) − 1 X T y , ( X T X ) − 1 X T y ⟩ + C , {\displaystyle \langle {\boldsymbol {\beta }},{\boldsymbol {\beta }}\rangle -2\langle {\boldsymbol {\beta }},(\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} \rangle +\langle (\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} ,(\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} \rangle +C,}
where C {\displaystyle C} depends only on y {\displaystyle \mathbf {y} } and X {\displaystyle \mathbf {X} } , and ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } is the inner product defined by
⟨ x , y ⟩ = x T ( X T X ) y . {\displaystyle \langle x,y\rangle =x^{\rm {T}}(\mathbf {X} ^{\rm {T}}\mathbf {X} )y.}
It follows that S ( β ) {\displaystyle S({\boldsymbol {\beta }})} is equal to
⟨ β − ( X T X ) − 1 X T y , β − ( X T X ) − 1 X T y ⟩ + C {\displaystyle \langle {\boldsymbol {\beta }}-(\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} ,{\boldsymbol {\beta }}-(\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} \rangle +C}
and therefore minimized exactly when
β − ( X T X ) − 1 X T y = 0. {\displaystyle {\boldsymbol {\beta }}-(\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} =0.}
Generalization for complex equations In general, the coefficients of the matrices X , β {\displaystyle \mathbf {X} ,{\boldsymbol {\beta }}} and y {\displaystyle \mathbf {y} } can be complex. By using a Hermitian transpose instead of a simple transpose, it is possible to find a vector β ^ {\displaystyle {\boldsymbol {\widehat {\beta }}}} which minimizes S ( β ) {\displaystyle S({\boldsymbol {\beta }})} , just as for the real matrix case. In order to get the normal equations we follow a similar path as in previous derivations:
S ( β ) = ⟨ y − X β , y − X β ⟩ = ⟨ y , y ⟩ − ⟨ X β , y ⟩ ¯ − ⟨ y , X β ⟩ ¯ + ⟨ X β , X β ⟩ = y T y ¯ − β † X † y − y † X β + β T X T X ¯ β ¯ , {\displaystyle \displaystyle S({\boldsymbol {\beta }})=\langle \mathbf {y} -\mathbf {X} {\boldsymbol {\beta }},\mathbf {y} -\mathbf {X} {\boldsymbol {\beta }}\rangle =\langle \mathbf {y} ,\mathbf {y} \rangle -{\overline {\langle \mathbf {X} {\boldsymbol {\beta }},\mathbf {y} \rangle }}-{\overline {\langle \mathbf {y} ,\mathbf {X} {\boldsymbol {\beta }}\rangle }}+\langle \mathbf {X} {\boldsymbol {\beta }},\mathbf {X} {\boldsymbol {\beta }}\rangle =\mathbf {y} ^{\rm {T}}{\overline {\mathbf {y} }}-{\boldsymbol {\beta }}^{\dagger }\mathbf {X} ^{\dagger }\mathbf {y} -\mathbf {y} ^{\dagger }\mathbf {X} {\boldsymbol {\beta }}+{\boldsymbol {\beta }}^{\rm {T}}\mathbf {X} ^{\rm {T}}{\overline {\mathbf {X} }}{\overline {\boldsymbol {\beta }}},}
where † {\displaystyle \dagger } stands for Hermitian transpose. We should now take derivatives of S ( β ) {\displaystyle S({\boldsymbol {\beta }})} with respect to each of the coefficients β j {\displaystyle \beta _{j}} , but first we separate real and imaginary parts to deal with the conjugate factors in above expression. For the β j {\displaystyle \beta _{j}} we have
β j = β j R + i β j I {\displaystyle \beta _{j}=\beta _{j}^{R}+i\beta _{j}^{I}}
and the derivatives change into
∂ S ∂ β j = ∂ S ∂ β j R ∂ β j R ∂ β j + ∂ S ∂ β j I ∂ β j I ∂ β j = ∂ S ∂ β j R − i ∂ S ∂ β j I ( j = 1 , 2 , 3 , … , n ) . {\displaystyle {\frac {\partial S}{\partial \beta _{j}}}={\frac {\partial S}{\partial \beta _{j}^{R}}}{\frac {\partial \beta _{j}^{R}}{\partial \beta _{j}}}+{\frac {\partial S}{\partial \beta _{j}^{I}}}{\frac {\partial \beta _{j}^{I}}{\partial \beta _{j}}}={\frac {\partial S}{\partial \beta _{j}^{R}}}-i{\frac {\partial S}{\partial \beta _{j}^{I}}}\quad (j=1,2,3,\ldots ,n).}
After rewriting S ( β ) {\displaystyle S({\boldsymbol {\beta }})} in the summation form and writing β j {\displaystyle \beta _{j}} explicitly, we can calculate both partial derivatives with result:
∂ S ∂ β j R =
− ∑ i = 1 m ( X ¯ i j y i + y ¯ i X i j ) + 2 ∑ i = 1 m X i j X ¯ i j β j R + ∑ i = 1 m ∑ k ≠ j n ( X i j X ¯ i k β ¯ k + β k X i k X ¯ i j ) ,
− i ∂ S ∂ β j I = ∑ i = 1 m ( X ¯ i j y i − y ¯ i X i j ) − 2 i ∑ i = 1 m X i j X ¯ i j β j I + ∑ i = 1 m ∑ k ≠ j n ( X i j X ¯ i k β ¯ k − β k X i k X ¯ i j ) , {\displaystyle {\begin{aligned}{\frac {\partial S}{\partial \beta _{j}^{R}}}={}&-\sum _{i=1}^{m}{\Big (}{\overline {X}}_{ij}y_{i}+{\overline {y}}_{i}X_{ij}{\Big )}+2\sum _{i=1}^{m}X_{ij}{\overline {X}}_{ij}\beta _{j}^{R}+\sum _{i=1}^{m}\sum _{k\neq j}^{n}{\Big (}X_{ij}{\overline {X}}_{ik}{\overline {\beta }}_{k}+\beta _{k}X_{ik}{\overline {X}}_{ij}{\Big )},\\[8pt]&{}-i{\frac {\partial S}{\partial \beta _{j}^{I}}}=\sum _{i=1}^{m}{\Big (}{\overline {X}}_{ij}y_{i}-{\overline {y}}_{i}X_{ij}{\Big )}-2i\sum _{i=1}^{m}X_{ij}{\overline {X}}_{ij}\beta _{j}^{I}+\sum _{i=1}^{m}\sum _{k\neq j}^{n}{\Big (}X_{ij}{\overline {X}}_{ik}{\overline {\beta }}_{k}-\beta _{k}X_{ik}{\overline {X}}_{ij}{\Big )},\end{aligned}}}
which, after adding it together and comparing to zero (minimization condition for β ^ {\displaystyle {\boldsymbol {\widehat {\beta }}}} ) yields
∑ i = 1 m X i j y ¯ i = ∑ i = 1 m ∑ k = 1 n