Kleinster achsenausgerichteter Begrenzungsrahmen aus Hyperellipsoid
Lassen $E$ sei der $n$-dimensionales Ellipsoid definiert durch $$E:=\{x \in \mathbb{R}^n: (x-c)^T A (x-c) \le 1\},$$ wo $c \in \mathbb{R}^n$ ist das Zentrum des Ellipsoids und $A \in \mathbb{R}^{n \times n}$ ist eine symmetrische positive definitive Matrix.
Frage: Wie kann man den an der Koordinatenachse ausgerichteten Begrenzungsrahmen, der das Ellipsoid gerade noch enthält, effizient berechnen?
Ein 2D-Beispiel finden Sie im folgenden Bild:
Hinweis: Ich stelle diese Frage und beantworte sie selbst, da diese Frage (in allgemeiner Form) auch nach mehr als 10 Jahren überraschend nicht in math.stackexchange enthalten ist. Gute Antworten auf diese Frage sind im Internet im Allgemeinen schwer zu finden. Nachdem ich herumgegoogelt hatte, musste ich das schließlich selbst herausfinden und poste hier, um zukünftigen Leuten die gleichen Probleme zu ersparen. Viele Websites diskutieren die Frage im Sonderfall von$2D$ und $3D$Das Format der Ellipse wird jedoch eher in Achsen und Winkeln als in SPD-Matrizen angegeben, und die Formeln verallgemeinern sich nicht auf n-Dimensionen. Die gute Antwort gibt Achilles Hui in den Kommentaren zu der folgenden geschlossenen Frage: Bounding Box von Ellipsoid, aber dort wird kein Beweis erbracht, und die Frage ist geschlossen, so dass ich die Antwort dort nicht beweisen kann. Selbst wenn diese Frage erneut geöffnet wurde, konzentriert sie sich eher auf den 3D-Fall mit Achsen und Winkeln als auf den n-dimensionalen Fall mit SPD-Matrizen.
Antworten
Gegebener Vektor $\rm{c} \in \Bbb R^n$ und Matrix $\rm{Q} \succ \rm{O}_n$, Lassen
$$\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\}$$
Lassen $g (\rm{x}) := \left( \rm{x} - \rm{c} \right)^\top \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$. Das Vektorfeld orthogonal zur Grenze des Ellipsoids$\mathcal E$ ist
$$\nabla g (\rm{x}) = 2 \, \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$$
Lass uns wählen $i \in [n]$ und konzentrieren Sie sich auf die $i$-te Achse. Lassen$\rm{P}_i := \rm{e}_i \rm{e}_i^\top$ sei die Projektionsmatrix, die auf die projiziert $i$-te Achse. An den beiden Stellen, an denen Ellipsoid$\mathcal E$ berührt den (kleinsten) Begrenzungsrahmen, den wir haben $\rm{P}_i \nabla g (\rm{x}) = \nabla g (\rm{x})$dh
$$\left( \rm{I}_n - \rm{P}_i \right) \underbrace{ {\rm Q}^{-1} \left( \rm{x} - \rm{c} \right)}_{=: {\rm y}} = 0_n$$
Daher, $y_i$ ist kostenlos und alle anderen Einträge von $\rm y$ sind Null, dh ${\rm y} = t \, {\rm e}_i$, oder, ${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i$. Diese Linie mit der Grenze des Ellipsoids schneiden$\mathcal E$, wir erhalten
$$t^2 = \left( {\rm e}_i^\top {\rm Q} \, {\rm e}_i \right)^{-1} = q_{ii}^{-1}$$ oder, $t = \pm \frac{1}{\sqrt{q_{ii}}}$. Also Ellipsoid$\mathcal E$ berührt den (kleinsten) Begrenzungsrahmen an Punkten
$${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i = {\rm c} \pm \frac{1}{\sqrt{q_{ii}}} \, {\rm Q} \, {\rm e}_i$$
und projizieren auf die $i$-te Achse,
$$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}}$$
Daher ist der Begrenzungsrahmen ist
$$\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]}$$
Der Begrenzungsrahmen, $B$ist gegeben durch $$B = \prod_{i=1}^n\left[c_i - \sqrt{d_i}, c_i + \sqrt{d_i}\right],$$ wo $d_i$ ist der $i^\text{th}$ diagonaler Eintrag von $A^{-1}$.
Beweis:
Lassen $e_i = (0,\dots,0,1,0,\dots,0)$ sei der Vektor mit $i^\text{th}$Eintrag gleich eins und alle anderen Einträge gleich null. Das$i^\text{th}$ Koordinatendifferenz zwischen einem Punkt $x$ und der Punkt $c$ ist gegeben durch $e_i^T (x-c)$. Die Punkte auf der Oberfläche der Ellipse erfüllen$x \in \mathbb{R}^n: (x-c)^T A (x-c) = 1$. Daher der Abstand von der Mitte der Ellipse zum Begrenzungsrahmen in Richtung$i$ ist die Lösung für das folgende Optimierungsproblem: $$ \begin{aligned} \max_{x} &\quad e_i^T (x-c) \\ \text{such that}&\quad (x - c)^TA(x-c) = 1. \end{aligned} $$ Nun lass $$A^{-1} = R^TR$$ eine Faktorisierung von sein $A^{-1}$, und lass $r_i$ sei der $i^\text{th}$ Spalte von $R$. Zum Beispiel,$R$ könnte der Cholesky-Faktor sein, oder $R$ könnte sein $A^{-1/2}$, oder $R$könnte der Faktor bei jeder anderen Faktorisierung dieser Form sein. Ändern von Variablen$u := R^{-T}(x-c),$ einfache algebraische Manipulationen durchführen und die Tatsache nutzen, dass $e_i^T R^T = r_i^T$wird das Optimierungsproblem $$ \begin{aligned} \max_{u} &\quad r_i^T u \\ \text{such that}&\quad \|u\| = 1. \end{aligned} $$ Die Lösung für dieses Optimierungsproblem ist gegeben durch $u = r^i/\|r_i\|$und der optimale Wert ist $$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}.$$
Daher in der $i^\text{th}$ Richtung erstreckt sich der Begrenzungsrahmen für das Ellipsoid von $c_i - \sqrt{d_i}$ zu $c_i + \sqrt{d_i}$. Dies gilt für alle Koordinatenrichtungen$i$, was das gewünschte Ergebnis impliziert. $\blacksquare$