Multiple Regression - Normal equations and features normalization (whitening)

Question

In the multivariate regression analysis, it is easy and natural to conclude that the coefficients of the regression are given by the so-called normal equation

$\hat{\beta}=(X^TX)^{-1}X^T y$

My doubt is related to the role of the term $(X^TX)^{-1}$. On Flach's Machine learning book, it is stated that $(X^TX)^{−1}$ acts as a transformation that decorrelates, centres and normalises the features, and I quote:

Let us try to understand the term $(X^TX)^{−1}$ a bit better. Assume that the features are uncorrelated (meaning the covariance between every pair of different features is 0) in addition to being zero-centred. ... the covariance matrix $\Sigma$ is diagonal with entries $\sigma_{jj}$ . Since $(X^TX)= n(\Sigma+M)$, and since the entries of $M$ are 0 because the columns of $X$ are zero-centred, this matrix is also diagonal with entries $n\sigma_{jj}$ – in fact, it is the matrix S referred to above. In other words, assuming zero-centred and uncorrelated features, $(X^TX)^{−1}$ reduces to our scaling matrix $S^{−1}$.In the general case we cannot make any assumptions about the features, and $(X^TX)^{−1}$ acts as a transformation that decorrelates, centres and normalises the features.

I am aware that to decorrelate and normalize a data set is known as whitening. A whitening matrix $W$ is such that $Z=WX$ decorrelates $X$; i.e., even if $X$ is correlated, the covariance of $Z$ will be diagonal. Usually, $W$ is determined via the eigen-decomposition of $\Sigma$ or the Cholesky decomposition of $\Sigma ^{-1}$, among other procedures, but nothing like $(X^TX)^{−1}$ (not that I am aware of).

Intrigued with what, I ran some simulations in Matlab where some random (and correlated) multivariate matrices were transformed by using the transformation $W_{Flach}=(X^TX)^{−1}$ and also $W_{Flach}=\Sigma^{-1}_X$ (the latter corresponds to the "cov" function in Matlab, which returns the covariance matrix of a matrix of data). It didn't work in either way: $Z=W_{Flach}X$ was surely transformed, but remained correlated.

I also tried the ZCA whitening (sometimes called Mahalanobis whitening, here), which uses the transformation $W_{ZCA}=\Sigma_x^{\frac{-1}{2}}$ in my simulations and, not surprisingly, it worked as expected: $Z=W_{ZCA}X$ becomes uncorrelated.

Finally, it is also clear that $W_{Flach}$ does not comply with the definition of a whitening transformation - if $W$ is a whitener, then $W^T W=\Sigma^{-1}$. Well, whereas $W_{ZCA}^T W_{ZCA}$ is identical to $\Sigma^{-1}$, $W_{Flach}^T W_{Flach}$ is obviously not. So, it is crystal clear that $W_{Flach}$ can not be a whitening transformation. And that is driving me crazy: as far as I know, to state that $W_{Flach}$ "decorrelates the features" is plainly wrong - if it was, it would decorrelate $X$, right? So, why on Earth Flach says that in his book?

One point caught my attention. Later on in his book, Flach defines the Mahalanobis distance as

$Dis_M=(x,y|\Sigma)=\sqrt{(x-y)^T\Sigma^{-1}(x-y)}$

and states that using the covariance matrix in this way has the effect of decorrelating and normalising the features, as we saw in Section 7.1 ("Section 7.1" is the quotation I made at the beginning).

Now, the Mahalanobis distance is applied in a different context: it takes the difference between two vectors, calculates the weighted product of this difference by itself and then takes the square root of the result; i.e., computes a normalized distance (the weighting factor is $(X^T X)^{-1} X$). While that is certainly a normalized measure, it is not the same as whitening $X$. Computing $\sqrt{((x-y)^T\Sigma^{-1}(x-y))}$ sounds pretty different from taking the product of $(X^T X)^{-1}$ by $X$. For a start, Flach doesn't assert that $X$ is centered, so $(X^T X)^{-1} X$ is not $N\Sigma^{-1}$.

Peter Flach is a renowned author and his book is well accepted in the academia, so probably I am missing something. I refuse to believe that Flach confused $\Sigma^{-1}$ for $\Sigma^\frac{-1}{2}$ and, in fact, he speaks about the decorrelation proprieties of $(X^TX)^{−1}$ along his book several times. Anyone could shed some light on that?

Answer 1

