Applications de la descente de gradient au calcul de projections orthogonales dans $\mathbb{R}^n$

Projection sur un sous espace linéaire

Le calcul de projections orthogonales est probablement l'opération la plus importante en mathématiques. On va ici essayer de voir comment il est parfois possible de calculer celle-ci analytiquement mais comment dans la plus grande majorité des cas, il n'existe pas de calcul en offrant une expression simple.

Commençons par le cas le plus simple, celui qui l'on sait calculer. On considère un sous-espace vectoriel $\mathcal{V} \sub \mathbb{R}^n$ de dimension $k$ engendré par $A \in \mathcal{M}_{n, k}(\mathbb{R})$ que l'on suppose de rang plein. On cherche la projection orthogonale $x^* = A \alpha^*$ de $b \in \mathbb{R}^n$ sur $\mathcal{V}$, c'est à dire: $$ x^* = \underset{x \in \mathcal{V}}{\operatorname{argmin}} \| b - x \|^2 = \underset{\alpha \in \mathbb{R}^k}{\operatorname{argmin}} \| b - \alpha A \| = \underset{\alpha \in \mathbb{R}^k}{\operatorname{argmin}} \gamma(\alpha) $$ avec: $$ \begin{align*} \gamma(\alpha) &= \| b - A \alpha \|^2 \\ &= (b-A\alpha)^\top(b-A\alpha) \\ &= b b^\top - 2 \alpha^\top A^\top b + \alpha^\top A^\top A \alpha \end{align*} $$ Maintenant, on s'intéresse au minimum de $\gamma$ sur $\mathbb{R}^k$. On va donc s'intéresser à ses points stationnaires. Montrons dans un premier temps la convexité de $\gamma$ via la Hessienne. Soit $\alpha \in \mathbb{R}^k$ $$ H_{\gamma}(\alpha) = \frac{\partial^2 \gamma}{\partial \alpha^2} = \frac{\partial}{\partial \alpha}\left( -2 Ab + 2 \alpha^\top A^\top A \right) = 2 A^\top A $$ Ainsi, $H_{\gamma}(\alpha)$ est à une constante près une matrice de Gram donc $H_\gamma(\alpha) \succ 0$. Ainsi par condition d'optimalité globale tout point stationnaire est également un minimum global de $\gamma$. Par ailleurs: $$ \begin{align*} \Delta_\alpha \gamma (\alpha^*) &= -2 A^\top b + 2 A^\top A \alpha^* = 0 \\ &\Leftrightarrow A^\top A \alpha^* = A^\top b \\ &\Leftrightarrow \alpha^* = (A^\top A)^{-1}A^\top b \end{align*} $$ En effet puisque l'on a supposé que $\operatorname{rang}(A) = k$, on a bien que $A^\top A$ est inversible. Ainsi on obtient finalement: $$ \boxed{ x^* = A(A^\top A)^{-1} A^\top b } $$

Exemple

On considère un pixel $p = (r\;g\;b)^\top \in \mathbb{R}^3$ et on va le projeter sur un plan. On considère les matrices génératrices suivantes: $$ A_r = \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ 1 & 0 \end{pmatrix} \text{,}\quad A_g = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \end{pmatrix} \text{,}\quad A_b = \begin{pmatrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} $$ L'application de la formule précédente donne: $$ \mathcal{p}_{A_r}(p) = \begin{pmatrix} r \\ \frac{g+b}{2} \\ \frac{g+b}{2} \end{pmatrix} \text{,}\quad \mathcal{p}_{A_g}(p) = \begin{pmatrix} \frac{r+b}{2} \\ g \\ \frac{r+b}{2} \end{pmatrix} \text{,}\quad \mathcal{p}_{A_b}(p) = \begin{pmatrix} \frac{r+g}{2} \\ \frac{r+g}{2} \\ b \\ \end{pmatrix} \text{,}\quad $$ On peut alors définir pour $c \in \{ r, g, b\}$ et une image $\mathbf{F}$ une image "projetée", $\mathbf{F}_c$ telle que: $$ \mathbf{F}_c[n, m] = \mathcal{p}_{A_c}(\mathbf{F}[n, m]) $$

On peut observer que $\mathbf{F}_c$ préserve fidèlement le canal $c$ tandis que les deux autres sont écrasés sur leur moyenne. Alors l'image conserve toute sa structure sur le canal $c$ mais devient achromatique dans le plan orthogonal. Ceci est particulièrement visible sur l'image $\mathbf{F}_g$ où l'herbe en arrière plan conserve bien sa couleur mais les autres couleurs sont écrasées.

Projection sur un sous-espace non linéaire avec solution analytique

Bon c'est très sympa, c'est notamment exactement ce qui est utilisé pour calculer des régressions linéaires, mais ça demande tout de même que le sous-espace soit linéaire. De manière plus générale, la démonstration précédente ne donne pas de solution au problème plus général

