Good notation translations to know for economists. (These will show up in the article)
( controls , econometrics ) (\text{controls}, \text{econometrics}) ( controls , econometrics )
c = β \pmb c = \pmb \beta c c = β β
p = X ′ y \pmb p = X'y p p = X ′ y
A = X A = X A = X
x = y \pmb x = \pmb y x x = y y
The Projection Theorem
We'll take as a given that the projection theorem is true .
Suppose S S S T = { p 1 , … , p m } ⊂ S T = \{\pmb p_1, \dots, \pmb p_m \} \subset S T = { p p 1 , … , p p m } ⊂ S V = span ( T ) V = \text{span}(T) V = span ( T )
For relevance to least squares, consider x = x ^ + e = ∑ i = 1 m c i c i + e \pmb x = \hat {\pmb x} + \pmb e = \sum_{i=1}^m c_i \pmb c_i + \pmb e x x = x x ^ + e e = ∑ i = 1 m c i c c i + e e e \pmb e e e
The projection theorem states that for x ∈ S \pmb x \in S x x ∈ S
min c 1 , … , c m ∥ e ∥ = min c 1 , … , c m ∥ x − ∑ i = 1 m c i p i ∥ \begin{align} \min_{c_1, \dots, c_m}\; \lVert\pmb e\rVert = \min_{c_1, \dots, c_m} \lVert \pmb x - \sum_{i=1}^mc_i\pmb p_i\rVert \end{align} c 1 , … , c m min ∥ e e ∥ = c 1 , … , c m min ∥ x x − i = 1 ∑ m c i p p i ∥ is obtained when e ⊥ span ( T ) \pmb e \perp \text{span}(T) e e ⊥ span ( T ) ⟨ e , v ⟩ = 0 \langle \pmb e ,\pmb v\rangle = 0 ⟨ e e , v v ⟩ = 0 v ∈ span ( T ) \pmb v \in \text{span}(T) v v ∈ span ( T )
The Grammian
The above problem may be more familiar if we write x = x ^ + e \pmb x = \hat {\pmb x} + \pmb e x x = x x ^ + e e x ^ = ∑ i = 1 m c i p i \hat{\pmb x}= \sum_{i=1}^mc_i\pmb p_i x x ^ = ∑ i = 1 m c i p p i
Let v ∈ span ( T ) \pmb v \in \text{span}(T) v v ∈ span ( T )
⟨ e , v ⟩ = ⟨ x − x ^ , v ⟩ = ⟨ x , v ⟩ − ⟨ x ^ , v ⟩ = 0 ⟹ ⟨ x , v ⟩ = ⟨ x ^ , v ⟩ = ⟨ ∑ i = 1 m c i p i , v ⟩ = ∑ i = 1 m c i ⟨ p i , v ⟩ = c 1 ⟨ p 1 , v ⟩ + ⋯ + c m ⟨ p m , v ⟩ \begin{align*} \langle \pmb e, \pmb v\rangle &= \langle \pmb x - \hat{\pmb x}, \pmb v\rangle \\ &= \langle \pmb x, \pmb v \rangle - \langle \hat{\pmb x} , \pmb v \rangle \\ &= 0 \\ \implies \langle \pmb x, \pmb v \rangle &= \langle \hat{\pmb x} , \pmb v \rangle \\ &= \left\langle \sum_{i=1}^mc_i\pmb p_i, \pmb v \right\rangle \\ &= \sum_{i=1}^mc_i\left\langle \pmb p_i, \pmb v \right\rangle \\ &= c_1\langle \pmb p_1, \pmb v\rangle + \dots + c_m\langle \pmb p_m, \pmb v\rangle \end{align*} ⟨ e e , v v ⟩ ⟹ ⟨ x x , v v ⟩ = ⟨ x x − x x ^ , v v ⟩ = ⟨ x x , v v ⟩ − ⟨ x x ^ , v v ⟩ = 0 = ⟨ x x ^ , v v ⟩ = ⟨ i = 1 ∑ m c i p p i , v v ⟩ = i = 1 ∑ m c i ⟨ p p i , v v ⟩ = c 1 ⟨ p p 1 , v v ⟩ + ⋯ + c m ⟨ p p m , v v ⟩ Therefore we have that c 1 ⟨ p 1 , v ⟩ + ⋯ + c m ⟨ p m , v ⟩ = ⟨ x , v ⟩ c_1\langle \pmb p_1, \pmb v\rangle + \dots + c_m\langle \pmb p_m, \pmb v\rangle = \langle \pmb x, \pmb v \rangle c 1 ⟨ p p 1 , v v ⟩ + ⋯ + c m ⟨ p p m , v v ⟩ = ⟨ x x , v v ⟩ v ∈ span ( T ) \pmb v \in \text{span}(T) v v ∈ span ( T )
Clearly p 1 , … , p m ∈ span ( T ) \pmb p_1, \dots, \pmb p_m \in \text{span}(T) p p 1 , … , p p m ∈ span ( T ) p \pmb p p p v \pmb v v v m m m
c 1 ⟨ p 1 , p 1 ⟩ + ⋯ + c m ⟨ p m , p 1 ⟩ = ⟨ x , p 1 ⟩ ⋮ c 1 ⟨ p 1 , p m ⟩ + ⋯ + c m ⟨ p m , p m ⟩ = ⟨ x , p m ⟩ \begin{align*} c_1\langle \pmb p_1, \pmb p_1\rangle + \dots + c_m\langle \pmb p_m, \pmb p_1\rangle &= \langle \pmb x, \pmb p_1\rangle \\ \vdots \\ c_1\langle \pmb p_1, \pmb p_m\rangle + \dots + c_m\langle \pmb p_m, \pmb p_m\rangle &= \langle \pmb x, \pmb p_m\rangle \end{align*} c 1 ⟨ p p 1 , p p 1 ⟩ + ⋯ + c m ⟨ p p m , p p 1 ⟩ ⋮ c 1 ⟨ p p 1 , p p m ⟩ + ⋯ + c m ⟨ p p m , p p m ⟩ = ⟨ x x , p p 1 ⟩ = ⟨ x x , p p m ⟩ These are known as the normal equations . They can be written in matrix form as:
[ ⟨ p 1 , p 1 ⟩ … ⟨ p m , p 1 ⟩ ⋮ ⋱ ⋮ ⟨ p 1 , p m ⟩ … ⟨ p m , p m ⟩ ] ⏟ Grammian [ c 1 ⋮ c m ] = [ ⟨ x , p 1 ⟩ ⋮ ⟨ x , p m ⟩ ] ⏟ Cross Correlation R c = p \begin{align*} \underbrace{\begin{bmatrix} \langle \pmb p_1, \pmb p_1 \rangle & \dots & \langle \pmb p_m, \pmb p_1 \rangle \\ \vdots & \ddots & \vdots \\ \langle \pmb p_1, \pmb p_m \rangle & \dots & \langle \pmb p_m, \pmb p_m \rangle \end{bmatrix}}_{\text{Grammian}} \begin{bmatrix}c_1 \\ \vdots \\ c_m\end{bmatrix} &= \underbrace{\begin{bmatrix} \langle \pmb x, \pmb p_1 \rangle \\ \vdots \\ \langle \pmb x, \pmb p_m\rangle \end{bmatrix}}_{\text{Cross Correlation}}\\[25pt] R \pmb c &= \pmb p \end{align*} Grammian ⎣ ⎡ ⟨ p p 1 , p p 1 ⟩ ⋮ ⟨ p p 1 , p p m ⟩ … ⋱ … ⟨ p p m , p p 1 ⟩ ⋮ ⟨ p p m , p p m ⟩ ⎦ ⎤ ⎣ ⎡ c 1 ⋮ c m ⎦ ⎤ R c c = Cross Correlation ⎣ ⎡ ⟨ x x , p p 1 ⟩ ⋮ ⟨ x x , p p m ⟩ ⎦ ⎤ = p p R R R
Solution to Norm Minimization
Recall that x = x ^ + e \pmb x = \hat{\pmb x} + \pmb e x x = x x ^ + e e x ^ = ∑ i = 1 m c i p i \hat{\pmb x} = \sum_{i=1}^mc_i\pmb p_i x x ^ = ∑ i = 1 m c i p p i x ^ = A c \hat{\pmb x} = A \pmb c x x ^ = A c c A = [ p 1 … p m ] A = \begin{bmatrix}\pmb p_1 & \dots & \pmb p_m\end{bmatrix} A = [ p p 1 … p p m ] c = [ c 1 … c m ] T \pmb c = \begin{bmatrix}c_1 & \dots & c_m \end{bmatrix}^T c c = [ c 1 … c m ] T c \pmb c c c
c = R − 1 p \begin{align*} \pmb c = R^{-1}\pmb p \end{align*} c c = R − 1 p p Therefore
x ^ = A c = A R − 1 p \begin{align*} \hat{\pmb x } &= A\pmb c \\ &= AR^{-1}\pmb p \end{align*} x x ^ = A c c = A R − 1 p p Inner Products
Weighted Least Squares
Assume we're working in a finite dimensional vector space (i.e. m m m
Every inner product can be written as ⟨ x , y ⟩ = y H W x \langle \pmb x , \pmb y \rangle = \pmb y^H W \pmb x ⟨ x x , y y ⟩ = y y H W x x W W W
Then starting from the top:
R c = p [ ⟨ p 1 , p 1 ⟩ … ⟨ p m , p 1 ⟩ ⋮ ⋱ ⋮ ⟨ p 1 , p m ⟩ … ⟨ p m , p m ⟩ ] [ c 1 ⋮ c m ] = [ ⟨ x , p 1 ⟩ ⋮ ⟨ x , p m ⟩ ] [ p 1 H W p 1 … p 1 H W p m ⋮ ⋱ ⋮ p m H W p 1 … p m H W p m ] [ c 1 ⋮ c m ] = [ p 1 H W x ⋮ p m H W x ] [ p 1 H ⋮ p m H ] W [ p 1 … p m ] [ c 1 ⋮ c m ] = [ p 1 H ⋮ p m H ] W [ x ⋮ x ] \begin{align*} R \pmb c &= \pmb p \\[8pt] \begin{bmatrix} \langle \pmb p_1, \pmb p_1 \rangle & \dots & \langle \pmb p_m, \pmb p_1 \rangle \\ \vdots & \ddots & \vdots \\ \langle \pmb p_1, \pmb p_m \rangle & \dots & \langle \pmb p_m, \pmb p_m \rangle \end{bmatrix} \begin{bmatrix}c_1 \\ \vdots \\ c_m\end{bmatrix} &= \begin{bmatrix} \langle \pmb x, \pmb p_1 \rangle \\ \vdots \\ \langle \pmb x, \pmb p_m\rangle \end{bmatrix} \\[25pt] \begin{bmatrix}\pmb p_1^H W \pmb p_1 & \dots & \pmb p_1^H W\pmb p_m \\ \vdots & \ddots & \vdots \\ \pmb p_m^H W\pmb p_1 & \dots & \pmb p_m^H W\pmb p_m\end{bmatrix} \begin{bmatrix}c_1 \\ \vdots \\ c_m\end{bmatrix} &= \begin{bmatrix} \pmb p_1^H W \pmb x \\ \vdots \\ \pmb p_m^H W \pmb x \end{bmatrix} \\[25pt] \begin{bmatrix}\pmb p_1^H \\ \vdots \\\pmb p_m^H\end{bmatrix} W \begin{bmatrix}\pmb p_1 & \dots & \pmb p_m\end{bmatrix}\begin{bmatrix}c_1 \\ \vdots \\ c_m\end{bmatrix} &= \begin{bmatrix}\pmb p_1^H \\ \vdots \\\pmb p_m^H\end{bmatrix} W \begin{bmatrix}\pmb x \\ \vdots \\ \pmb x\end{bmatrix} \end{align*} R c c ⎣ ⎡ ⟨ p p 1 , p p 1 ⟩ ⋮ ⟨ p p 1 , p p m ⟩ … ⋱ … ⟨ p p m , p p 1 ⟩ ⋮ ⟨ p p m , p p m ⟩ ⎦ ⎤ ⎣ ⎡ c 1 ⋮ c m ⎦ ⎤ ⎣ ⎡ p p 1 H W p p 1 ⋮ p p m H W p p 1 … ⋱ … p p 1 H W p p m ⋮ p p m H W p p m ⎦ ⎤ ⎣ ⎡ c 1 ⋮ c m ⎦ ⎤ ⎣ ⎡ p p 1 H ⋮ p p m H ⎦ ⎤ W [ p p 1 … p p m ] ⎣ ⎡ c 1 ⋮ c m ⎦ ⎤ = p p = ⎣ ⎡ ⟨ x x , p p 1 ⟩ ⋮ ⟨ x x , p p m ⟩ ⎦ ⎤ = ⎣ ⎡ p p 1 H W x x ⋮ p p m H W x x ⎦ ⎤ = ⎣ ⎡ p p 1 H ⋮ p p m H ⎦ ⎤ W ⎣ ⎡ x x ⋮ x x ⎦ ⎤ Define A = [ p 1 … p m ] A = \begin{bmatrix}\pmb p_1 & \dots & \pmb p_m\end{bmatrix} A = [ p p 1 … p p m ]
A H W A c = A H W x R c = p \begin{align*} A^H W A \pmb c &= A^HW \pmb x \\ R \pmb c &= \pmb p \end{align*} A H W A c c R c c = A H W x x = p p When W = I W=I W = I
Other Inner products
There are many inner products that we could consider. For example, the inner product could be the expected value or it could be the integral of the basis vectors along some interval when our spanning set are functions instead of discrete data.
Remember that the normal equations tell us a necessary and sufficient condition for when our error vector will be perpendicular to the spanning set, and by the projection theorem, this is when the induced norm is minimized.
Minimum Error
Let's write the solution to the minimum error in a few forms that are useful.
∥ e min ∥ 2 = ∥ x − x ^ ∥ 2 = ⟨ x − x ^ , x − x ^ ⟩ = ⟨ x , x ⟩ − ⟨ x , x ^ ⟩ − ⟨ x ^ , x ⟩ + ⟨ x ^ , x ^ ⟩ = ⟨ x , x ⟩ − ⟨ x ^ + e , x ^ ⟩ − ⟨ x ^ , x ^ + e ⟩ + ⟨ x ^ , x ^ ⟩ = ⟨ x , x ⟩ − ⟨ x ^ , x ^ ⟩ − ⟨ e , x ^ ⟩ ⏟ 0 − ⟨ x ^ , x ^ ⟩ − ⟨ x ^ , e ⟩ ⏟ 0 + ⟨ x ^ , x ^ ⟩ = ⟨ x , x ⟩ − ⟨ x ^ , x ^ ⟩ = ∥ x ∥ 2 − ∥ x ^ ∥ 2 \begin{align*} \lVert \pmb e_{\min} \rVert^2 &= \lVert \pmb x - \hat {\pmb x} \rVert^2 \\ &= \langle \pmb x - \hat {\pmb x} , \pmb x - \hat {\pmb x} \rangle \\ &= \langle \pmb x, \pmb x \rangle - \langle \pmb x, \hat{ \pmb x} \rangle - \langle \hat{\pmb x}, \pmb x \rangle + \langle \hat{\pmb x }, \hat{\pmb x } \rangle \\ &= \langle \pmb x, \pmb x \rangle - \langle \hat{\pmb x} + \pmb e, \hat{ \pmb x} \rangle - \langle \hat{\pmb x}, \hat{\pmb x} + \pmb e \rangle + \langle \hat{\pmb x }, \hat{\pmb x } \rangle \\ &= \langle \pmb x, \pmb x \rangle - \langle \hat{\pmb x}, \hat{ \pmb x} \rangle - \underbrace{\langle \pmb e, \hat{ \pmb x} \rangle}_{0} - \langle \hat{\pmb x}, \hat{\pmb x} \rangle - \underbrace{\langle \hat{\pmb x} , \pmb e \rangle}_0 + \langle \hat{\pmb x }, \hat{\pmb x } \rangle \\ &= \langle \pmb x , \pmb x \rangle - \langle \hat {\pmb x}, \hat {\pmb x} \rangle \\ &= \lVert \pmb x \rVert^2 - \lVert \hat {\pmb x} \rVert^2 \end{align*} ∥ e e m i n ∥ 2 = ∥ x x − x x ^ ∥ 2 = ⟨ x x − x x ^ , x x − x x ^ ⟩ = ⟨ x x , x x ⟩ − ⟨ x x , x x ^ ⟩ − ⟨ x x ^ , x x ⟩ + ⟨ x x ^ , x x ^ ⟩ = ⟨ x x , x x ⟩ − ⟨ x x ^ + e e , x x ^ ⟩ − ⟨ x x ^ , x x ^ + e e ⟩ + ⟨ x x ^ , x x ^ ⟩ = ⟨ x x , x x ⟩ − ⟨ x x ^ , x x ^ ⟩ − 0 ⟨ e e , x x ^ ⟩ − ⟨ x x ^ , x x ^ ⟩ − 0 ⟨ x x ^ , e e ⟩ + ⟨ x x ^ , x x ^ ⟩ = ⟨ x x , x x ⟩ − ⟨ x x ^ , x x ^ ⟩ = ∥ x x ∥ 2 − ∥ x x ^ ∥ 2 Let the inner product be characterized by any arbitrary positive definite weighting matrix.
∥ x ^ ∥ 2 = ∥ A c ∥ 2 = ⟨ A c , A c ⟩ = c H ( A H W A ) c = c H R c = c H p = p H R − 1 p = x H W H A ( A H W A ) − 1 A H W x \begin{align*} \lVert \hat{\pmb x} \rVert^2 &= \lVert A \pmb c \rVert^2 \\ &= \langle A \pmb c, A \pmb c \rangle \\ &= \pmb c^H (A^HWA) \pmb c \\ &=\pmb c^H R \pmb c \\ &=\pmb c^H \pmb p \\ &= \pmb p^H R^{-1}\pmb p \\ &= \pmb x^H W^H A (A^H W A)^{-1} A^H W \pmb x \end{align*} ∥ x x ^ ∥ 2 = ∥ A c c ∥ 2 = ⟨ A c c , A c c ⟩ = c c H ( A H W A ) c c = c c H R c c = c c H p p = p p H R − 1 p p = x x H W H A ( A H W A ) − 1 A H W x x Therefore
∥ e min ∥ 2 = ∥ x ∥ 2 − ∥ x ^ ∥ 2 = x H W x + x H W H A ( A H W A ) − 1 A H W x = x H ( W − W H A ( A H W A ) − 1 A H W ) x = x H M x \begin{align*} \lVert \pmb e_{\min} \rVert^2 &= \lVert \pmb x \rVert^2 - \lVert \hat {\pmb x} \rVert^2 \\ &= \pmb x^H W \pmb x + \pmb x^H W^H A (A^H W A)^{-1} A^H W \pmb x \\ &= \pmb x^H(W - W^H A (A^H W A)^{-1} A^H W)\pmb x \\ &= \pmb x^HM \pmb x \end{align*} ∥ e e m i n ∥ 2 = ∥ x x ∥ 2 − ∥ x x ^ ∥ 2 = x x H W x x + x x H W H A ( A H W A ) − 1 A H W x x = x x H ( W − W H A ( A H W A ) − 1 A H W ) x x = x x H M x x Consider,
M 2 = ( W − W H A ( A H W A ) − 1 A H W ) ( W − W H A ( A H W A ) − 1 A H W ) = W W − W W H A ( A H W A ) − 1 A H W − W H A ( A H W A ) − 1 A H W + W H A ( A H W A ) − 1 A H W W H A ( A H W A ) − 1 A H W \begin{align*} M^2 &= (W - W^H A (A^H W A)^{-1} A^H W)(W - W^H A (A^H W A)^{-1} A^H W) \\ &= WW - WW^H A (A^H W A)^{-1} A^H W - W^H A (A^H W A)^{-1} A^H W + W^H A (A^H W A)^{-1} A^H W W^H A (A^H W A)^{-1} A^H W \end{align*} M 2 = ( W − W H A ( A H W A ) − 1 A H W ) ( W − W H A ( A H W A ) − 1 A H W ) = WW − W W H A ( A H W A ) − 1 A H W − W H A ( A H W A ) − 1 A H W + W H A ( A H W A ) − 1 A H W W H A ( A H W A ) − 1 A H W Which clearly doesn't reduce to M M M W = I W=I W = I