0
$\begingroup$

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 $<z_{j},z_{m}>=0$ for $j\neq m$. The steps that I have gone through are:

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

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

However, I know that $<x_{j},x_{m}>\neq 0$, in general. Thus, I do not know how to move on from there to conclude: \begin{equation} <x_{j},x_{m}>=\sum_{l=0}^{m-1}\gamma_{lm}\gamma_{lj}<z_{l},z_{l}>+\sum_{k=0}^{j-1}\gamma_{kj}\gamma_{km}<z_{k},z_{k}> \\ -\sum_{k=0}^{j-1}\sum_{l=0}^{m-1}\gamma_{kj}\gamma_{lm}<z_{k},z_{l}>,\hspace{3mm} j\neq m \end{equation} 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 :)

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

1 Answer 1

0
$\begingroup$

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, X_2> }{<X_1, X_1>} 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{<X_3,R_1>}{<R_1, R_1>} R_1 - \frac{<X_3, R_2>}{<R_2, R_2>} 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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 30, 2022 at 19:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .