13.4 Retour sur la méthode des moindres carrés

Rappelons qu’une solution des moindres carrés d’un système \(\mathbf{A}\mathbf{x} = \mathbf{b}\) est un vecteur \(\mathbf{x}\) qui minimise \(\|\mathbf{A}\mathbf{x} -\mathbf{b}\|\).

Dans cette section, nous utilisons la décomposition en valeurs singulières de \(\mathbf{A}\) afin de trouver une solution des moindres carrés sans utiliser le calcul différentiel ou les projections orthogonales.

Observons que le problème initial revient à minimiser \(\|\mathbf{A}\mathbf{x} - \mathbf{b}\|^2\).

Soit \(\mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}\) une décomposition en valeurs singulières de \(\mathbf{A}\). Si \(\mathbf{y} = \mathbf{V}^\mathsf{T}\mathbf{x}\), alors \[\begin{align*} \|\mathbf{A}\mathbf{x} -\mathbf{b}\|^2 & = (\mathbf{A}\mathbf{x} - \mathbf{b})^\mathsf{T}(\mathbf{A}\mathbf{x}-\mathbf{b}) \\ & = (\mathbf{U}\mathbf{\Sigma} \mathbf{y} - \mathbf{b})^\mathsf{T}(\mathbf{U}\mathbf{\Sigma} \mathbf{y}-\mathbf{b}) \\ & = (\mathbf{y}^\mathsf{T}\mathbf{\Sigma}^\mathsf{T}\mathbf{U}^\mathsf{T}- \mathbf{b}^\mathsf{T})(\mathbf{U}\mathbf{\Sigma} \mathbf{y}-\mathbf{b}) \\ & = (\mathbf{y}^\mathsf{T}\mathbf{\Sigma}^\mathsf{T}\mathbf{U}^\mathsf{T})(\mathbf{U}\mathbf{\Sigma} \mathbf{y}) - 2\mathbf{y}^\mathsf{T}(\mathbf{\Sigma}^\mathsf{T}\mathbf{U}^\mathsf{T}\mathbf{b}) + \mathbf{b}^\mathsf{T}\mathbf{b} \\ & = \mathbf{y}^\mathsf{T}\mathbf{\Sigma}^\mathsf{T}\mathbf{\Sigma} \mathbf{y} - 2\mathbf{y}^\mathsf{T}(\mathbf{\Sigma}^\mathsf{T}\mathbf{U}^\mathsf{T}\mathbf{b}) + \mathbf{b}^\mathsf{T}\mathbf{b} \\ \end{align*}\] Observons que \(\mathbf{b}^\mathsf{T}\mathbf{b}\) est une constante et que \(\mathbf{\Sigma}^\mathsf{T}\mathbf{\Sigma}\) est une matrice diagonale carrée où le \(i\)-ième élément de la diagonale est nul lorsque \(i > r\), \(r\) étant le nombre de valeurs singulières de \(\mathbf{A}\).

En prenant \(\mathbf{d} = \mathbf{\Sigma}^\mathsf{T}\mathbf{U}^\mathsf{T}\mathbf{b}\), on peut réécrire \(\mathbf{y}^\mathsf{T}\mathbf{\Sigma}^\mathsf{T}\mathbf{\Sigma} \mathbf{y} - 2\mathbf{y}^\mathsf{T}(\mathbf{\Sigma}^\mathsf{T}\mathbf{U}^\mathsf{T}\mathbf{b})\) sous la forme \[\sum_{i=1}^r (\sigma_i^2 y_i^2 - 2d_i y_i) =\sum_{i=1}^r \sigma_i^2 \left(y_i^2 - 2\frac{d_i}{\sigma_i^2}y_i\right).\]

La complétion du carré donne \[\begin{equation} \sum_{i=1}^r \left(\sigma_i^2\left(y_i - \frac{d_i}{\sigma_i^2}\right)^2 - \left(\frac{d_i}{\sigma_i}\right)^2\right).\tag{13.1} \end{equation}\]

