3
$\begingroup$

This question regards the problem of Generalized Least Squares. Vectors and matrices will be denoted in bold.

Premises. Let $N,K$ be given integers, with $K \gg N > 1$. The transpose of matrix $\mathbf{A}$ will be denoted with $\mathbf{A}^T$. Suppose the following statistical model holds $$ (*) \quad \mathbf{y} = \mathbf{Hx + n}, \quad \mathbf{n} \sim \mathcal{N}_{K}(\mathbf{0}, \mathbf{C}) $$ where $\mathbf{y} \in \mathbb{R}^{K \times 1}$ are the observables, $\mathbf{H} \in \mathbb{R}^{K \times N}$ is a known full-rank matrix, $\mathbf{x} \in \mathbb{R}^{N \times 1}$ is a deterministic vector of unknown parameters (which we want to estimate) and finally $\mathbf{n} \in \mathbb{R}^{K \times 1}$ is a disturbance vector (noise) with a known (positive definite) covariance matrix $\mathbf{C} \in \mathbb{R}^{K \times K}$. The Maximum Likelihood (ML) estimate of $\mathbf{x}$, denoted with $\hat{\mathbf{x}}_{ML}$, is given by $$ (1) \quad \hat{\mathbf{x}}_{ML} = (\mathbf{H}^T \mathbf{C^{-1}} \mathbf{H})^{-1} \mathbf{H}^T \mathbf{C}^{-1} \mathbf{y} $$ and this is also the standard formula of Generalized Linear Least Squares (GLLS). Consider the standard formula of Ordinary Least Squares (OLS) for a linear model, i.e. $$ (2) \quad \hat{\mathbf{x}}_{OLS} = (\mathbf{H}^T \mathbf{H})^{-1} \mathbf{H}^T \mathbf{y} $$ As a final note on notation, $\mathbf{I}_K$ is the $K \times K$ identity matrix and $\mathbf{O}$ is a matrix of all zeros (with appropriate dimensions).


Now, for the problem at hand, assume that $\mathbf{C}^{-1} = \mathbf{I}_K + \mathbf{X}$, where $\mathbf{X} \in \mathbb{R}^{K \times K}$ is a symmetric, invertible matrix (and, for the formalism to make sense, $\mathbf{X}$ is such that $\mathbf{I}_K + \mathbf{X}$ is invertible and the inverse is positive definite). In this case, it can be proven (using matrix inversion lemma) that $$ (3) \quad (\mathbf{H}^T \mathbf{C^{-1}} \mathbf{H})^{-1} \mathbf{H}^T \mathbf{C}^{-1} = (\mathbf{H}^T \mathbf{H})^{-1} \mathbf{H}^T + \mathbf{Q} $$ where the expression for the matrix $\mathbf{Q} \in \mathbb{R}^{N \times K}$ can be found (I will omit it here). Now, finally,

Proposition 1. If $\mathbf{H}^T\mathbf{X} = \mathbf{O}_{N,K}$, then equation $(1)$ degenerates in equation $(2)$, i.e., there exists no difference between GLLS and OLS.

The proof is straigthforward and is valid even if $\mathbf{X}$ is singular. Now, my question is

Question: Can an equation similar to eq. $(3)$ (which "separates" an OLS-term from a second term) be written when $\mathbf{X}$ is a singular matrix?

I am not interested in a closed-form of $\mathbf{Q}$ when $\mathbf{X}$ is singular. But I do am interested in understanding the concept beyond that expression: what is the actual role of $\mathbf{Q}$? In which space does it operate?

I found this problem during a numerical implementation where both OLS and GLLS performed roughly the same (the actual model is $(*)$), and I cannot understand why OLS is not strictly sub-optimal. I found this slightly counter-intuitive, since you know a lot more in GLLS (you know $\mathbf{C}$ and make full use of it, why OLS does not), but this is somehow "useless" if some conditions are met. What are these conditions?

As a final note, I am rather new to the world of Least Squares, since I generally work within a ML-framework (or MMSE in other cases) and never studied the deep aspects of GLLS vs OLS, since, in my case, they are just intermediate steps during the derivation of MLE for a given problem.

If the question is, in your opinion, a bit too broad, or if there is something I am missing, could you please point me in the right direction by giving me references? Preferably well-known books written in standard notation.