$$ (\mathcal{P}_{f, b}) \quad \underset{x \in \operatorname{Dom}(f)}{\operatorname{argmin}} \| f(x) - b \| $$ Est-ce que ça veut pour autant dire que l'on connait pas de solution analytique du tout? Non. Considérons à titre d'exemple la fonction $f = \operatorname{id}_{[0,1]^3}$, donc un cube dans $\mathbb{R}^3$. Soit $b \in \mathbb{R}^3$ $$ \begin{align*} x^* &= \underset{x \in [0,1]^3}{\operatorname{argmin}\| x - b \|^2} \\ &= \underset{x_1 \in [0,1]}{\operatorname{argmin}}(x_1 - b_1)^2 + \underset{x_2 \in [0,1]}{\operatorname{argmin}}(x_2 - b_2)^2 + \underset{x_3 \in [0,1]}{\operatorname{argmin}}(x_3 - b_3)^2 \\ \end{align*} $$ Par ailleurs, $(x_i - b_i)^2$ est une parabole centrée en $b_i$. On distingue alors 3 cas: $$ x_i^* = \underset{x_i \in [0,1]}{\operatorname{argmin}}(x_i - b_i)^2 = \begin{cases} 0 \quad\text{si}\quad b_i < 0 \\ b_i \quad\text{si}\quad 0 < b_i < 1 \\ 1 \quad\text{si}\quad b_i > 1 \\ \end{cases} $$ Ainsi, dans tous les cas, $x_i^* = \operatorname{max}(\operatorname{min}(b_i, 1), 0)$. On a donc bien trouvé une expression analytique de la projection bien que l'espace considéré ne soit pas linéaire. On peut voir ci-dessous, en vert représenté $b \in \mathbb{R}^3$ et en rouge $x^* \in [0,1]^3$

On connaît la paramétrisation du tore sur $[0, 2 \pi]^2$ $$ \begin{cases} x(u, v) = (R + r \cos v) \cos u \\ y(u, v) = (R + r \cos v) \sin v \\ z(u, v) = r \sin v \end{cases} $$ $u \in [0, 2\pi]$ indique la position selon le plan $xy$, c'est pourquoi $z(u, v)$ ne dépend pas de $v$. Tandis que $v$ donne la position par rapport à "l'enroulement" autour du tore. On note $T = (x\;y\;z)^\top$. Pour rappel, on cherche: $$ (u^*, v^*) = \underset{(u, v) \in [0, 2 \pi]^2}{\operatorname{argmin}}\|T(u, v) - b\|^2 = \underset{(u, v) \in [0, 2 \pi]^2}{\operatorname{argmin}}d_b(u, v) $$ Par ailleurs, $$ \begin{align*} d_b(u, v) &= [(R + r \cos u)\cos v - b_1]^2 + [(R + r \cos u)\sin v - b_2]^2 + [r \sin u - b_3]^2 \\ &= [A\cos v - b_1]^2 + [A\sin v - b_2]^2 + [r \sin u - b_3]^2 \\ &= A^2 \cos(v)^2 + b_1^2 - 2b_1A \cos v + A^2 \sin(v)^2 + b_2^2 - 2b_2A \sin(v) + r^2 \sin(u)^2 + b_3^2 - 2rb_3 \sin u \\ &= \| b \|^2 + A^2 - 2b_1 A \cos v - 2b_2A \sin v - 2rb_3 \sin u + r^2 \sin(u)^2 \\ &= \| b \|^2 + R^2 + r^2 + 2 R r \cos u - 2(R + r \cos u)(b_1 \cos v + b_2 \sin v) + rb_3 \sin u \end{align*} $$ Maintenant, on obtient, $$ \nabla d_b(u, v) = \begin{pmatrix} -2r [ \sin u ( b_1 \cos v + b_2 \sin v - R) -b_3 \cos u] \\ 2(R + r \cos u)(b_1 \sin v - b_2 \cos v) \end{pmatrix} $$

La condition $\nabla_u d_b(u^*, v^*)=0$ donne, à condition que $R > r$, $v^* = \operatorname{arctan}\left(\displaystyle\frac{b_2}{b_1}\right)$. Puis, par injection on trouve: $$ v^* = \operatorname{arctan}\left(\frac{b_2}{b_1}\right) \quad\text{et}\quad u^* = \operatorname{arctan}\left(\frac{b_3}{\sqrt{b_1^2+b_2^2}-R}\right) $$ Ainsi, en injectant ces valeurs dans la paramétrisation du tore on obtient, en posant $\rho = \sqrt{b_1^2 + b_2^2}$ et $D = \sqrt{(\rho - R)^2 + b^3}$ (la distance de $b$ au cercle centrale) $$ \boxed{ x^* = \frac{b_1}{\rho}\left(R + \frac{r(\rho - R)}{D} \right) \text{,}\quad y^* = \frac{b_2}{\rho}\left(R + \frac{r(\rho - R)}{D} \right) \text{,}\quad z^* = \frac{r b_3}{D} } $$

$x$ 3.00

$y$ 1.00

$z$ 2.00