AnnalesÉcoles d'ingénieurs

X-ENS PC 2024 — Maths

Distance entre nuages de points à déplacement près (problème de Procuste) · 7 pages

Le sujet définit le groupe des déplacements de $\mathbb{R}^d$ , couples $(\tau, R)$ avec $R \in \mathrm{SO}_d(\mathbb{R})$ , et la distance $\delta(x, y)$ entre deux familles de $n$ points comme la plus petite distance de $y$ à l'image de $x$ par un déplacement. Après avoir montré que $\delta$ est symétrique et vérifie l'inégalité triangulaire, il ramène le calcul au maximum de $\langle Z, R\rangle = \operatorname{tr}(Z^\top R)$ sur $\mathrm{SO}_d(\mathbb{R})$ en centrant les nuages, l'existence d'un optimum venant de la compacité. Une décomposition en valeurs singulières de $Z$ donne alors $\delta(x, y)$ en fonction des variances des nuages et des valeurs singulières, avec une correction sur la plus petite d'entre elles lorsque $\det Z < 0$ .

Le sujet, partie par partie

Notations et Partie 1 — Préliminaires p. 2–3

Espaces préhilbertiens et euclidiens · Matrices orthogonales et rotations · Inégalités classiques — produit scalaire de Frobenius, trace d'un produit, groupe orthogonal, groupe spécial orthogonal, coefficients diagonaux d'une matrice orthogonale

Partie 2 — Ensemble des déplacements de $\mathbb{R}^d$ p. 3–4

Isométries et groupe orthogonal · Groupes · Géométrie affine et euclidienne · Matrices orthogonales et rotations — déplacement, translation, rotation vectorielle, loi de composition, élément neutre, groupe non commutatif

Partie 3 — Distance à déplacement près p. 4–5

Actions de groupes · Espaces vectoriels normés · Isométries et groupe orthogonal — action d'un groupe, orbite, distance entre orbites, inégalité triangulaire, borne inférieure

Partie 4 — Un problème d'optimisation p. 5

Extrema et optimisation · Compacité · Groupes de matrices · Topologie des espaces de matrices — moindres carrés, isobarycentre, $\mathrm{SO}_d(\mathbb{R})$ fermé borné, existence d'un minimum, variance empirique

Partie 5 — Calcul de $\delta(x, y)$ lorsque $\det Z > 0$ p. 6

Valeurs singulières et conditionnement · Théorème spectral · Matrices orthogonales et rotations · Matrices symétriques positives — décomposition en valeurs singulières, matrice $Z^\top Z$ , base orthonormée de vecteurs propres, problème de Procuste orthogonal

Partie 6 — Le cas où $\det Z < 0$ p. 6–7

Matrices orthogonales et rotations · Valeurs singulières et conditionnement · Sous-espaces stables · Déterminants · Inégalités classiques — valeurs propres d'une matrice orthogonale, déterminant $-1$ , hyperplan stable, majoration de la trace, plus petite valeur singulière

X-ENS PC 2024 — Maths

Le sujet, partie par partie

Notations et Partie 1 — Préliminaires p. 2–3

Partie 2 — Ensemble des déplacements de ℝd\mathbb{R}^d p. 3–4

Partie 3 — Distance à déplacement près p. 4–5

Partie 4 — Un problème d'optimisation p. 5

Partie 5 — Calcul de δ(x,y)\delta(x, y) lorsque det⁡Z>0\det Z > 0 p. 6

Partie 6 — Le cas où det⁡Z<0\det Z < 0 p. 6–7

Dans l'édifice

Partie 2 — Ensemble des déplacements de $\mathbb{R}^d$ p. 3–4

Partie 5 — Calcul de $\delta(x, y)$ lorsque $\det Z > 0$ p. 6

Partie 6 — Le cas où $\det Z < 0$ p. 6–7