Ainsi, le minimum est atteint lorsque \(y_i = \frac{d_i}{\sigma_i^2}\) pour \(i = 1,\ldots, r\), ou, de façon équivalente, lorsque \(y_i = \frac{1}{\sigma_i}(\mathbf{U}^\mathsf{T}\mathbf{b})_i\) pour \(i = 1,\ldots, r\). Posons \(y_i = 0\) lorsque \(i > r\). Puisque \(\sigma_i = 0\) dans ce cas, le vecteur \(\mathbf{y}\) devient \[\mathbf{y} = \mathbf{\Sigma}^+ \mathbf{U}^\mathsf{T}\mathbf{b},\] où \(\mathbf{\Sigma}^+\) est obtenu de \(\mathbf{\Sigma}\) en remplaçant chaque élément non nul par son inverse et en prenant la transposée de la matrice ainsi obtenue. Puisque \(\mathbf{y} = \mathbf{V}^\mathsf{T}\mathbf{x}\) et que \(\mathbf{V}\) est une matrice orthogonale, on obtient \[\mathbf{x} = \mathbf{V}\mathbf{y} = \mathbf{V}(\mathbf{\Sigma}^+ \mathbf{U}^\mathsf{T}\mathbf{b}) = (\mathbf{V}\mathbf{\Sigma}^+ \mathbf{U}^\mathsf{T}) \mathbf{b}.\]

La matrice \(\mathbf{V}\mathbf{\Sigma}^+ \mathbf{U}^\mathsf{T}\) est un pseudo-inverse de Moore-Penrose de \(\mathbf{A}\) et est dénotée par \(\mathbf{A}^+\).

Autrement dit, \(\mathbf{A}^+ \mathbf{b}\) est une solution des moindres carrés de \(\mathbf{A}\mathbf{x} = \mathbf{b}.\) Notons qu’il peut y avoir plusieurs solutions des moindres carrés. Comme nous l’avons vu précédemment, on peut utiliser toute autre valeur non nulle pour \(y_i,\) \(i > r\). Cependant, si toutes ces valeurs sont nulles, on obtient une solution \(\mathbf{x}\) qui minimise \(\|\mathbf{x}\|.\)

Exemple 13.2 Soient \(\mathbf{A} = \begin{bmatrix} 2 & 1 \\ 2 & 1 \\ \frac{2}{5} & \frac{11}{5} \\ \frac{2}{5} & \frac{11}{5} \end{bmatrix}\) et \(\mathbf{b} = \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3\end{bmatrix}\). Nous obtenons une solution des moindres carrés de \(\mathbf{A} \mathbf{x} = \mathbf{b}\) en calculant \(\mathbf{A}^+\mathbf{b}\).

Le produit \(\mathbf{U}\mathbf{\Sigma}\mathbf{V}^\mathsf{T}\) est une décomposition en valeurs singulières de \(\mathbf{A},\) où \[\begin{align*} \mathbf{U} & = \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{bmatrix} \\ \mathbf{\Sigma} & = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 0 & 0 \\ 0 & 0 \end{bmatrix} \\ \mathbf{V} & = \begin{bmatrix} \frac{3}{5} & -\frac{4}{5} \\ \frac{4}{5} & \frac{3}{5} \end{bmatrix}. \end{align*}\] Si \[\mathbf{A}^+ = \mathbf{V} \begin{bmatrix} \frac{1}{4} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \end{bmatrix} \mathbf{U}^\mathsf{T}= \begin{bmatrix} \frac{11}{40} & \frac{11}{40} & -\frac{1}{8} & -\frac{1}{8} \\ -\frac{1}{20} & -\frac{1}{20} & \frac{1}{4} & \frac{1}{4} \end{bmatrix},\] une solution des moindres carrés est donnée par \(\mathbf{x} = \mathbf{A}^+ \mathbf{b} = \begin{bmatrix} -\frac{7}{20} \\ \frac{6}{5}\end{bmatrix}.\)

Exercices

1. Utilisez la méthode décrite dans cette section afin d’obtenir la solution des moindres carrés de \(\mathbf{A}\mathbf{x} = \mathbf{b}\), où \(\mathbf{A} = \begin{bmatrix} -2 & 11 \\ 5 & 10 \\ 14 & -2 \end{bmatrix}\) et \(\mathbf{b} = \begin{bmatrix} 1 \\ -2 \\ 3 \end{bmatrix}.\) Vous pouvez utiliser la décomposition en valeurs singulières suivante de \(\mathbf{A}\) : \[\begin{bmatrix} -\frac{2}{15} & \frac{11}{15} & \frac{2}{3} \\ \frac{1}{3} & \frac{2}{3} & -\frac{2}{3} \\ \frac{14}{15} & -\frac{2}{15} & \frac{1}{3} \end{bmatrix} \begin{bmatrix} 15 & 0 \\ 0 & 15 \\ 0 & 0\end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix}.\]

