# Multiple regression by successive orthogonalization

I was studying The Elements of Statistical Learning book and trying to understand the section where multiple linear regression is explained by successive orthogonalization procedure, i.e. Gram-Schmidt alghoritm. I am trying to prove that the different residuals are orthogonal, in other words $$=0$$ for $$j\neq m$$. The steps that I have gone through are:

$$$$\begin{split} =<(x_{j}-\sum_{k=0}^{j-1}\gamma_{kj}z_{k}),(x_m-\sum_{l=0}^{m-1}\gamma_{lm}z_{l})>=-\sum_{l=0}^{m-1}\gamma_{lm}-\sum_{k=0}^{j-1}\gamma_{kj} +\sum_{k=0}^{j-1}\sum_{l=0}^{m-1}\gamma_{kj}\gamma_{lm}. \end{split}$$$$

Then, I have used the fact that $$\gamma_{lj}=\frac{}{}$$: $$$$=-\sum_{l=0}^{m-1}\gamma_{lm}\gamma_{lj}-\sum_{k=0}^{j-1}\gamma_{kj}\gamma_{km} \\ +\sum_{k=0}^{j-1}\sum_{l=0}^{m-1}\gamma_{kj}\gamma_{lm}.$$$$

However, I know that $$\neq 0$$, in general. Thus, I do not know how to move on from there to conclude: $$$$=\sum_{l=0}^{m-1}\gamma_{lm}\gamma_{lj}+\sum_{k=0}^{j-1}\gamma_{kj}\gamma_{km} \\ -\sum_{k=0}^{j-1}\sum_{l=0}^{m-1}\gamma_{kj}\gamma_{lm},\hspace{3mm} j\neq m$$$$ so that the dot product of different residuals are exactly zero.

I do not know if my approach even makes sense. By intuition, I know that regressing $$x_{j}$$ on $$z_{0},z_{1},...,z_{j-1}$$ already creates a residual vector $$z_{j}$$ that is orthogonal to all $$z_{0},z_{1},...,z_{j-1}$$ if we start with $$z_{0}=1$$ and $$x_{0}=1$$. However, I want to show this by the above method that I carry out, as well. I have added the orthogonalization procedure as a figure.

Procedure

Thanks in advance :)

• Suggestion: Try googling Gram-Schmidt orthogonalization and looking at numerical examples to get a sense of what I happening in the recursive algorithm. Oct 29, 2022 at 17:41

## 1 Answer

Edit in response to follow-up comments. Apparently you wish to confirm that all residuals are mutually orthogonal.

Let's review Gram-Schmidt.

Step 1 in Gram Schmidt: Select vector $$X_1$$ and take it as our first basis vector for a new basis. We can call it $$R_1$$

Step 2. Select $$X_2$$ and split it into a part that is parallel to $$X_1$$ and a residual part that is perpendicular to $$X_1$$. The residual part is $$R_2=X_2- \frac{ }{} X_1$$.

(To verify that $$R_2$$ is perpendicular $$X_1$$, just dot it with $$X_1$$ and verify cancellation.) Except in degenerate cases where $$R_2=0$$, we can take this as a second basis vector orthogonal to the first and continue.

Next step. Let $$R_3$$ be the residual part of $$X_3$$ after you remove the projection of $$X_3$$ in the span of the prior orthogonal vectors. That is, $$R_3= X_3- \frac{}{} R_1 - \frac{}{} R_2$$. You can verify that $$R_3$$ is orthogonal to say $$R_1$$ by dotting with $$R_1$$. It's the same sort of calculation as in the prior step, since $$R_1$$ does not "see" $$R_2$$, because that pair $$(R_1,R_2)$$ is known to be orthogonal by the prior step.

Likewise you can check that $$R_3\perp R_2$$.

Thus by construction each residual is orthogonal to its predecessors. Ditto for all subsequent steps.

• Hi and thank you for your answer! I understand the procedure of choosing an orthogonal basis for the projection. We want it since the basis constructed by the ordinary x vectors are not orthogonal in most of the situations, i.e. there is correlation between the feature vectors. We do this by the Gram-Schmidt procedure, in other words by regressing the feature vectors onto the residuals to obtain an orthogonal basis for the projection. However, I cannot prove mathematically that these residuals are in fact orthogonal, which is what I am trying to do in the method above. Oct 30, 2022 at 19:18