I think there are two ways to think about this that may be helpful. The first is to explore the relationship between linear regressions and Mahalanobis Distance (MD), and realize that just how $(X'X)^{-1}$ acts there to essentially 'standardize' multivariate data by introducing orthogonal coordinates and re-scaling an ellipse into a circle, it's doing the same thing here. See this question for an excellent discussion of MD, and some of the answers there should provide some great intuition and understanding.

The second way is a geometric understanding of $(X'X)^{-1}$. We have $Y = X\beta + \epsilon$, $X \in \mathbb{R}^{n\times m}$. Then $Y,X\beta \in \mathbb{R}^n$, and we can think of $X\hat{\beta}$ as being in some subspace of $\mathbb{R}^n$ that corresponds to the span of vectors $X_1,\dots,X_m$. Since we are so used to $X\hat{\beta}$ as having regression-interpretation, lets consider some vector $w$ in the subspace. Linear algebra gives us different ways of representing $w$.

First, we can think of $w$ using our basis $X_1,\dots,X_m$, and so $$w = \alpha_1X_1+ \dots + \alpha_mX_m$$ and so given the basis $X$ is fixed, $a$ defines $w$.

Alternatively, we can represent $w$ by considering the orthogonal projections of $w$ onto each $X_i$. Then we can represent $w$ as $w = (c_1,\dots,c_m)$, where $c_i = X_i'w$, and so $c = X'w$.

Why is this useful? Well now let's go back to regression-land. Instead of considering $w$, let $w = X\beta$, and so $\alpha_i$ from above is equal to $\beta_i$. Then we also have $$c = X'w = X'X\beta$$ and so $(X'X)$ is the linear transformation from $\beta$ to $c$, or, in other words, measures how much $X_i$ projects into the other $X_j$'s, and each component of $(X'X)_{ij}$ measures how much $X_i$ projects onto $X_j$ (think about what would happen if the $X_i$ are linearly independent). So then what is $(X'X)^{-1}$? Well it's simply the inverse transformation of $(X'X)$, and in our context, is the map that takes us from $c$ to $\beta$. So we have $$\beta = (X'X)^{-1}c$$ and so recalling that $c = X'X\beta = X'y$, we can think of $(X'X)^{-1}$ as the map that takes $X'y$, which we can think of 'dirtily' projecting $y$ to $X$, and 'cleans it up' by spitting out $\beta$, which corresponds to the coordinates given the spanning vectors $X$. What this amounts to is essentially decorrelating, centering, and normalizing $X$ so that we get $\beta$ in the coordinate space defined by $X$.

Answer 2

In my opinion, Flach’s statement regarding the role of the term $({X^TX})^{-1}$ is fuzzy and should be restated for clarity. It seems a reference to the Mahalanobis’ distance, as @doubled properly pointed out, but I was unable to follow his reasoning, as I remarked in the comments section of his answer.

I never had a formal training in mathematics, which maybe explains the trouble I am experiencing to grasp @doubled’s answer, but after a while I have got the rationale behind Flach’s statement. Now it is clear to me that Flach resorts to the reader’s intuition to introduce subjects that actually require some math background, which is essentially good but has a side effect: those who have more than zero background in Mathematics struggle to understand his reasoning given that it is based almost exclusively on inspection instead of a formal mathematical derivation. In a nutshell, I concluded that it was not I that failed to get Flach's point, but he that failed to demonstrate it clearly. Anyway, that is a minor issue in his book, which is sound and comprehensive. Given that a few people up voted my question, I felt it was convenient post my conclusions here, as follows.

Statement of the Problem

Claim: $({X^TX})^{-1}$ acts as a whitening transformation that decorrelates, centres and normalises the features $X$

Analysis: such a claim seems related to the definition of the Mahalanobis distance $M_D$, which employs the term $({X^TX})^{-1}$ in its formulation to normalize the values of distances calculated in a space characterized by non-spherical distributions. Centering consists in subtracting $\mathbb{E}X$ from $X$, which is not what $(X^TX)^{-1}$ does in the Mahalanobis’ formula. Decorrelating and normalizing a random variable is an algebraic procedure known as whitening and no whitening procedure I am aware of uses the term $(X^TX)^{-1}$. The so called Mahalanobis whitening is defined by the term $(X^TX)^{-\frac{1}{2}}$, which can be derived from $M_D$.

Proof: The reasoning proceeds in four steps: (1) the whitening procedures is succinctly described, (2) some remarks and assumptions are made, (3) the Mahalanobis’ is scrutinized, and (4) it is shown that the normal equations lead to a certain “hat matrix” that implicitly refer to a whitening procedure known as Mahalanobis whitening. With that, I show what Flach really meant and put his (bold) statement in perspective: no, $({X^TX})^{-1}$ is not a whitening transformation.

STEP (1) – Whitening

Whitening is a linear transformation intended to both normalize and decorrelate a given random variable $X$. In multivariate analysis, $X$ is a matrix whose rows $x_i$ are the realizations (observations) of some random process characterized by some features (the columns of $X$). As decorrelated multivariate data show a circular pattern when plotted, this transformation is also known as sphering.

By definition, $W$ is a whitening transformation (a sphering matrix) if $Z=XW$ and the covariance of the random variable $Z$, $\Sigma_Z$, is diagonal and unitary; i.e., $\Sigma_Z = \mathbb{I}$. It is trivial to show that $\Sigma_Z = \mathbb{I} \implies W W^T=\Sigma^{-1}_x$.

STEP (2) – Assumptions

• Assumption 0 (whitening transformation): let $X$ a random variable with a non-diagonal covariance matrix $\Sigma_x$. If we define a whitening matrix $W$ such that $Z=X W$ and $\Sigma_Z = \mathbb{I}$, then it is trivial to show that $W W^T=\Sigma^{-1}_x$
• Assumption 1 (Sample covariance): $\mathbb{E} X^TX = \Sigma_x=\frac{1}{N} X^TX $ if, and only if, $\mathbb{E} X$ = 0
• Assumption 2 (definition of the matrix square root): Differently from real numbers, a matrix can have several square roots. By definition, a matrix $A_{sqrt}$ is said to be a square root of $B$ if the matrix product $A_{sqrt} A_{sqrt} = B$. Equivalently, $\Sigma_x = {\Sigma^\frac{1}{2}_x} {\Sigma^\frac{1}{2}_x}$
• Assumption 3 (the square root of $\Sigma_x$ is symmetric): $\Sigma^\frac{1}{2}_x = {(\Sigma^\frac{1}{2}_x})^T$
• Assumption 4 (squaring and inversion are commutative): ${\Sigma^{-\frac{1}{2}}_x} = {(\Sigma^\frac{1}{2}_x)}^{-1}$
• Assumption 5 (covariance of a linear transformation): $\mathbb{E} X^TX = \Sigma_x$ implies that the covariance of a linear transformation $AX$ is the covariance of $A(X-\mathbb{E} X)$ which is $A\Sigma_X A^T$
• Assumption 6 (normal equations): given an unknown multivariate function $y=f(x)$, the estimated coefficients of the corresponding linear regression analysis are collected in a vector $\hat{\beta}$ such that $\hat{\beta}= (X^TX)^{-1} X^T Y $

STEP (3) – Mahalanobi’s distance

The Mahalanobis’ distance $D_M$ gives the dissimilarity degree between two random vectors $u$ and $v$ in a features space characterized by a distribution $f(x)$ whose covariance matrix is $\Sigma_x$. It may be thought as a generalized form for the Euclidean distance given that it weights the Euclidean distance by $\Sigma_x^{-1}$, as given by the formula $D_M=\sqrt{u^T \Sigma_x^{-1} v}$.

By weighting the Euclidean distance with the inverse covariance matrix of the underlying distribution of $X$, the Mahalanobis’ distance considers how data points spread out around their mean in the Cartesian space, something ignored by its Euclidean counterpart. As a matter of fact, if the spread is symmetrical (spherical) the covariance matrix will be diagonal and both Euclidean and Mahalanobis distance will be equivalent in the sense that the loci defined by a constant distance will be a sphere. If the spread is not symmetrical, a constant Mahalanobi’s distance will still define a sphere due the weighting factor $\Sigma_x^{-1}$, but the Euclidean one will define a ellipsoid (here).

Often, it is convenient to consider the Mahalanobis’ distance as a multivariate generalization of of the univariate standardization procedure (z-scores), in which the distance between $u$ and $v$ is measured in standard deviations.

Consider the problem of computing the weighted distance between the points $x$ and $\mu = \mathbb{E} X$, under Assumptions 2 and 3. For convenience, we will deal with the squared Mahalanobis’ distance, as follows:

$ D^2_M = (x-\mu)^T \Sigma_x^{-1} (x-\mu) \\ D^2_M = (x-\mu)^T (\Sigma_x^{-\frac{1}{2}} \Sigma_x^{-\frac{1}{2}})(x-\mu) \\ D^2_M = ((x-\mu)^T \Sigma_x^{-\frac{1}{2}}) (\Sigma_x^{-\frac{1}{2}}(x-\mu)) \\ D^2_M = (\Sigma_x^{-\frac{1}{2}} (x-\mu))^T (\Sigma_x^{-\frac{1}{2}}(x-\mu)) $

If we define $z \triangleq \Sigma_x^{-\frac{1}{2}} (x-\mu) $, then

$ D^2_M = z^T z = ||z|| $

We note that $z$ is the result of a linear transformation given by $z=\Sigma^{-\frac{1}{2}}_x (x-\mu)$.By assumptions 2 and 5, the covariance of $z$ can be computed as

$ \Sigma_z = \textrm{cov}(Z)= \textrm{cov} (\Sigma^{-\frac{1}{2}}_x (X-\mu)) = \textrm{cov} (\Sigma^{-\frac{1}{2}}_x X) \\ \textrm{cov} (\Sigma^{-\frac{1}{2}}_x X) = \Sigma^{-\frac{1}{2}}_x \Sigma_x (\Sigma^{-\frac{1}{2}}_x)^T = \Sigma^{-\frac{1}{2}}_x (\Sigma^{\frac{1}{2}}_x \Sigma^{\frac{1}{2}}_x) \Sigma^{-\frac{1}{2}}_x = (\Sigma^{-\frac{1}{2}}_x \Sigma^{\frac{1}{2}}_x) (\Sigma^{\frac{1}{2}}_x \Sigma^{-\frac{1}{2}}_x) = \mathbb{I} $

So, we conclude that the transformation $Z=\Sigma^{-\frac{1}{2}}_x X$ is a whitening transformation with $W=\Sigma^{-\frac{1}{2}}_x $. In fact, this kind of whitening is called ZCA whitening (where ZCA stands for “zero-phase components analysis”) or Mahalanobis whitening (here).

STEP (4) – The Hat Matrix

From the multivariate regression analysis, the estimates $\hat{Y}$ are given in function of a set of estimated parameters $\hat{\beta}$; i.e.,

$ \hat{Y}=X \hat{\beta} \\ \hat{\beta}= (X^TX)^{-1} X^T Y \\ \therefore \hat{Y}= X (X^TX)^{-1} X^T Y \\ $

Using this result and Assumption 6, we can define the so-called hat matrix $H$ and define $\hat{Y}$ in terms of $H$:

$H \triangleq X (X^TX)^{-1} X^T \implies \hat{Y}=HY$

, where $\hat{Y}=HY$ justifies the mnemonic "the hat matrix puts a hat on y". Now, let us pay a closer attention to the hat matrix $H= X (X^TX)^{-1} X^T$ and factor it as appropriate, using Assumptions 0, 1 and 3 and, furthermore, assuming that $X$ is zero-centered:

$ H = X (X^TX)^{-1} X^T = \\ H = N X \Sigma_x^{-1} X^T = \\ H = N X (\Sigma_x^{-\frac{1}{2}} \Sigma_x^{-\frac{1}{2}}) X^T = \\ H = N (X \Sigma_x^{-\frac{1}{2}}) ( \Sigma_x^{-\frac{1}{2}} X^T) = \\ H = N (X \Sigma_x^{-\frac{1}{2}}) (X \Sigma_x^{-\frac{1}{2}}) ^T \\ \therefore \hat{Y} = N (X \Sigma_x^{-\frac{1}{2}}) (X \Sigma_x^{-\frac{1}{2}}) ^T Y $

Now we have all we need to establish if $\Sigma_x^{-1}$ effectively decorrelates, centres and normalizes the features $X$ as stated by Flach. By factoring the hat matrix definition as above and defining $Z\triangleq X \Sigma_x^{-\frac{1}{2}}$ then we have

$ \hat{Y} = N Z Z^T Y $

Hence, the linear regression actually decorrelates $X$ via the aforementioned Mahalanobis whitening, something we represented by $Z= X \Sigma_x^{-\frac{1}{2}}$ in the results above. Right afterwards, this result is squared ($Z Z^T$) and then multiplied by $Y$ (and $N$). So, yes, to “put a hat in Y” amounts to whitening $X$ as an intermediary step – but that does not mean that $\Sigma_x^{-1}$ “decorrelates the features”. Flach probably meant something like “the term $\Sigma_x^{-1}$ appears in the hat matrix multiplied by $X$ on both sides. Given that $\Sigma_x^{-1}=\Sigma_x^{-\frac{1}{2}} \Sigma_x^{-\frac{1}{2}}$ , it is clear that $\hat{Y}$ is a function of a decorrelated version of $X$”. A huge difference from the original statement – specially considering Flach didn’t defined the hat matrix $H$. It is pretty hard to follow his reasoning without an extensive derivation as I did here.

In a nutshell: it is inaccurate to state that $(X^TX)^{-1}$ acts as a transformation that decorrelates, centres and normalises the features. It is, at best, a reference to another context (Mahalanobis’ formula) and, therefore, should be put in perspective in Flach’s book.