2. Soit \(\mathbf{A} \in \mathbb{R}^{2\times 2}.\) Supposons que la décomposition en valeurs singulières de \(\mathbf{A}\) est donnée par \(\mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}\), où \(\mathbf{U}, \mathbf{V} \in \mathbb{R}^{2 \times 2}\) sont orthogonales et \(\mathbf{\Sigma} = \begin{bmatrix} \sigma & 0 \\ 0 & 0 \end{bmatrix},\) \(\sigma > 0.\)

   1. Montrez que \(\mathbf{G} = \mathbf{V} \begin{bmatrix} \frac{1}{\sigma} & 0 \\ 0 & \delta \end{bmatrix} \mathbf{U}^\mathsf{T}\) est un pseudo-inverse de \(\mathbf{A}\) pour tout \(\delta \in \mathbb{R}.\)

   2. Donnez deux pseudo-inverses distincts de \(\begin{bmatrix} 1 & -1 \\ -2 & 2 \end{bmatrix}.\)

Solutions

1. Notons que \[\mathbf{A}^+ = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{15} & 0 & 0 \\ 0 & \frac{1}{15} & 0 \end{bmatrix} \begin{bmatrix} -\frac{2}{15} & \frac{1}{3} & \frac{14}{15} \\ \frac{11}{15} & \frac{2}{3} & -\frac{2}{15} \\ \frac{2}{3} & -\frac{2}{3} & \frac{1}{3} \end{bmatrix}.\] On obtient alors une solution des moindres carrés en calculant \[\mathbf{x} = \mathbf{A}^+\mathbf{b} = \begin{bmatrix} \frac{2}{15} \\ -\frac{1}{15} \end{bmatrix}.\]

2. 1. Montrons que \(\mathbf{A}\mathbf{G}\mathbf{A}=\mathbf{A}.\) Si \(\mathbf{S}\) dénote la matrice \(\begin{bmatrix} \frac{1}{\sigma} & 0 \\ 0 & \delta \end{bmatrix},\) alors \[\begin{align*} \mathbf{A}\mathbf{G}\mathbf{A} & = (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T})( \mathbf{V} \mathbf{S} \mathbf{U}^\mathsf{T}) (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}) \\ & = \mathbf{U} \mathbf{\Sigma} \mathbf{S} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}\\ & = \mathbf{U} \begin{bmatrix} \sigma & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} \frac{1}{\sigma} & 0 \\ 0 & \delta \end{bmatrix} \begin{bmatrix} \sigma & 0 \\ 0 & 0 \end{bmatrix} \mathbf{V}^\mathsf{T}\\ & = \mathbf{U} \begin{bmatrix} \sigma & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \mathbf{V}^\mathsf{T}\\ & = \mathbf{U} \begin{bmatrix} \sigma & 0 \\ 0 & 0 \end{bmatrix} \mathbf{V}^\mathsf{T}\\ & = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}\\ & = \mathbf{A} \end{align*}\] tel que désiré.

   2. Une décomposition en valeurs singulières de \(\begin{bmatrix} 1 & -1 \\ -2 & 2 \end{bmatrix}\) est donnée par \[\begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \\ \end{bmatrix} \begin{bmatrix} \sqrt{10} & 0 \\ 0 & 0 \\ \end{bmatrix} \begin{bmatrix} -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}.\] En utilisant le résultat de la partie précédente, les deux matrices suivantes sont des pseudo-inverses de \(\begin{bmatrix} 1 & -1 \\ -2 & 2 \end{bmatrix}\) : \[\begin{bmatrix} -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}} & 0 \\ 0 & 0 \\ \end{bmatrix} \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \\ \end{bmatrix} = \begin{bmatrix} \frac{1}{10} & -\frac{1}{5} \\ -\frac{1}{10} & \frac{1}{5} \end{bmatrix}\] et \[\begin{bmatrix} -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}} & 0 \\ 0 & \frac{1}{\sqrt{10}} \\ \end{bmatrix} \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \\ \end{bmatrix} = \begin{bmatrix} \frac{3}{10} & -\frac{1}{10} \\ \frac{1}{10} & \frac{3}{10} \end{bmatrix}.\]