Najmniejszy prostokąt ograniczający wyrównany do osi hiperelipsoidy
Pozwolić $E$ być $n$-wymiarowa elipsoida zdefiniowana przez $$E:=\{x \in \mathbb{R}^n: (x-c)^T A (x-c) \le 1\},$$ gdzie $c \in \mathbb{R}^n$ jest środkiem elipsoidy, a $A \in \mathbb{R}^{n \times n}$ jest symetryczną dodatnią określoną macierzą.
Pytanie: Jak skutecznie obliczyć prostokąt ograniczający wyrównany do osi współrzędnych, który ledwo zawiera elipsoidę?
Aby zapoznać się z przykładem 2D, zobacz następujący obraz:
Uwaga: zadaję to pytanie i sam na nie odpowiadam, ponieważ to pytanie (w ogólnej formie) jest zaskakująco nieobecne w math.stackexchange nawet po ponad 10 latach. Ogólnie rzecz biorąc, w internecie trudno znaleźć dobre odpowiedzi na to pytanie. Po wygooglowaniu musiałem w końcu sam to rozgryźć i publikuję tutaj, aby oszczędzić przyszłym ludziom tego samego kłopotu. Wiele witryn omawia tę kwestię w specjalnym przypadku$2D$ i $3D$, ale format elipsy jest podany w postaci osi i kątów, a nie macierzy SPD, a wzory nie uogólniają na n-wymiary. Dobrej odpowiedzi udziela Achilles hui w komentarzach do następującego pytania zamkniętego: Bounding box of Ellipsoid, ale nie ma tam żadnego dowodu, a pytanie jest zamknięte, więc nie mogę podać odpowiedzi z dowodem. Nawet gdyby to pytanie zostało ponownie otwarte, koncentruje się na przypadku 3D z osiami i kątami, a nie na przypadku n-wymiarowym z matrycami SPD.
Odpowiedzi
Dany wektor $\rm{c} \in \Bbb R^n$ i macierz $\rm{Q} \succ \rm{O}_n$, pozwolić
$$\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\}$$
Pozwolić $g (\rm{x}) := \left( \rm{x} - \rm{c} \right)^\top \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$. Pole wektorowe prostopadłe do granicy elipsoidy$\mathcal E$ jest
$$\nabla g (\rm{x}) = 2 \, \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$$
Wybierzmy $i \in [n]$ i skup się na $i$-ta oś. Pozwolić$\rm{P}_i := \rm{e}_i \rm{e}_i^\top$ być macierzą projekcji, która rzutuje na $i$-ta oś. W dwóch punktach, gdzie elipsoida$\mathcal E$ dotyka (najmniejszej) obwiedni, którą mamy $\rm{P}_i \nabla g (\rm{x}) = \nabla g (\rm{x})$tj.
$$\left( \rm{I}_n - \rm{P}_i \right) \underbrace{ {\rm Q}^{-1} \left( \rm{x} - \rm{c} \right)}_{=: {\rm y}} = 0_n$$
W związku z tym, $y_i$ jest bezpłatny, a wszystkie inne wpisy $\rm y$ są równe zero, tj. ${\rm y} = t \, {\rm e}_i$lub ${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i$. Przecięcie tej linii z granicą elipsoidy$\mathcal E$, otrzymujemy
$$t^2 = \left( {\rm e}_i^\top {\rm Q} \, {\rm e}_i \right)^{-1} = q_{ii}^{-1}$$ lub, $t = \pm \frac{1}{\sqrt{q_{ii}}}$. Zatem elipsoida$\mathcal E$ dotyka (najmniejszej) obwiedni w punktach
$${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i = {\rm c} \pm \frac{1}{\sqrt{q_{ii}}} \, {\rm Q} \, {\rm e}_i$$
i, rzutując na $i$-ta oś,
$$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}}$$
Stąd ramką graniczną jest
$$\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]}$$
Obwiednia, $B$, jest dany przez $$B = \prod_{i=1}^n\left[c_i - \sqrt{d_i}, c_i + \sqrt{d_i}\right],$$ gdzie $d_i$ jest $i^\text{th}$ ukośne wejście $A^{-1}$.
Dowód:
Pozwolić $e_i = (0,\dots,0,1,0,\dots,0)$ być wektorem z $i^\text{th}$wpis równy jeden, a wszystkie inne wpisy równe zero. Plik$i^\text{th}$ różnica współrzędnych między punktem $x$ i o co chodzi $c$ jest dany przez $e_i^T (x-c)$. Punkty na powierzchni elipsy spełniają$x \in \mathbb{R}^n: (x-c)^T A (x-c) = 1$. Dlatego odległość od środka elipsy do prostokąta ograniczającego w kierunku$i$ jest rozwiązaniem następującego problemu optymalizacji: $$ \begin{aligned} \max_{x} &\quad e_i^T (x-c) \\ \text{such that}&\quad (x - c)^TA(x-c) = 1. \end{aligned} $$ Teraz pozwól $$A^{-1} = R^TR$$ być faktoryzacją $A^{-1}$, i pozwól $r_i$ być $i^\text{th}$ kolumna $R$. Na przykład,$R$ może być czynnikiem Choleskiego, lub $R$ możliwe $A^{-1/2}$lub $R$może być czynnikiem w każdej innej faktoryzacji tej postaci. Dokonywanie zmiany zmiennych$u := R^{-T}(x-c),$ wykonując proste manipulacje algebraiczne i korzystając z tego faktu $e_i^T R^T = r_i^T$pojawia się problem optymalizacji $$ \begin{aligned} \max_{u} &\quad r_i^T u \\ \text{such that}&\quad \|u\| = 1. \end{aligned} $$ Rozwiązanie tego problemu optymalizacji podaje $u = r^i/\|r_i\|$, a optymalna wartość to $$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}.$$
Dlatego w $i^\text{th}$ kierunku, obwiednia elipsoidy rozciąga się od $c_i - \sqrt{d_i}$ do $c_i + \sqrt{d_i}$. Dotyczy to wszystkich kierunków współrzędnych$i$, co implikuje pożądany rezultat. $\blacksquare$