Plus petit cadre englobant aligné sur l'axe de l'hyper-ellipsoïde
Laisser $E$ Soit le $n$-ellipsoïde dimensionnel défini par $$E:=\{x \in \mathbb{R}^n: (x-c)^T A (x-c) \le 1\},$$ où $c \in \mathbb{R}^n$ est le centre de l'ellipsoïde, et $A \in \mathbb{R}^{n \times n}$ est une matrice symétrique définie positive.
Question: Comment calculer efficacement le cadre englobant aligné sur l'axe des coordonnées qui contient à peine l'ellipsoïde?
Pour un exemple 2D, voir l'image suivante:
Remarque: je pose cette question et y répond moi-même, car cette question (sous sa forme générale) est étonnamment absente de math.stackexchange même après plus de 10 ans. De bonnes réponses à cette question sont difficiles à trouver sur Internet en général. Après avoir cherché sur Google, j'ai finalement dû comprendre cela moi-même, et je poste ici pour éviter aux futurs gens le même problème. De nombreux sites Web discutent de la question dans le cas particulier de$2D$ et $3D$, mais le format de l'ellipse est donné en termes d'axes et d'angles plutôt que de matrices SPD, et les formules ne se généralisent pas à n dimensions. La bonne réponse est donnée par achilles hui dans les commentaires à la question fermée suivante: Boîte englobante de l'ellipsoïde mais aucune preuve n'y est fournie, et la question est fermée, donc je ne peux pas fournir la réponse avec la preuve. Même si cette question était rouverte, elle se concentre sur le cas 3D avec axes et angles plutôt que sur le cas n-dimensionnel avec des matrices SPD.
Réponses
Vecteur donné $\rm{c} \in \Bbb R^n$ et matrice $\rm{Q} \succ \rm{O}_n$, laisser
$$\mathcal E := \left\{ \rm{x} \in \Bbb R^n \mid \left( \rm{x} - \rm{c} \right)^\top \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right) \leq 1 \right\}$$
Laisser $g (\rm{x}) := \left( \rm{x} - \rm{c} \right)^\top \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$. Le champ vectoriel orthogonal à la frontière de l'ellipsoïde$\mathcal E$ est
$$\nabla g (\rm{x}) = 2 \, \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$$
Laissez-nous choisir $i \in [n]$ et concentrez-vous sur le $i$-ème axe. Laisser$\rm{P}_i := \rm{e}_i \rm{e}_i^\top$ être la matrice de projection qui se projette sur le $i$-ème axe. Aux deux points où l'ellipsoïde$\mathcal E$ touche la (plus petite) boîte englobante, nous avons $\rm{P}_i \nabla g (\rm{x}) = \nabla g (\rm{x})$, c'est à dire,
$$\left( \rm{I}_n - \rm{P}_i \right) \underbrace{ {\rm Q}^{-1} \left( \rm{x} - \rm{c} \right)}_{=: {\rm y}} = 0_n$$
Par conséquent, $y_i$ est gratuit et toutes les autres entrées de $\rm y$ sont nuls, c'est-à-dire ${\rm y} = t \, {\rm e}_i$, ou, ${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i$. Intersection de cette ligne avec la limite de l'ellipsoïde$\mathcal E$, on obtient
$$t^2 = \left( {\rm e}_i^\top {\rm Q} \, {\rm e}_i \right)^{-1} = q_{ii}^{-1}$$ ou, $t = \pm \frac{1}{\sqrt{q_{ii}}}$. Ainsi, l'ellipsoïde$\mathcal E$ touche la (plus petite) boîte englobante aux points
$${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i = {\rm c} \pm \frac{1}{\sqrt{q_{ii}}} \, {\rm Q} \, {\rm e}_i$$
et, projetant sur le $i$-ème axe,
$$x_i = c_i \pm \frac{1}{\sqrt{q_{ii}}} \, {\rm e}_i^\top {\rm Q} \, {\rm e}_i = c_i \pm \frac{q_{ii}}{\sqrt{q_{ii}}} = c_i \pm \sqrt{q_{ii}}$$
Par conséquent, la boîte englobante est
$$\color{blue}{\left[ c_1 - \sqrt{q_{11}}, c_1 + \sqrt{q_{11}} \right] \times \left[ c_2 - \sqrt{q_{22}}, c_2 + \sqrt{q_{22}} \right] \times \cdots \times \left[ c_n - \sqrt{q_{nn}}, c_n + \sqrt{q_{nn}} \right]}$$
La boîte englobante, $B$, est donné par $$B = \prod_{i=1}^n\left[c_i - \sqrt{d_i}, c_i + \sqrt{d_i}\right],$$ où $d_i$ est le $i^\text{th}$ entrée diagonale de $A^{-1}$.
Preuve:
Laisser $e_i = (0,\dots,0,1,0,\dots,0)$ être le vecteur avec $i^\text{th}$entrée égale à un et toutes les autres entrées égales à zéro. le$i^\text{th}$ différence de coordonnées entre un point $x$ et le point $c$ est donné par $e_i^T (x-c)$. Les points sur la surface de l'ellipse satisfont$x \in \mathbb{R}^n: (x-c)^T A (x-c) = 1$. Par conséquent, la distance entre le centre de l'ellipse et le cadre englobant dans la direction$i$ est la solution au problème d'optimisation suivant: $$ \begin{aligned} \max_{x} &\quad e_i^T (x-c) \\ \text{such that}&\quad (x - c)^TA(x-c) = 1. \end{aligned} $$ Maintenant, laisse $$A^{-1} = R^TR$$ être une factorisation de $A^{-1}$, et laissez $r_i$ Soit le $i^\text{th}$ colonne de $R$. Par exemple,$R$ pourrait être le facteur Cholesky, ou $R$ pourrait être $A^{-1/2}$, ou $R$pourrait être le facteur de toute autre factorisation de cette forme. Faire le changement de variables$u := R^{-T}(x-c),$ effectuer des manipulations algébriques simples et utiliser le fait que $e_i^T R^T = r_i^T$, le problème d'optimisation devient $$ \begin{aligned} \max_{u} &\quad r_i^T u \\ \text{such that}&\quad \|u\| = 1. \end{aligned} $$ La solution à ce problème d'optimisation est donnée par $u = r^i/\|r_i\|$, et la valeur optimale est $$r_i^T u = \frac{r_i^Tr_i}{\|r_i\|} = \sqrt{r_i^Tr_i} = \sqrt{\left(A^{-1}\right)_{ii}} = \sqrt{d_i}.$$
Par conséquent, dans le $i^\text{th}$ direction, la boîte englobante de l'ellipsoïde s'étend de $c_i - \sqrt{d_i}$ à $c_i + \sqrt{d_i}$. Cela vaut pour toutes les directions de coordonnées$i$, ce qui implique le résultat souhaité. $\blacksquare$