---
title: "OCVX2 : Tout ce que vous avez toujours voulu savoir sur l'ACP (ou pas)"
date: 2021-10-27 10:00
categories: [Image S9, OCVX2]
tags: [Image, SCIA, S9, OCVX2]
math: true
---

Lien de la [note Hackmd](https://hackmd.io/@lemasymasa/ryg-FKLIt)

On a un nuage de points:



On une infinite de directions possibles. On projette sur les axes:


:::info
On cherche un vecteur $\vec u$ tel que l'erreur de projection des $\{x_i\}$ sur l'espace engendre par notre vecteur $\text{span}(u)$ soit minimale.
:::

En formulation mathematiques:

$$
\text{proj}(x_i,\text{span}(u))=P_u(x_i)=\langle x_i,u\rangle = x_i^Tu
$$

:::warning
En l'etat: une infinite de solutions (si $u$ solutions, $ku$ solutions avec $k\in\mathbb R^{\*}$)
:::

On impose $\Vert u\Vert=1$

$$
P_u(x_i)=\langle x_i,u\rangle=x_i^Tu\to E(x_i,\underbrace{P_u(x_i)}_{y_i}) = \Vert x_i-y_i\Vert^{(2)}
$$

:::success
On cherche donc:

$$
\text{arg}\min_{u,\Vert u\Vert=1}\sum_{i=1}^n E(x_i,P_u(x_i))
$$

:::

D'apres Pythagore:

$$
\Vert x_i\Vert^2=\Vert y_i\Vert^2+\Vert x_i-y_i\Vert\\
\Vert x_i-y_i\Vert^2=\Vert x_i\Vert^2-\Vert y_i\Vert^2
$$

On peut donc reecrire:

$$
\begin{aligned}
\sum_{i=1}^nE(x_i,P_u(x_i))&=\sum_{i=1}^n\Vert x_i-y_i\Vert^2\\
&=\underbrace{\sum_{i=1}^n\Vert x_i\Vert^2}_{\text{constante}} - \sum_{i=1}^n\Vert y_i\Vert^2
\end{aligned}
$$

Donc:

$$
\begin{aligned}
\text{arg}\min_{u,\Vert u\Vert=1}&=\text{arg}\min_{u,\Vert u\Vert=1}-\sum_{i=1}^n\Vert y\Vert^2\\
&=\text{arg}\max_{u,\Vert u\Vert=1}\sum_{i=1}^n\Vert y_i\Vert^2\\
&=\text{arg}\max_{u,\Vert u\Vert=1}\underbrace{\frac{1}{n}\sum_{i=1}^n\Vert y\Vert^2}\\
&\Vert y_i\Vert^2=y_i^Ty_i\underbrace{\frac{1}{n}\sum_{i=1}^ny_i^Ty_i}_{\text{var}(P_u(X))}
\end{aligned}
$$

On est en train de chercher:

$$
\begin{aligned}
\text{arg}\min_{u,\Vert u\Vert=1}-\sum_{i=1}^n\Vert y_i\Vert^2&= -\frac{1}{n}\sum_{i=1}^ny_i^Ty_i\\
&= -\frac{1}{n}\sum_{i=1}^n(x_i^Tu)^T(x_i^Tu)\\
&= -\frac{1}{n}\sum_{i=1}^nu^Tx_ix_i^Tu\\
&= -u^T(\underbrace{\frac{1}{n}\sum_{i=1}^nx_ix_i^T}_{\Sigma\text{ matrice de covariance} \\ \text{de } X=\{x_i\}^n_{i=1}\text{ centre}})u
\end{aligned}
$$

:::danger
On cherche: $$\boxed{\text{arg}\min_{u\in\mathbb R^p \\ \Vert u\Vert =1}-u^T\underbrace{\Sigma}_{\text{matrice de} \\ \text{covariance}}u}$$

:::

$$
\text{arg}\max_{\Vert u\Vert=1}u^T\Sigma u = \text{arg}\max\overbrace{\frac{u^T\Sigma u}{u^Tu}}^{\text{Quotien de Rayleigh}}
$$

On va reecrire:

$$
\text{arg}\min_{u\in\mathbb R^p}-u^T\Sigma u\\
\begin{aligned}
\Vert u\Vert =1\Leftrightarrow &\Vert u\Vert^2=1\\
&\begin{cases}
u^Tu=1 &f(u)-u^T\Sigma u\\
u^Tu-1=0&g(u)=u^Tu-1
\end{cases}\biggr\}\text{arg}\min_{g(u)=0} f(u)
\end{aligned}
$$

Le lagrangien de ce probleme est $\mathscr L(u\lambda)=f(u)+\lambda g(u)-u^T\Sigma u+\lambda(u^Tu-1)$
- Stationnarite de $\mathscr L:\nabla_u\mathscr L(u,\lambda)=0=\nabla_u(-u^T\Sigma u)+\lambda\nabla_u(u^Tu-1)$

:::info
**Rappel**: $f(x)=x^TAx$
:::

On calcule la differentielle $f(x+h)=f(x)+df_x(h)+O(h)$

$$
\begin{aligned}
f(x+h)=(x+h)^TA(x+h)=\underbrace{x^TAx}_{f(x)}+x^T\underbrace{AH+h^T}&Ax+\underbrace{h^TAh}_{O(h)}\\
x^TAh+(\underbrace{h^TAx})^T&\\
\underbrace{x^TA^Th}&\\
x^T(A+A^T)h&\to df_x(h)=x^T(A+A^T)h\\
(=2x^TAh\text{ si } &A \text{ symetrique } A=A^T)
\end{aligned}\\
$$

$$
df_x(h)=\langle\nabla_xf,h\rangle=\nabla_xf^Th\to\nabla_xf=(A+A^T)x=2Ax\\
\begin{aligned}
\nabla_u(-u^T\Sigma u)=-\nabla_u(u^T\Sigma u)=-2\Sigma u\\
\nabla_u(u^Tu)=\nabla_u(u^TI_du)=2u
\end{aligned}\biggr\}-2\Sigma u+2du=0
$$

:::danger
$$
\color{red}{\boxed{\Sigma u=\lambda\mu}}
$$

$u$ est un vecteur propre de $\Sigma$
$\lambda$ est sa vlaeur propre
:::

On se souvient qu'on cehrche $u$, $\Vert u\Vert=1$ qui maximise:

$$
\begin{aligned}
\underbrace{\frac{1}{n}\sum_{i=1}^n\Vert y_i\Vert^2}_{\text{var}(P_u(x))}&= \frac{1}{n}\sum_{i=1}^ny_i^Ty_i\\
&=\frac{1}{n}\sum_{i=1}^n(x_i^Tu)(x_i^Tu)\\
&=\frac{1}{n}\sum_{i=1}^nu^Tx_ix_i^Tu\\
&=u^T(\frac{1}{n}\sum_{i=1}^nx_ix_i^T)u\\
&=u^T\underbrace{\Sigma u}_{\lambda u}\\
&=\lambda \underbrace{u^Tu}_{\Vert u\Vert^2 =1}\\
&=\lambda
\end{aligned}
$$