1
$\begingroup$

I am reading The Elements of Statistical Learning. This is a page from the partial least square section:

enter image description here

The exercise asks to prove the equivalence between Algorithm 3.3 and Eq. (3.64). Here's my attempt:

(Notation changes: unlike Algorithm 3.3, here let $\tilde{\phi}_m={\mathbf{X}^{(m-1)}}^\mathrm{T}\mathbf{y}$, and $\hat{\phi}_m=\tilde{\phi}_m/\|\tilde{\phi}_m\|$, to meet the constraint $\|\alpha\|=1$.)

Since $\mathrm{Corr}^2(\mathbf{y},\mathbf{X}\alpha)\mathrm{Var}(\mathbf{X}\alpha)\propto(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha)^2$, let

$$ \mathcal{L}=\left(\mathbf{y}^\mathrm{T} \mathbf{X}\alpha\right)^2+\lambda\left(\|\alpha\|^2-1\right)+\sum_{l=1}^{m-1}\mu_l\alpha^\mathrm{T}S\hat{\phi}_l. $$

Then $$ \frac{\partial\mathcal{L}}{\partial \alpha}=0\Longrightarrow 2\left(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\right)\cdot\mathbf{X}^\mathrm{T}\mathbf{y}+2\lambda\alpha+\sum_{l=1}^{m-1}\mu_lS\hat{\phi}_l=0. $$

Take the inner product of $\frac{\partial\mathcal{L}}{\partial\alpha}$ and $\alpha$, since $\|\alpha\|^2=1$ and $\alpha^\mathrm{T}S\hat{\phi}_l=0$, we have $$ \lambda=-\left(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\right)^2. $$

Plug $\lambda$ in and take the inner product of $\frac{\partial\mathcal{L}}{\partial\alpha}$ and $\hat{\phi}_i$, since $\hat{\phi}_i^\mathrm{T}S\hat{\phi}_l=0\,(i\ne l)$, we have

$$ \mu_i=\frac{2\left(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\right)^2\left(\alpha^\mathrm{T}\hat{\phi}_i\right)-2\left(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\right)\left(\mathbf{y}^\mathrm{T}\mathbf{X}\hat{\phi}_i\right)}{\hat{\phi}_i^\mathrm{T}S\hat{\phi}_i} $$

So if $\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\ne 0$ (when $\mathbf{X}$ is not orthogonal, for example), we have

$$ \mathbf{X}^\mathrm{T}\mathbf{y}-\left(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\right)\cdot\alpha+\sum_{l=1}^{m-1}\frac{\left(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha\right)\left(\alpha^\mathrm{T}\hat{\phi}_i\right)-\mathbf{y}^\mathrm{T}\mathbf{X}\hat{\phi}_i}{\hat{\phi}_l^\mathrm{T}S\hat{\phi}_l}=0 $$

Let $\tilde{\alpha}=(\mathbf{y}^\mathrm{T}\mathbf{X}\alpha)\cdot\alpha$, then $\alpha=\tilde{\alpha}/\|\tilde{\alpha}\|$, so rewrite the equation as

$$ \tilde{\alpha}-\sum_{l=1}^{m-1}\frac{\tilde{\alpha}^\mathrm{T}\hat{\phi}_l}{\hat{\phi}_l^\mathrm{T}S\hat{\phi}_l}\cdot S\hat{\phi}_l=\mathbf{X}^\mathrm{T}\mathbf{y}-\sum_{l=1}^{m-1}\frac{\mathbf{y}^\mathrm{T}\mathbf{X}\hat{\phi}_l}{\hat{\phi}_l^\mathrm{T}S\hat{\phi}_l}\cdot S\hat{\phi}_l $$

On the other hand, from Algorithm 3.3, we have

$$\ \left\{ \begin{eqnarray} \mathbf{X}^{(0)}&=&\mathbf{X}\\ \mathbf{z}_m &=&\mathbf{X}^{(m-1)}{\mathbf{X}^{(m-1)}}^\mathrm{T}\mathbf{y}\\ \mathbf{x}^{(m)}_j&=&\mathbf{x}^{(m-1)}_j-\frac{\langle\mathbf{z}_m,\mathbf{x}^{(m-1)}_j\rangle}{\langle\mathbf{z}_m,\mathbf{z}_m\rangle}\cdot\mathbf{z}_m \end{eqnarray} \right. $$

Take the inner product of $\mathbf{x}^{(m)}_j$ and $\mathbf{y}$ and rewrite it in the matrix form, we have

\begin{align*} &{\mathbf{X}^{(m)}}^\mathrm{T}\mathbf{y}={\mathbf{X}^{(m-1)}}^\mathrm{T}\mathbf{y}-\frac{\langle\mathbf{z}_m,\mathbf{y}\rangle}{\langle\mathbf{z}_m,\mathbf{z}_m\rangle}\cdot{\mathbf{X}^{(m-1)}}^\mathrm{T}\mathbf{z}_m\\ \Longrightarrow& \tilde{\phi}_{m+1}=\tilde{\phi}_{m}-\frac{\tilde{\phi}_{m}^\mathrm{T}\tilde{\phi}_{m}}{\tilde{\phi}_{m}^\mathrm{T}{\mathbf{X}^{(m-1)}}^\mathrm{T}\mathbf{X}^{(m-1)}\tilde{\phi}_{m}}\cdot {\mathbf{X}^{(m-1)}}^\mathrm{T}\mathbf{X}^{(m-1)}\tilde{\phi}_{m} \end{align*}

I want to prove $\tilde{\alpha}=\tilde{\phi}_m$ by induction since the case of $m=1$ already holds, but I don't know how to connect the two equations of $\tilde{\alpha}$ and $\tilde{\phi}_m$. Any hints are welcome. Thanks.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.