$\endgroup$
  • $\begingroup$ The matrix inversion lemma in the form you use it relies on the matrix $\mathbf X$ being invertible. Intuitively, I would guess that you can extend it to non-invertible (positive-semidifenite?) matrices by using the Moore-Penrose pseudo-inverse, but of course this is very far from a mathematical proof ;-) $\endgroup$ – davidhigh Jul 8 '14 at 14:34
  • $\begingroup$ Thank you for your comment. It was the first thought I had, but, intuitively, it is a bit too hard problem and, if someone managed to actually solve it in closed form, a full-fledged theorem would be appropriate to that result. Anyway, if you have some intuition on the other questions I asked, feel free to add another comment. $\endgroup$ – PseudoRandom Jul 8 '14 at 18:51
  • $\begingroup$ Two questions. One: I'm confused by what you say about the equation $C^{-1}=I+X$. There is no assumption involved in this equation, is there? Doesn't the equation serve to define $X$ as $X=C^{-1}-I$? And doesn't $X$, as the difference between two symmetric matrixes, have to be symmetric--no assumption necessary? Two: I'm wondering if you are assuming either that $y$ and the columns of $H$ are each zero mean or if you are assuming that one of the columns of $H$ is a column of 1s. It would be very unusual to assume neither of these things when using the linear model. $\endgroup$ – Bill Jul 11 '14 at 19:51
  • $\begingroup$ 1. $X$ is symmetric without assumptions, yes. However, $X = C^{-1} - I$ is correct but misleading: $X$ is not defined that way, $C^{-1}$ is (because of its structure). Consider the simple case where $C^{-1}$ is a diagonal matrix, where each element on the main diagonal is of the form: $1 + x_{ii}$, with $x_{ii} > 1$. You would write that matrix as $C^{-1} = I + X$. 2. Unfortunately, no matter how unusual it seems, neither assumption holds in my problem. However, if you can solve the problem with the last column of $H$ being all 1s, please do so, it would still be an important result. $\endgroup$ – PseudoRandom Jul 12 '14 at 11:11
5
+50
$\begingroup$

There are two questions. First, there is a purely mathematical question about the possibility of decomposing the GLS estimator into the OLS estimator plus a correction factor. Second, there is a question about what it means when OLS and GLS are the same. (I will use ' rather than T throughout to mean transpose).

Also, I would appreciate knowing about any errors you find in the arguments.

Question 1

Ordinary Least Squares (OLS) solves the following problem: \begin{align} min_x\;\left(y-Hx\right)'\left(y-Hx\right) \end{align} leading to the solution: \begin{align} \hat{x}_{OLS}=\left(H'H\right)^{-1}H'y \end{align} Generalized Least Squares (GLS) solves the following problem: \begin{align} min_x\;\left(y-Hx\right)'C^{-1}\left(y-Hx\right) \end{align} leading to the solution: \begin{align} \hat{x}_{OLS}=\left(H'C^{-1}H\right)^{-1}H'C^{-1}y \end{align} Now, make the substitution $C^{-1}=X+I$ in the GLS problem: \begin{align} min_x\;&\left(y-Hx\right)'\left(X+I\right)\left(y-Hx\right)\\~\\ min_x\;&\left(y-Hx\right)'X\left(y-Hx\right) + \left(y-Hx\right)'\left(y-Hx\right)\\ \end{align} The solution is still characterized by first order conditions since we are assuming that $C$ and therefore $C^{-1}$ are positive definite: \begin{align} 0=&2\left(H'XH\hat{x}_{GLS}-H'Xy\right) +2\left(H'H\hat{x}_{GLS}-H'y\right)\\ \hat{x}_{GLS}=&\left(H'H\right)^{-1}H'y+\left(H'H\right)^{-1}H'Xy -\left(H'H\right)^{-1}H'XH\hat{x}_{GLS}\\ \hat{x}_{GLS}=& \hat{x}_{OLS} + \left(H'H\right)^{-1}H'Xy -\left(H'H\right)^{-1}H'XH\hat{x}_{GLS}\\ \end{align}

I can see two ways to give you what you asked for in the question from here. First, we have a formula for the $\hat{x}_{GLS}$ on the right-hand-side of the last expression, namely $\left(H'C^{-1}H\right)^{-1}H'C^{-1}y$. Thus, the above expression is a closed form solution for the GLS estimator, decomposed into an OLS part and a bunch of other stuff. The other stuff, obviously, goes away if $H'X=0$. To be clear, one possible answer to your first question is this: \begin{align} \hat{x}_{GLS}=& \hat{x}_{OLS} + \left(H'H\right)^{-1}H'Xy -\left(H'H\right)^{-1}H'XH\left(H'C^{-1}H\right)^{-1}H'C^{-1}y\\ \hat{x}_{GLS}=& \hat{x}_{OLS} + \left(H'H\right)^{-1}H'X \left(I -H\left(H'C^{-1}H\right)^{-1}H'C^{-1}\right)y \end{align} I can't say I get much out of this. That awful mess near the end multiplying $y$ is a projection matrix, but onto what?

Another way you could proceed is to go up to the line right before I stopped to note there are two ways to proceed and to continue thus: \begin{align} \left(I+\left(H'H\right)^{-1}H'XH\right)\hat{x}_{GLS}=& \hat{x}_{OLS} + \left(H'H\right)^{-1}H'Xy\\ \hat{x}_{GLS}=& \left(I+\left(H'H\right)^{-1}H'XH\right)^{-1}\left(\hat{x}_{OLS} + \left(H'H\right)^{-1}H'Xy\right) \end{align} Again, GLS is decomposed into an OLS part and another part. The other part goes away if $H'X=0$. I still don't get much out of this. What this one says is that GLS is the weighted average of OLS and a linear regression of $Xy$ on $H$. I guess you could think of $Xy$ as $y$ suitably normalized--that is after having had the "bad" part of the variance $C$ divided out of it.

I should be careful and verify that the matrix I inverted in the last step is actually invertible: \begin{align} \left(I+\left(H'H\right)^{-1}H'XH\right) &= \left(H'H\right)^{-1}\left(H'H+H'XH\right)\\ &= \left(H'H\right)^{-1}H'\left(I+X\right)H\\ &= \left(H'H\right)^{-1}H'C^{-1}H \end{align}

Question 2

The question here is when are GLS and OLS the same, and what intuition can we form about the conditions under which this is true? I will only provide an answer here for a special case on the structure of $C$. The requirement is: \begin{align} \left(H'C^{-1}H\right)^{-1}H'C^{-1}Y = \left( H'H\right)^{-1}H'Y \end{align}

To form our intuitions, let's assume that $C$ is diagonal, let's define $\overline{c}$ by $\frac{1}{\overline{c}}=\frac{1}{K}\sum \frac{1}{C_{ii}}$, and let's write: \begin{align} \left(H'C^{-1}H\right)^{-1}H'C^{-1}Y &= \left(H'\overline{c}C^{-1}H\right)^{-1}H'\overline{c}C^{-1}Y\\ &=\left( H'H\right)^{-1}H'Y \end{align}

One way for this equation to hold is for it to hold for each of the two factors in the equation: \begin{alignat}{3} \left(H'\overline{c}C^{-1}H\right)^{-1} &=\left( H'H\right)^{-1} & \iff& & H'\left(\overline{c}C^{-1}-I\right)H&=0\\ H'\overline{c}C^{-1}Y&=H'Y & \iff& & H'\left(\overline{c}C^{-1}-I\right)Y&=0 \end{alignat} Remembering that $C$, $C^{-1}$, and $I$ are all diagonal and denoting by $H_i$ the $i$th row of $H$: \begin{alignat}{3} H'\left(\overline{c}C^{-1}-I\right)H&=0 & \iff& & \frac{1}{K} \sum_{i=1}^K H_iH_i'\left( \frac{\overline{c}}{C_{ii}}-1\right)=0\\~\\ H'\left(\overline{c}C^{-1}-I\right)Y&=0 & \iff& & \frac{1}{K} \sum_{i=1}^K H_iY_i\left( \frac{\overline{c}}{C_{ii}}-1\right)=0 \end{alignat} What are those things on the right-hand-side of the double-headed arrows? They are a kind of sample covariance. To see this, notice that the mean of $\frac{\overline{c}}{C_{ii}}$ is 1, by the construction of $\overline{c}$. Finally, we are ready to say something intuitive. In this special case, OLS and GLS are the same if the inverse of the variance (across observations) is uncorrelated with products of the right-hand-side variables with each other and products of the right-hand-side variables with the left-hand-side variable. This is a very intuitive result.

In estimating the linear model, we only use the products of the RHS variables with each other and with the LHS variable, $(H'H)^{-1}H'y$. In GLS, we weight these products by the inverse of the variance of the errors. When does that re-weighting do nothing, on average? Why, when the weights are uncorrelated with the thing they are re-weighting! Yes? When is a weighted average the same as a simple average? When the weights are uncorrelated with the things you are averaging.

This insight, by the way, if I am remembering correctly, is due to White(1980) and perhaps Huber(1967) before him---I don't recall exactly.

$\endgroup$
  • $\begingroup$ A very detailed and complete answer, thanks! Matrix notation sometimes does hide simple things such as sample means and weighted sample means. $Q = (H′H)^{−1}H′X(I−H(H′C^{−1}H)^{−1}H′C^{−1})$ does seem incredibly obscure. However, I'm glad my intuition was correct in that GLS can be decomponsed in such a way, regardless if $X$ is invertible or not. Anyway, thanks again! $\endgroup$ – PseudoRandom Jul 13 '14 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.