Rappels d'algèbre linéaire

Vecteurs et matrices

Vecteurs

Un vecteur $\mathbf{x}\in {\mathbb{R}}^n$ est un tableau ordonné de $n$ nombres réels :

$$\mathbf{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$$

Le produit scalaire entre deux vecteurs $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$ est défini par :

$$⟨\mathbf{x},\mathbf{y}⟩={\mathbf{x}}^T\mathbf{y}=\sum _{i=1}^n{x}_i{y}_i$$

La norme euclidienne est $\parallel \mathbf{x}\parallel =\sqrt{{\mathbf{x}}^T\mathbf{x}}$.

Deux vecteurs sont orthogonaux si ${\mathbf{x}}^T\mathbf{y}=0$.

Matrices

Une matrice $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ est un tableau de $m$ lignes et $n$ colonnes. Les opérations fondamentales sont :

• Transposée : $[{\mathbf{A}}^T{]}_{ij}=[\mathbf{A}{]}_{ji}$
• Produit matriciel : $[\mathbf{AB}{]}_{ij}=\sum _k{a}_{ik}{b}_{kj}$
• Trace : $\text{tr}(\mathbf{A})=\sum _i{a}_{ii}$ (matrices carrées)
• Déterminant : $det(\mathbf{A})$ (matrices carrées)

Propriétés du produit :

• $(\mathbf{AB}{)}^T={\mathbf{B}}^T{\mathbf{A}}^T$
• $(\mathbf{ABC})=\mathbf{A}(\mathbf{BC})$ (associativité)
• En général, $\mathbf{AB}\ne \mathbf{BA}$ (non-commutatif)

Matrices particulières

Type	Définition	Propriétés
Symétrique	$\mathbf{A}={\mathbf{A}}^T$	Valeurs propres réelles
Orthogonale	${\mathbf{A}}^T\mathbf{A}=\mathbf{I}$	Préserve les normes
Diagonale	$a_{ij}=0$ si $i\ne j$	${\mathbf{A}}^{-1}=\text{diag}(1/a_{ii})$
Identité	${\mathbf{I}}_{ij}={\delta }_{ij}$	$\mathbf{AI}=\mathbf{IA}=\mathbf{A}$

Transformations linéaires

Une matrice $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ définit une application linéaire $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ par $f(\mathbf{x})=\mathbf{A}\mathbf{x}$.

L'image du cercle unité par différentes matrices illustre la nature géométrique des transformations linéaires :

Figure 1 : Image du cercle unité par différentes transformations linéaires

Systèmes linéaires et inverse

Inverse d'une matrice

Une matrice carrée $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ est inversible s'il existe ${\mathbf{A}}^{-1}$ telle que :

$$\mathbf{A}{\mathbf{A}}^{-1}={\mathbf{A}}^{-1}\mathbf{A}=\mathbf{I}$$

$\mathbf{A}$ est inversible si et seulement si $det(\mathbf{A})\ne 0$.

Propriétés :

• $({\mathbf{A}}^{-1}{)}^{-1}=\mathbf{A}$
• $(\mathbf{AB}{)}^{-1}={\mathbf{B}}^{-1}{\mathbf{A}}^{-1}$
• $({\mathbf{A}}^T{)}^{-1}=({\mathbf{A}}^{-1}{)}^T$

Résolution de systèmes linéaires

Le système $\mathbf{A}\mathbf{x}=\mathbf{b}$ admet :

• Une solution unique si $\mathbf{A}$ est inversible : $\mathbf{x}={\mathbf{A}}^{-1}\mathbf{b}$
• Une infinité de solutions si le système est sous-déterminé ($m<n$)
• Aucune solution exacte si le système est sur-déterminé ($m>n$), ce qui conduit à la notion de moindres carrés

Valeurs propres et vecteurs propres

Définition

Un scalaire $\lambda$ et un vecteur non nul $\mathbf{v}$ sont respectivement une valeur propre et un vecteur propre de $\mathbf{A}$ si :

$$\mathbf{A}\mathbf{v}=\lambda \mathbf{v}$$

Les valeurs propres sont les racines du polynôme caractéristique $det(\mathbf{A}-\lambda \mathbf{I})=0$.

Diagonalisation

Si $\mathbf{A}$ possède $n$ vecteurs propres linéairement indépendants, elle est diagonalisable :

$$\mathbf{A}=\mathbf{P}\mathbf{\Lambda }{\mathbf{P}}^{-1}$$

où $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$ et les colonnes de $\mathbf{P}$ sont les vecteurs propres.

Pour une matrice symétrique $\mathbf{A}={\mathbf{A}}^T$ :

• Toutes les valeurs propres sont réelles
• Les vecteurs propres sont orthogonaux : $\mathbf{A}=\mathbf{Q}\mathbf{\Lambda }{\mathbf{Q}}^T$ avec $\mathbf{Q}$ orthogonale

Figure 2 : Vecteurs propres d'une matrice symétrique, spectre et conditionnement

Conditionnement

Le nombre de conditionnement d'une matrice inversible est :

$$\kappa (\mathbf{A})=\parallel \mathbf{A}\parallel \cdot \parallel {\mathbf{A}}^{-1}\parallel =\frac{{\lambda }_{max}}{{\lambda }_{min}}$$

Un conditionnement élevé ($\kappa \gg 1$) signifie que le système est mal conditionné : de petites perturbations sur $\mathbf{b}$ entraînent de grandes variations sur la solution $\mathbf{x}$. Ce problème est central en régression linéaire et motive l'utilisation de la régularisation.

Projection orthogonale

Principe

La projection orthogonale de $\mathbf{b}$ sur l'image de $\mathbf{A}$ (notée $\text{Im}(\mathbf{A})$) est le vecteur $\hat{\mathbf{b}}\in \text{Im}(\mathbf{A})$ qui minimise la distance $\parallel \mathbf{b}-\hat{\mathbf{b}}\parallel$ :

$$\hat{\mathbf{b}}=\mathbf{A}({\mathbf{A}}^T\mathbf{A}{)}^{-1}{\mathbf{A}}^T\mathbf{b}$$

La matrice $\mathbf{P}=\mathbf{A}({\mathbf{A}}^T\mathbf{A}{)}^{-1}{\mathbf{A}}^T$ est la matrice de projection sur $\text{Im}(\mathbf{A})$.

Propriétés :

• ${\mathbf{P}}^2=\mathbf{P}$ (idempotente)
• ${\mathbf{P}}^T=\mathbf{P}$ (symétrique)
• Le résidu $\mathbf{e}=\mathbf{b}-\hat{\mathbf{b}}$ est orthogonal à $\text{Im}(\mathbf{A})$ : ${\mathbf{A}}^T\mathbf{e}=\mathbf{0}$

Figure 3 : Projection orthogonale sur une droite (2D) et sur un plan (3D)

Lien avec les moindres carrés

La solution au sens des moindres carrés du système sur-déterminé $\mathbf{A}\mathbf{x}\approx \mathbf{b}$ est :

$$\hat{\mathbf{x}}=\underset{\mathbf{x}}{\arg min}\parallel \mathbf{b}-\mathbf{A}\mathbf{x}{\parallel }^2=({\mathbf{A}}^T\mathbf{A}{)}^{-1}{\mathbf{A}}^T\mathbf{b}$$

C'est exactement le vecteur $\mathbf{x}$ tel que $\mathbf{A}\hat{\mathbf{x}}=\hat{\mathbf{b}}$, la projection de $\mathbf{b}$ sur $\text{Im}(\mathbf{A})$. Cette formule est au coeur de la régression linéaire.

Décomposition en valeurs singulières (SVD)

Définition

Toute matrice $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ admet une décomposition en valeurs singulières :

$$\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T$$

où :

• $\mathbf{U}\in {\mathbb{R}}^{m\times m}$ est orthogonale (vecteurs singuliers gauches)
• $\mathbf{\Sigma }\in {\mathbb{R}}^{m\times n}$ est diagonale avec ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$ (valeurs singulières)
• $\mathbf{V}\in {\mathbb{R}}^{n\times n}$ est orthogonale (vecteurs singuliers droits)

Géométriquement, la SVD décompose toute transformation linéaire en trois étapes : rotation, dilatation, rotation.

Figure 4 : Interprétation géométrique de la SVD : rotation → dilatation → rotation

Propriétés

• Le rang de $\mathbf{A}$ est le nombre de valeurs singulières non nulles
• Les valeurs propres de ${\mathbf{A}}^T\mathbf{A}$ sont ${\sigma }_i^2$
• $\parallel \mathbf{A}{\parallel }_F=\sqrt{\sum _i{\sigma }_i^2}$ (norme de Frobenius)
• La pseudo-inverse de Moore-Penrose est ${\mathbf{A}}^{+}=\mathbf{V}{\mathbf{\Sigma }}^{+}{\mathbf{U}}^T$

Formes quadratiques et matrices définies positives

Forme quadratique

Une forme quadratique associée à une matrice symétrique $\mathbf{A}$ est la fonction :

$$q(\mathbf{x})={\mathbf{x}}^T\mathbf{A}\mathbf{x}=\sum _{i,j}{a}_{ij}{x}_i{x}_j$$

La nature de la forme quadratique dépend du signe des valeurs propres de $\mathbf{A}$ :

Type	Condition	Valeurs propres
Définie positive	$q(\mathbf{x})>0$ pour tout $\mathbf{x}\ne \mathbf{0}$	Toutes $>0$
Semi-définie positive	$q(\mathbf{x})\ge 0$ pour tout $\mathbf{x}$	Toutes $\ge 0$
Indéfinie	$q$ change de signe	Positives et négatives

Figure 5 : Lignes de niveau de formes quadratiques selon la nature de la matrice

Matrices définies positives

Les matrices définies positives jouent un rôle central en estimation statistique :

• La matrice de covariance $\mathbf{\Sigma }$ est semi-définie positive
• La matrice ${\mathbf{A}}^T\mathbf{A}$ est toujours semi-définie positive
• ${\mathbf{A}}^T\mathbf{A}$ est définie positive si et seulement si $\mathbf{A}$ est de rang plein

Propriétés : Si $\mathbf{A}$ est définie positive, alors :

• $\mathbf{A}$ est inversible
• $det(\mathbf{A})>0$
• ${\mathbf{A}}^{-1}$ est aussi définie positive
• Il existe une unique matrice ${\mathbf{A}}^{1/2}$ définie positive telle que ${\mathbf{A}}^{1/2}{\mathbf{A}}^{1/2}=\mathbf{A}$

Dérivation matricielle

Les dérivées matricielles sont essentielles pour l'optimisation en estimation et régression.

Gradient

Le gradient d'une fonction scalaire $f:{\mathbb{R}}^n\to \mathbb{R}$ par rapport à $\mathbf{x}$ est :

$${\mathrm{\nabla }}_{\mathbf{x}}f=\left[\begin{array}{c}\frac{\partial f}{\partial x_1}\\ ⋮\\ \frac{\partial f}{\partial x_n}\end{array}\right]$$

Formules utiles

Pour $\mathbf{A}$ matrice constante, $\mathbf{b}$ vecteur constant :

Fonction	Gradient
$f(\mathbf{x})={\mathbf{b}}^T\mathbf{x}$	$\mathrm{\nabla }f=\mathbf{b}$
$f(\mathbf{x})={\mathbf{x}}^T\mathbf{A}\mathbf{x}$	$\mathrm{\nabla }f=(\mathbf{A}+{\mathbf{A}}^T)\mathbf{x}$
$f(\mathbf{x})={\mathbf{x}}^T\mathbf{A}\mathbf{x}$ ($\mathbf{A}$ symétrique)	$\mathrm{\nabla }f=2\mathbf{A}\mathbf{x}$
$f(\mathbf{x})=|\mathbf{b}-\mathbf{A}\mathbf{x}{|}^2$	$\mathrm{\nabla }f=-2{\mathbf{A}}^T(\mathbf{b}-\mathbf{A}\mathbf{x})$

La dernière formule est directement utilisée pour dériver la solution des moindres carrés : en posant $\mathrm{\nabla }f=\mathbf{0}$, on obtient les équations normales ${\mathbf{A}}^T\mathbf{A}\mathbf{x}={\mathbf{A}}^T\mathbf{b}$.