Eclats de vers : Matemat 10 : Optimisation - 6

Index des Grimoires

Retour à l’accueil

Table des matières

\( \newcommand{\parentheses}[1]{\left(#1\right)} \newcommand{\crochets}[1]{\left[#1\right]} \newcommand{\accolades}[1]{\left\{#1\right\}} \newcommand{\ensemble}[1]{\left\{#1\right\}} \newcommand{\identite}{\mathrm{Id}} \newcommand{\indicatrice}{\boldsymbol{\delta}} \newcommand{\dirac}{\delta} \newcommand{\moinsun}{{-1}} \newcommand{\inverse}{\ddagger} \newcommand{\pinverse}{\dagger} \newcommand{\topologie}{\mathfrak{T}} \newcommand{\ferme}{\mathfrak{F}} \newcommand{\img}{\mathbf{i}} \newcommand{\binome}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\canonique}{\mathfrak{c}} \newcommand{\tenseuridentite}{\boldsymbol{\mathcal{I}}} \newcommand{\permutation}{\boldsymbol{\epsilon}} \newcommand{\matriceZero}{\mathfrak{0}} \newcommand{\matriceUn}{\mathfrak{1}} \newcommand{\christoffel}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\lagrangien}{\mathfrak{L}} \newcommand{\sousens}{\mathfrak{P}} \newcommand{\partition}{\mathrm{Partition}} \newcommand{\tribu}{\mathrm{Tribu}} \newcommand{\topologies}{\mathrm{Topo}} \newcommand{\setB}{\mathbb{B}} \newcommand{\setN}{\mathbb{N}} \newcommand{\setZ}{\mathbb{Z}} \newcommand{\setQ}{\mathbb{Q}} \newcommand{\setR}{\mathbb{R}} \newcommand{\setC}{\mathbb{C}} \newcommand{\corps}{\mathbb{K}} \newcommand{\boule}{\mathfrak{B}} \newcommand{\intervalleouvert}[2]{\relax \ ] #1 , #2 [ \ \relax} \newcommand{\intervallesemiouvertgauche}[2]{\relax \ ] #1 , #2 ]} \newcommand{\intervallesemiouvertdroite}[2]{[ #1 , #2 [ \ \relax} \newcommand{\fonction}{\mathbb{F}} \newcommand{\bijection}{\mathrm{Bij}} \newcommand{\polynome}{\mathrm{Poly}} \newcommand{\lineaire}{\mathrm{Lin}} \newcommand{\continue}{\mathrm{Cont}} \newcommand{\homeomorphisme}{\mathrm{Hom}} \newcommand{\etagee}{\mathrm{Etagee}} \newcommand{\lebesgue}{\mathrm{Leb}} \newcommand{\lipschitz}{\mathrm{Lip}} \newcommand{\suitek}{\mathrm{Suite}} \newcommand{\matrice}{\mathbb{M}} \newcommand{\krylov}{\mathrm{Krylov}} \newcommand{\tenseur}{\mathbb{T}} \newcommand{\essentiel}{\mathfrak{E}} \newcommand{\relation}{\mathrm{Rel}} \newcommand{\strictinferieur}{\ < \ } \newcommand{\strictsuperieur}{\ > \ } \newcommand{\ensinferieur}{\eqslantless} \newcommand{\enssuperieur}{\eqslantgtr} \newcommand{\esssuperieur}{\gtrsim} \newcommand{\essinferieur}{\lesssim} \newcommand{\essegal}{\eqsim} \newcommand{\union}{\ \cup \ } \newcommand{\intersection}{\ \cap \ } \newcommand{\opera}{\divideontimes} \newcommand{\autreaddition}{\boxplus} \newcommand{\autremultiplication}{\circledast} \newcommand{\commutateur}[2]{\left[ #1 , #2 \right]} \newcommand{\convolution}{\circledcirc} \newcommand{\correlation}{\ \natural \ } \newcommand{\diventiere}{\div} \newcommand{\modulo}{\bmod} \newcommand{\pgcd}{pgcd} \newcommand{\ppcm}{ppcm} \newcommand{\produitscalaire}[2]{\left\langle #1 \left|\right\relax #2 \right\rangle} \newcommand{\scalaire}[2]{\left\langle #1 \| #2 \right\rangle} \newcommand{\braket}[3]{\left\langle #1 \right| #2 \left| #3 \right\rangle} \newcommand{\orthogonal}{\bot} \newcommand{\forme}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\biforme}[3]{\left\langle #1 , #2 , #3 \right\rangle} \newcommand{\contraction}[3]{\left\langle #1 \odot #3 \right\rangle_{#2}} \newcommand{\dblecont}[5]{\left\langle #1 \right| #3 \left| #5 \right\rangle_{#2,#4}} \newcommand{\major}{major} \newcommand{\minor}{minor} \newcommand{\maxim}{maxim} \newcommand{\minim}{minim} \newcommand{\argument}{arg} \newcommand{\argmin}{arg\ min} \newcommand{\argmax}{arg\ max} \newcommand{\supessentiel}{ess\ sup} \newcommand{\infessentiel}{ess\ inf} \newcommand{\dual}{\star} \newcommand{\distance}{\mathfrak{dist}} \newcommand{\norme}[1]{\left\| #1 \right\|} \newcommand{\normetrois}[1]{\left|\left\| #1 \right\|\right|} \newcommand{\adh}{adh} \newcommand{\interieur}{int} \newcommand{\frontiere}{\partial} \newcommand{\image}{im} \newcommand{\domaine}{dom} \newcommand{\noyau}{ker} \newcommand{\support}{supp} \newcommand{\signe}{sign} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\unsur}[1]{\frac{1}{#1}} \newcommand{\arrondisup}[1]{\lceil #1 \rceil} \newcommand{\arrondiinf}[1]{\lfloor #1 \rfloor} \newcommand{\conjugue}{conj} \newcommand{\conjaccent}[1]{\overline{#1}} \newcommand{\division}{division} \newcommand{\difference}{\boldsymbol{\Delta}} \newcommand{\differentielle}[2]{\mathfrak{D}^{#1}_{#2}} \newcommand{\OD}[2]{\frac{d #1}{d #2}} \newcommand{\OOD}[2]{\frac{d^2 #1}{d #2^2}} \newcommand{\NOD}[3]{\frac{d^{#3} #1}{d #2^{#3}}} \newcommand{\deriveepartielle}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dblederiveepartielle}[2]{\frac{\partial^2 #1}{\partial #2 \partial #2}} \newcommand{\dfdxdy}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}} \newcommand{\dfdxdx}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\gradient}{\mathbf{\nabla}} \newcommand{\combilin}[1]{\mathrm{span}\{ #1 \}} \newcommand{\trace}{tr} \newcommand{\proba}{\mathbb{P}} \newcommand{\probaof}[1]{\mathbb{P}\left[#1\right]} \newcommand{\esperof}[1]{\mathbb{E}\left[#1\right]} \newcommand{\cov}[2]{\mathrm{cov} \left( #1 , #2 \right) } \newcommand{\var}[1]{\mathrm{var} \left( #1 \right) } \newcommand{\rand}{\mathrm{rand}} \newcommand{\variation}[1]{\left\langle #1 \right\rangle} \newcommand{\composante}{comp} \newcommand{\bloc}{bloc} \newcommand{\ligne}{ligne} \newcommand{\colonne}{colonne} \newcommand{\diagonale}{diag} \newcommand{\matelementaire}{\mathrm{Elem}} \newcommand{\matpermutation}{permut} \newcommand{\matunitaire}{\mathrm{Unitaire}} \newcommand{\gaussjordan}{\mathrm{GaussJordan}} \newcommand{\householder}{\mathrm{Householder}} \newcommand{\rang}{rang} \newcommand{\schur}{\mathrm{Schur}} \newcommand{\singuliere}{\mathrm{DVS}} \newcommand{\convexe}{\mathrm{Convexe}} \newcommand{\petito}[1]{o\left(#1\right)} \newcommand{\grando}[1]{O\left(#1\right)} \)

1 Valeurs singulières

1.1 Décomposition en valeurs singulières

Soit les espaces vectoriels \(E\) et \(F\) et une application linéaire \(A : E \mapsto F\) admettant un dual \(A^\dual : F \mapsto E\). Les applications \(A^\dual \circ A\) et \(A \circ A^\dual\) étant auto-adjointes, il y a fort à parier que leurs valeurs et vecteurs propres possèdent d'importantes propriétés.

Supposons que \(A^\dual \circ A\) admette les valeurs propres \(\lambda_i \in \corps\) triées par ordre décroissant ($λ1 ≥ λ2 ≥ λ3 ≥ …$) et correspondant aux vecteurs propres \(v_i \in E\) formant une suite orthonormée. On a donc :

\[A^\dual \circ A(v_i) = \lambda_i \cdot v_i\]

On voit que les vecteurs \(z_i = A(v_i) \in F\) possèdent la propriété :

\[A^\dual(z_i) = A^\dual \circ A(v_i) = \lambda_i \cdot v_i\]

et :

\[A \circ A^\dual(z_i) = A(\lambda_i \cdot v_i) = \lambda_i \cdot A(v_i) = \lambda_i \cdot z_i\]

Les \(z_i\) sont donc vecteurs propres de \(A \circ A^\dual\) de valeurs propres \(\lambda_i\) identiques à celles de \(A^\dual \circ A\). On a l'orthogonalité :

\( \scalaire{z_i}{z_j} = \scalaire{A(v_i)}{A(v_j)} = \scalaire{v_i}{A^\dual \circ A(v_j)} = \lambda_j \cdot \scalaire{v_i}{v_j} = \lambda_i \cdot \indicatrice_{ij} \)

On voit aussi que les valeurs propres sont positives :

\[\lambda_i = \scalaire{A(v_i)}{A(v_i)} \ge 0\]

Comme elles sont également triées par ordre décroissant, on a \(\lambda_1 \ge \lambda_2 \ge ... \ge \lambda_r \strictsuperieur 0\) pour un certain \(r \in \setN\), et \(\lambda_n = 0\) pour tout \(n \strictsuperieur r\). Dans la suite, nous nous restreignons aux valeurs propres non nulles. On peut alors poser :

\[\sigma_i = \sqrt{\lambda_i} \strictsuperieur 0\]

afin de normaliser les \(z_i\) :

\[u_i = \unsur{\sigma_i} \cdot z_i = \unsur{\sigma_i} \cdot A(v_i)\]

On a alors :

\[\scalaire{u_i}{u_j} = \scalaire{v_i}{v_j} = \indicatrice_{ij}\]

ainsi que :

\[A^\dual(u_i) = \frac{\lambda_i}{\sigma_i} \cdot v_i = \sigma_i \cdot v_i\]

Nous disposons donc des relations primales et duales :

\( A(v_i) = \sigma_i \cdot u_i \\ A^\dual(u_i) = \sigma_i \cdot v_i \)

Pour tout \(x \in \combilin{v_1,...,v_r}\), on a :

\[x = \sum_{i = 1}^r \scalaire{v_i}{x} \cdot v_i\]

et :

\begin{align} A(x) &= \sum_{i = 1}^r \scalaire{v_i}{x} \cdot A(v_i) \\ &= \sum_{i = 1}^r \scalaire{v_i}{x} \cdot \sigma_i \cdot u_i \end{align}

1.2 Représentation tensorielle

On conclut de ce qui précède que \(A\) peut être représentée sur \(\combilin{v_1,...,v_n}\) par le tenseur associé :

\[\mathcal{A} = \sum_{i = 1}^r \sigma_i \cdot u_i \otimes v_i\]

de sorte que :

\[A(x) = \mathcal{A} \cdot x = \contraction{ \mathcal{A} }{1}{x} = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot \scalaire{v_i}{x}\]

On appelle une telle représentation une décomposition en valeurs singulières.

1.3 Dualité

Le tenseur dual est donc :

\[\mathcal{A}^\dual = \sum_{i = 1}^r \sigma_i \cdot v_i \otimes u_i\]

1.3.1 Propriétés

On retrouve sans surprise les représentation de :

\begin{align} \mathcal{A}^\dual \cdot \mathcal{A} &= \sum_{i,j = 1}^r \sigma_i \cdot \sigma_j \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes v_j \\ &= \sum_{i = 1}^r \sigma_i^2 \cdot v_i \otimes v_i \end{align}

et de :

\begin{align} \mathcal{A} \cdot \mathcal{A}^\dual &= \sum_{i,j = 1}^r \sigma_i \cdot \sigma_j \cdot \scalaire{v_i}{v_j} \cdot u_i \otimes u_j \\ &= \sum_{i = 1}^r \sigma_i^2 \cdot u_i \otimes u_i \end{align}

en fonction de leurs valeurs et vecteurs propres.

1.4 Inverse

Supposons que \((v_1,...,v_r)\) forme une base de \(E\) et que \((u_1,...u_r)\) forme une base de \(F\). Soit \(x \in E\) et \(y \in F\) tels que \(y = A(x) = \mathcal{A} \cdot x\). On a :

\[y = \sum_{i = 1}^r \scalaire{u_i}{y} \cdot u_i = \mathcal{A} \cdot x = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot \scalaire{v_i}{x}\]

On en déduit en comparant que \(\sigma_i \cdot \scalaire{v_i}{x} = \scalaire{u_i}{y}\), ce qui nous donne les produits scalaires correspondant aux coordonnées de \(x\) par rapport aux \(v_i\) :

\[\scalaire{v_i}{x} = \unsur{\sigma_i} \cdot \scalaire{u_i}{y}\]

On a donc :

\[x = \sum_i \scalaire{v_i}{x} \cdot v_i = \sum_i \unsur{\sigma_i} \cdot \scalaire{u_i}{y} \cdot v_i\]

Donc, si on pose :

\[\mathcal{A}^{-1} = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i\]

on a :

\[x = \mathcal{A}^{-1} \cdot y\]

1.5 Pseudo-inverse

Nous ne supposons à présent plus que les suites de vecteurs \((u_1,...,u_r)\) et \((v_1,...,v_r)\) forment des bases de \(E\) et \(F\), mais nous définissons malgré tout par analogie le tenseur pseudo-inverse de \(A\) par :

\[\mathcal{A}^\pinverse = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i\]

Le pseudo-inverse \(A^\pinverse\) de l'application linéaire correspondante \(A\) est donc défini par :

\[A^\pinverse(y) = \mathcal{A}^\pinverse \cdot y = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot \scalaire{u_i}{y}\]

1.5.1 Tenseurs de projections

On voit que :

\begin{align} \mathcal{A}^\pinverse \cdot \mathcal{A} &= \sum_{i,j = 1}^r \unsur{\sigma_i} \cdot \sigma_j \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes v_j \\ &= \sum_{i = 1}^r v_i \otimes v_i \end{align}

correspond au tenseur de projection sur \(\combilin{v_1,...,v_r}\). De même :

\begin{align} \mathcal{A} \cdot \mathcal{A}^\pinverse &= \sum_{i,j = 1}^r \sigma_i \cdot \unsur{\sigma_j} \cdot \scalaire{v_i}{v_j} \cdot u_i \otimes u_j \\ &= \sum_{i = 1}^r u_i \otimes u_i \end{align}

correspond au tenseur de projection sur \(\combilin{u_1,...,u_r}\).

1.5.2 Dualité

On a clairement :

\( (\mathcal{A} \cdot \mathcal{A}^\pinverse)^\dual = \mathcal{A} \cdot \mathcal{A}^\pinverse \\ (\mathcal{A}^\pinverse \cdot \mathcal{A})^\dual = \mathcal{A}^\pinverse \cdot \mathcal{A} \)

1.5.3 Produits

On déduit des résultats ci-dessus que :

\begin{align} \mathcal{A} \cdot \mathcal{A}^\pinverse \cdot \mathcal{A} &= \sum_{i,j = 1}^r \sigma_i \cdot \scalaire{v_i}{v_j} \cdot u_i \otimes v_j \\ &= \sum_{i = 1}^r \sigma_i \cdot u_i \otimes v_i \\ &= \mathcal{A} \end{align}

et :

\begin{align} \mathcal{A}^\pinverse \cdot \mathcal{A} \cdot \mathcal{A}^\pinverse &= \sum_{i,j = 1}^r \unsur{\sigma_i} \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes u_j \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i \\ &= \mathcal{A}^\pinverse \end{align}

1.5.4 Orthogonalité

Soit le tenseur identité \(\tenseuridentite\). On déduit de ce qui précède les propriétés d'orthogonalité :

\( \mathcal{A} \cdot (\tenseuridentite - \mathcal{A}^\pinverse \cdot \mathcal{A}) = 0 \\ \mathcal{A}^\pinverse \cdot (\tenseuridentite - \mathcal{A} \cdot \mathcal{A}^\pinverse) = 0 \)

1.6 Représentation matricielle

Soit une matrice \(A \in \matrice(\corps,m,n)\) et \(p = \min \{ m , n \}\). L'algorithme de décomposition en valeurs singulières est très simple. On évalue :

\( (\Lambda_1, U) = \schur(A \cdot A^\dual) \\ (\Lambda_2, V) = \schur(A^\dual \cdot A) \)

On a alors \(U,\Lambda_1 \in \matrice(\corps,n,n)\) et \(V,\Lambda_2 \in \matrice(\corps,m,m)\). Comme les matrices \(A^\dual \cdot A\) et \(A \cdot A^\dual\) sont hermitiennes et que leurs valeurs propres sont identiques, les matrices « triangulaires » obtenues sont en fait diagonales et :

\( \Lambda_1 = \diagonale_n(\lambda_1,...\lambda_p) \\ \Lambda_2 = \diagonale_m(\lambda_1,...\lambda_p) \)

On pose alors \(\sigma_i = \sqrt{\lambda_i}\) pour \(i \in \{1,2,...,p\}\) et on a \(\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_r \strictsuperieur 0\) et \(\sigma_{r + 1} = ... = \sigma_p = 0\). Les colonnes de \(U\) et de \(V\) sont les vecteurs propres correspondant :

\( u_i = \colonne_i U \\ v_i = \colonne_i V \)

On a également \(U^{-1} = U^\dual\) et \(V^{-1} = V^\dual\). La décomposition en valeurs singulières de \(A\) s'écrit :

\[A = \sum_{i = 1}^r \sigma_i \cdot u_i \otimes v_i = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot v_i^\dual\]

Si nous posons :

\[S = \diagonale_{m,n}(\sigma_1,...,\sigma_r)\]

on peut réécrire la décomposition de \(A\) sous la forme :

\[A = U \cdot S \cdot V^\dual\]

On note alors :

\[(U,S,V) = \singuliere(A)\]

1.7 Pseudo-inverse

Le pseudo-inverse est donné par :

\[A^\pinverse = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot u_i^\dual\]

On a donc :

\[S^\pinverse = \diagonale_{n,m}\left(\unsur{\sigma_1},...,\unsur{\sigma_r}\right)\]

et :

\[A^\pinverse = V \cdot S^\pinverse \cdot U^\dual\]

1.8 Systèmes linéaires

1.8.1 Moindres carrés

Soit la matrice \(A \in \matrice(\corps,m,n)\), le vecteur matriciel \(b \in \corps^m\) et l'erreur produite par \(x \in \corps^n\) :

\[e(x) = b - A \cdot x\]

On dit aussi que \(e(x)\) est le résidu du système en \(x\). Nous allons tenter de minimiser :

\[\mathcal{E}(x) = e(x)^\dual \cdot e(x) = \norme{e(x)}^2\]

en utilisant la décomposition en valeurs singulières \(A = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot v_i^\dual\). Comme \((v_1,...,v_n)\), suite orthonormée et linéairement indépendante, forme une base de \(\corps^n\), on peut exprimer \(x\) en fonction de ses coordonnées dans cette base :

\[x = \sum_{i = 1}^n x_i \cdot v_i = \sum_{i = 1}^n \scalaire{v_i}{x} \cdot v_i\]

Comme \((u_1,...,u_m)\), suite orthonormée et linéairement indépendante, forme une base de \(\corps^m\), on peut exprimer \(b\) comme :

\[b = \sum_{i = 1}^m \scalaire{u_i}{b} \cdot u_i\]

On a également :

\[A \cdot x = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot \scalaire{v_i}{x} = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot x_i\]

On en conclut que l'erreur s'écrit :

\[e(x) = \sum_{i = 1}^r (\scalaire{u_i}{b} - \sigma_i \cdot x_i) \cdot u_i + \sum_{i = r + 1}^m \scalaire{u_i}{b} \cdot u_i\]

Posons :

\( ei(x) =

\begin{cases} \scalaire{u_i}{b} - \sigma_i \cdot x_i & \text{ si } i \in \{1,...,r\} \\ \scalaire{u_i}{b} & \text{ si } i \in \{r + 1, ...,m\} \\ \end{cases}

\)

On a alors \(e(x) = \sum_{i = 1}^m e_i(x) \cdot u_i\) et :

\[\mathcal{E}(x) = \norme{e(x)}^2 = \sum_{i,j = 1}^m \conjaccent{e}_i(x) \cdot e_j(x) \cdot u_i^\dual \cdot u_j = \sum_{i = 1}^m \abs{e_i(x)}^2\]

On a donc :

\[\mathcal{E}(x) = \sum_{i = 1}^r \abs{\scalaire{u_i}{b} - \sigma_i \cdot x_i}^2 + \sum_{i = r + 1}^m \abs{\scalaire{u_i}{b}}^2\]

Dans le cas où l'on travaille avec des réels, l'annulation de la dérivée par rapport aux \(x_i\) nous donne :

\[2 (\scalaire{u_i}{b} - \sigma_i \cdot x_i) = 0\]

lorsque \(i \in \{1,...,r\}\). Nous n'avons par contre aucune contrainte sur \(x_{r + 1},...,x_n\). Un choix satisfaisant les conditions ci-dessus est donc :

\( xi =

\begin{cases} \scalaire{u_i}{b} / \sigma_i & \text{ si } i \in \{1,...,r\} \\ 0 & \text{ si } i \in \{r + 1, ...,n\} \\ \end{cases}

\)

Notre \(x\) potentiellement optimal s'écrit donc :

\[x = \sum_{i = 1}^r \unsur{\sigma_i} \cdot \scalaire{u_i}{b} \cdot v_i\]

La somme ressemble à une expression faisant intervenir le pseudo-inverse. En effet, on a :

\[A^\pinverse \cdot b = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot \scalaire{u_i}{b} = x\]

Considérons à présent le cas général complexe. On voit que pour le choix \(x = A^\pinverse \cdot b\) :

\[\mathcal{E}(x) = \sum_{i = r + 1}^m \abs{\scalaire{u_i}{b}}^2\]

On en déduit la borne inférieure de l'erreur :

\[\mathcal{E}(z) = \sum_{i = 1}^r \abs{\scalaire{u_i}{b} - \sigma_i \cdot \scalaire{v_i}{z}}^2 + \sum_{i = r + 1}^m \abs{\scalaire{u_i}{b}}^2 \ge \sum_{i = r + 1}^n \abs{\scalaire{u_i}{b}}^2 = \mathcal{E}(x)\]

pour tout \(z \in \setC^n\). Le choix \(x = A^\pinverse \cdot b\) minimise bien la norme de l'erreur sur \(\setC^n\) :

\[x = A^\pinverse \cdot b \in \arg\min_{z \in \setC^n} \mathcal{E}(z)\]

Les \(x_{r + 1},...,x_n\) étant des complexes arbitraires, nous allons montrer que l'ensemble optimal s'écrit :

\[\arg\min_{z \in \setC^n} \mathcal{E}(z) = \Gamma = \left\{ \left(A^\pinverse \cdot b + \sum_{i = r + 1}^n x_i \cdot v_i \right) : \ x_{r + 1},...,x_n \in \setC \right\}\]

En effet, on a \(\mathcal{E}(z) = \mathcal{E}(x)\) pour tout \(z \in \Gamma\). On voit aussi que tout choix de \(z \notin \Gamma\) provoque :

\[\sum_{i = 1}^r \abs{\scalaire{u_i}{b} - \sigma_i \cdot \scalaire{v_i}{z}}^2 \strictsuperieur 0\]

et donc \(\mathcal{E}(z) \strictsuperieur \mathcal{E}(x)\).

1.8.2 Projection

On peut réécrire \(\Gamma\) sous la forme :

\[\Gamma = \{ A^\pinverse \cdot b \} + \combilin{v_{r + 1},...,v_n}\]

Soit la matrice de projection :

\[P = \sum_{i = r + 1}^n v_i \otimes v_i\]

On sait que \(P \cdot z \in \combilin{v_{r + 1},...,v_n}\) pour tout \(z \in \setC^n\) et que \(P \cdot y = y\) pour tout \(y \in \combilin{v_{r + 1},...,v_n}\). On en conclut que tout \(x \in \Gamma\) peut s'écrire sous la forme :

\[x = A^\pinverse \cdot b + P \cdot z\]

pour un certain \(z \in \corps^n\). La matrice de projection \(P\) est également la complémentaire de la projection sur \(\combilin{v_1,...,v_r}\). Or, on a a vu que \(A^\pinverse \cdot A\) est précisément cette matrice de projection. On retrouve donc fort logiquement :

\[I - A^\pinverse \cdot A = \sum_{i = 1}^n v_i \otimes v_i - \sum_{i = 1}^r v_i \otimes v_i = \sum_{i = r + 1}^n v_i \otimes v_i = P\]

On a donc en définitive des vecteurs optimaux de la forme :

\[x = A^\pinverse \cdot b + (I - A^\pinverse \cdot A) \cdot z\]

1.8.3 Solutions

Soit l'espace des solutions :

\[S = \{ x \in \setC^n : A \cdot x = b \} = \{ x \in \setC^n : \mathcal{E}(x) = 0 \}\]

Si \(\scalaire{u_{r + 1}}{b} = ... = \scalaire{u_m}{b} = 0\), le minimum de l'erreur est nul et \(\mathcal{E}(x) = 0\) pour tout \(x \in \Gamma\). On en conclut que \(x \in S\), d'où \(\Gamma \subseteq S\). D'un autre coté, tout \(z \in S\) minimise \(\mathcal{E}(z) = 0\). On a donc également \(S \subseteq \Gamma\) et finalement \(\Gamma = S\).

Inversément, si \(S \ne \emptyset\), on conclut que \(\scalaire{u_{r + 1}}{b} = ... = \scalaire{u_m}{b} = 0\).

1.8.4 Norme contrainte

Supposons que \(S \ne \emptyset\). Soit \(x \in \Gamma = S\), que l'on écrit sous la forme :

\begin{align} x &= A^\pinverse \cdot b + \sum_{i = r + 1}^n x_i \cdot v_i \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot \scalaire{u_i}{b} + \sum_{i = r + 1}^n x_i \cdot v_i \\ \end{align}

Par orthonormalité des \(v_i\), on a :

\[\norme{x}^2 = x^\dual \cdot x = \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot \abs{\scalaire{u_i}{b}}^2 + \sum_{i = r + 1}^n \abs{x_i}^2\]

On voit que :

\[\norme{x}^2 \ge \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot \abs{\scalaire{u_i}{b}}^2 = \norme{A^\pinverse \cdot b}^2\]

On en conclut que le choix \(x = A^\pinverse \cdot b\) minimise la norme de \(x\) sur \(S\) :

\[A^\pinverse \cdot b \in \arg\min_{z \in S} \norme{z}^2\]

1.8.5 Lien avec les résultats précédents

  • On a montré précédemment en dérivant les expressions matricielles que le choix :

\[x = (A^\dual \cdot A)^{-1} \cdot A^\dual \cdot b\]

minimise également l'erreur \(\mathcal{E}\) sur \(\setR^n\) lorsque l'inverse de \(A^\dual \cdot A\) existe. Si tel est le cas, on a :

\[(A^\dual \cdot A)^{-1} = \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot v_i \otimes v_i\]

et :

\begin{align} (A^\dual \cdot A)^{-1} \cdot A^\dual &= \sum_{i,j = 1}^r \frac{\sigma_j}{\sigma_i^2} \cdot \scalaire{v_i}{v_j} \cdot v_i \otimes u_j \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i = A^\pinverse \end{align}
  • On a vu aussi en utilisant les multiplicateurs de lagrange que le choix :

\[x = A^\dual \cdot (A \cdot A^\dual)^{-1} \cdot b\]

minimise également la norme de \(x\) sur \(S\) lorsque l'inverse de \(A \cdot A^\dual\) existe. Si tel est le cas, on a :

\[(A \cdot A^\dual)^{-1} = \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot u_i \otimes u_i\]

et :

\begin{align} A^\dual \cdot (A \cdot A^\dual)^{-1} &= \sum_{i,j = 1}^r \frac{\sigma_i}{\sigma_j^2} \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes u_j \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i = A^\pinverse \end{align}

1.9 Image et noyau

Tout vecteur \(b = A \cdot x = \sum_{i = 1}^r \sigma_i \cdot \scalaire{v_i}{x} \cdot u_i\) est exprimé comme une combinaison linéaire des \((u_1,...,u_r)\). On en conclut que \(\image A \subseteq \combilin{u_1,...,u_r}\). Réciproquement, si \(b \in \combilin{u_1,...,u_r}\), on a \(\scalaire{u_{r + 1}}{b} = \scalaire{u_m}{b} = 0\) et l'espace des solutions \(\{ x \in \setC^n : A \cdot x = b\}\) n'est pas vide. On en conclut que \(\combilin{u_1,...,u_r} \subseteq \image A\). D'où finalement :

\[\image A = \combilin{u_1,...,u_r}\]

Tout vecteur \(z \in \combilin{v_{r + 1},...,v_n}\) vérifie \(\scalaire{v_1}{z} = ... = \scalaire{v_r}{z} = 0\). On en déduit que \(A \cdot z = \sum_{i = 1}^r \sigma_i \cdot 0 \cdot u_i = 0\) et que \(\combilin{v_{r + 1},...,v_n} \subseteq \noyau A\). Réciproquement, si \(z \in \noyau A\), on a \(\sum_{i = 1}^r \sigma_i \cdot \scalaire{v_i}{z} \cdot u_i = 0\) ce qui implique \(\scalaire{v_1}{z} = ... = \scalaire{v_r}{z} = 0\). On en conclut que \(\noyau A \subseteq \combilin{v_{r + 1},...,v_n}\). D'où finalement :

\[\noyau A = \combilin{v_{r + 1},...,v_n}\]

1.10 Normes

La décomposition en valeurs singulières permet d'évaluer facilement la norme usuelle des applications linéaires :

\[\norme{A}_\lineaire = \sup_{x \ne 0} \frac{\norme{A \cdot x}}{\norme{x}} = \max \{\sigma_1,...,\sigma_r\}\]

ainsi que la norme de Frobénius :

\[\norme{A}_F = \sqrt{A^\dual : A} = \sqrt{\sum_{i = 1}^r \sigma_i^2}\]

1.11 Fonctions de matrices

La décomposition en valeurs singulières permet d'étendre la définition d'une fonction \(f : \setR \mapsto \setR\). Soit la décomposition de \(A\) :

\[A = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot v_i^\dual\]

On définit alors :

\[f(A) = \sum_{i = 1}^r f(\sigma_i) \cdot u_i \cdot v_i^\dual\]

Auteur: chimay

Created: 2019-10-01 mar 12:32

Validate