Lien de la note Hackmd

On a un nuage de points:

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

On cherche un vecteur

$\overrightarrow{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)=⟨x_i,u⟩=x_i^{T}u$$

En l'etat: une infinite de solutions (si

$u$ solutions,

$ku$ solutions avec

$k\in {\mathbb{R}}^{\text{*}}$)

On impose

$\Vert u\Vert =1$

$$P_u(x_i)=⟨x_i,u⟩=x_i^{T}u\to E(x_i,\underset{y_i}{\underbrace{P_u(x_i)}})=\Vert x_i-y_i{\Vert }^{(2)}$$

On cherche donc:

$$\text{arg}\underset{u,\Vert u\Vert =1}{min}\sum _{i=1}^{n}E(x_i,P_u(x_i))$$

D'apres Pythagore:

$$\begin{gathered} \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 \end{gathered}$$

On peut donc reecrire:

$$\begin{array}{rl}\sum _{i=1}^{n}E(x_i,P_u(x_i))& =\sum _{i=1}^n\Vert x_i-y_i{\Vert }^2\\ & =\underset{\text{constante}}{\underbrace{\sum _{i=1}^n\Vert x_i{\Vert }^2}}-\sum _{i=1}^n\Vert y_i{\Vert }^2\end{array}$$

Donc:

$$\begin{array}{rl}\text{arg}\underset{u,\Vert u\Vert =1}{min}& =\text{arg}\underset{u,\Vert u\Vert =1}{min}-\sum _{i=1}^n\Vert y{\Vert }^2\\ & =\text{arg}\underset{u,\Vert u\Vert =1}{max}\sum _{i=1}^n\Vert y_i{\Vert }^2\\ & =\text{arg}\underset{u,\Vert u\Vert =1}{max}\underbrace{\frac{1}{n}\sum _{i=1}^n\Vert y{\Vert }^2}\\ & \Vert y_i{\Vert }^2=y_i^T{y}_i\underset{\text{var}(P_u(X))}{\underbrace{\frac{1}{n}\sum _{i=1}^n{y}_i^T{y}_i}}\end{array}$$

On est en train de chercher:

$$\begin{gathered} \begin{array}{rl}\text{arg}\underset{u,\Vert u\Vert =1}{min}-\sum _{i=1}^n\Vert y_i{\Vert }^2& =-\frac{1}{n}\sum _{i=1}^n{y}_i^T{y}_i\\ & =-\frac{1}{n}\sum _{i=1}^n(x_i^{T}u{)}^T(x_i^{T}u)\\ & =-\frac{1}{n}\sum _{i=1}^n{u}^T{x}_i{x}_i^{T}u\\ & =-u^T(\underset{\mathrm{\Sigma }\text{ matrice de covariance} \\ \text{de }X=\{x_i{\}}_{i=1}^n\text{ centre}}{\underbrace{\frac{1}{n}\sum _{i=1}^n{x}_i{x}_i^T}})u\end{array} \end{gathered}$$

On cherche:

$$\begin{gathered} \boxed{{\displaystyle \text{arg}\underset{u\in {\mathbb{R}}^p \\ \Vert u\Vert =1}{min}-u^T\underset{\text{matrice de} \\ \text{covariance}}{\underbrace{\mathrm{\Sigma }}}u}} \end{gathered}$$

$$\text{arg}\underset{\Vert u\Vert =1}{max}{u}^T\mathrm{\Sigma }u=\text{arg}max\stackrel{\text{Quotien de Rayleigh}}{\overbrace{\frac{u^T\mathrm{\Sigma }u}{u^{T}u}}}$$

On va reecrire:

$$\begin{gathered} \text{arg}\underset{u\in {\mathbb{R}}^p}{min}-u^T\mathrm{\Sigma }u \\ \begin{array}{rl}\Vert u\Vert =1\iff & \Vert u{\Vert }^2=1\\ & \{\begin{array}{ll}{u}^{T}u=1& f(u)-u^T\mathrm{\Sigma }u\\ u^{T}u-1=0& g(u)=u^{T}u-1\end{array}\}\text{arg}\underset{g(u)=0}{min}f(u)\end{array} \end{gathered}$$

Le lagrangien de ce probleme est

$\mathcal{L}(u\lambda )=f(u)+\lambda g(u)-u^T\mathrm{\Sigma }u+\lambda (u^{T}u-1)$

• Stationnarite de
  $\mathcal{L}:{\mathrm{\nabla }}_u\mathcal{L}(u,\lambda )=0={\mathrm{\nabla }}_u(-u^T\mathrm{\Sigma }u)+\lambda {\mathrm{\nabla }}_u(u^{T}u-1)$

Rappel:

$f(x)=x^{T}Ax$

On calcule la differentielle

$f(x+h)=f(x)+d{f}_x(h)+O(h)$

$$\begin{array}{rl}f(x+h)=(x+h{)}^{T}A(x+h)=\underset{f(x)}{\underbrace{x^{T}Ax}}+x^T\underbrace{AH+h^T}& Ax+\underset{O(h)}{\underbrace{h^{T}Ah}}\\ x^{T}Ah+(\underbrace{h^{T}Ax}{)}^T& \\ \underbrace{x^T{A}^{T}h}& \\ x^T(A+A^T)h& \to d{f}_x(h)=x^T(A+A^T)h\\ (=2x^{T}Ah\text{ si }& A\text{ symetrique }A=A^T)\end{array}$$

$$\begin{gathered} d{f}_x(h)=⟨{\mathrm{\nabla }}_{x}f,h⟩={\mathrm{\nabla }}_x{f}^{T}h\to {\mathrm{\nabla }}_{x}f=(A+A^T)x=2Ax \\ \begin{array}{r}{\mathrm{\nabla }}_u(-u^T\mathrm{\Sigma }u)=-{\mathrm{\nabla }}_u(u^T\mathrm{\Sigma }u)=-2\mathrm{\Sigma }u\\ {\mathrm{\nabla }}_u(u^{T}u)={\mathrm{\nabla }}_u(u^T{I}_{d}u)=2u\end{array}\}-2\mathrm{\Sigma }u+2du=0 \end{gathered}$$

$$\text{color}red\boxed{{\displaystyle \mathrm{\Sigma }u=\lambda \mu }}$$

$u$ est un vecteur propre de

$\mathrm{\Sigma }$

$\lambda$ est sa vlaeur propre

On se souvient qu'on cehrche

$u$,

$\Vert u\Vert =1$ qui maximise:

$$\begin{array}{rl}\underset{\text{var}(P_u(x))}{\underbrace{\frac{1}{n}\sum _{i=1}^n\Vert y_i{\Vert }^2}}& =\frac{1}{n}\sum _{i=1}^n{y}_i^T{y}_i\\ & =\frac{1}{n}\sum _{i=1}^n(x_i^{T}u)(x_i^{T}u)\\ & =\frac{1}{n}\sum _{i=1}^n{u}^T{x}_i{x}_i^{T}u\\ & =u^T(\frac{1}{n}\sum _{i=1}^n{x}_i{x}_i^T)u\\ & =u^T\underset{\lambda u}{\underbrace{\mathrm{\Sigma }u}}\\ & =\lambda \underset{\Vert u{\Vert }^2=1}{\underbrace{u^{T}u}}\\ & =\lambda \end{array}$$