Kotak pembatas selaras sumbu terkecil dari hyper-ellipsoid
Membiarkan $E$ jadilah $n$elipsoid berdimensi yang ditentukan oleh $$E:=\{x \in \mathbb{R}^n: (x-c)^T A (x-c) \le 1\},$$ dimana $c \in \mathbb{R}^n$ adalah pusat ellipsoid, dan $A \in \mathbb{R}^{n \times n}$ adalah matriks pasti positif simetris.
Pertanyaan: Bagaimana cara menghitung kotak pembatas selaras-sumbu koordinat yang hampir tidak berisi ellipsoid?
Untuk contoh 2D, lihat gambar berikut:
Catatan: Saya mengajukan pertanyaan ini, dan menjawabnya sendiri, karena pertanyaan ini (dalam bentuk umum) secara mengejutkan tidak ada dalam math.stackexchange bahkan setelah 10+ tahun. Jawaban yang baik untuk pertanyaan ini sulit ditemukan di internet secara umum. Setelah mencari-cari di Google, saya akhirnya harus mencari tahu sendiri, dan memposting di sini untuk menghindarkan orang-orang di masa depan dari masalah yang sama. Banyak situs web membahas pertanyaan dalam kasus khusus$2D$ dan $3D$, tetapi format elips diberikan dalam bentuk sumbu dan sudut daripada matriks SPD, dan rumus tidak digeneralisasikan ke dimensi-n. Jawaban yang baik diberikan oleh achilles hui dalam komentar untuk pertanyaan tertutup berikut ini: Kotak pembatas dari Ellipsoid tetapi tidak ada bukti yang diberikan di sana, dan pertanyaannya ditutup sehingga saya tidak dapat memberikan jawaban dengan bukti di sana. Bahkan jika pertanyaan itu dibuka kembali, ini difokuskan pada kasus 3D dengan sumbu dan sudut daripada kasus n-dimensi dengan matriks SPD.
Jawaban
Diberikan vektor $\rm{c} \in \Bbb R^n$ dan matriks $\rm{Q} \succ \rm{O}_n$, biarkan
$$\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\}$$
Membiarkan $g (\rm{x}) := \left( \rm{x} - \rm{c} \right)^\top \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$. Bidang vektor ortogonal ke batas ellipsoid$\mathcal E$ adalah
$$\nabla g (\rm{x}) = 2 \, \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$$
Mari kita pilih $i \in [n]$ dan fokus pada $i$sumbu ke-. Membiarkan$\rm{P}_i := \rm{e}_i \rm{e}_i^\top$ menjadi matriks proyeksi yang memproyeksikan ke $i$sumbu ke-. Di dua titik di mana ellipsoid$\mathcal E$ menyentuh kotak pembatas (terkecil), yang kami miliki $\rm{P}_i \nabla g (\rm{x}) = \nabla g (\rm{x})$, yaitu,
$$\left( \rm{I}_n - \rm{P}_i \right) \underbrace{ {\rm Q}^{-1} \left( \rm{x} - \rm{c} \right)}_{=: {\rm y}} = 0_n$$
Karenanya, $y_i$ gratis dan semua entri lainnya dari $\rm y$ adalah nol, yaitu, ${\rm y} = t \, {\rm e}_i$, atau, ${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i$. Memotong garis ini dengan batas ellipsoid$\mathcal E$, kami dapatkan
$$t^2 = \left( {\rm e}_i^\top {\rm Q} \, {\rm e}_i \right)^{-1} = q_{ii}^{-1}$$ atau, $t = \pm \frac{1}{\sqrt{q_{ii}}}$. Jadi, ellipsoid$\mathcal E$ menyentuh kotak pembatas (terkecil) di beberapa titik
$${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i = {\rm c} \pm \frac{1}{\sqrt{q_{ii}}} \, {\rm Q} \, {\rm e}_i$$
dan, memproyeksikan ke $i$sumbu ke-,
$$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}}$$
Oleh karena itu, kotak pembatas adalah
$$\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]}$$
Kotak pembatas, $B$, diberikan oleh $$B = \prod_{i=1}^n\left[c_i - \sqrt{d_i}, c_i + \sqrt{d_i}\right],$$ dimana $d_i$ adalah $i^\text{th}$ entri diagonal $A^{-1}$.
Bukti:
Membiarkan $e_i = (0,\dots,0,1,0,\dots,0)$ menjadi vektor dengan $i^\text{th}$entri sama dengan satu, dan semua entri lainnya sama dengan nol. Itu$i^\text{th}$ mengoordinasikan perbedaan antara satu titik $x$ dan intinya $c$ diberikan oleh $e_i^T (x-c)$. Titik-titik di permukaan elips memenuhi$x \in \mathbb{R}^n: (x-c)^T A (x-c) = 1$. Oleh karena itu, jarak dari pusat elips ke kotak pembatas searah$i$ adalah solusi untuk masalah pengoptimalan berikut: $$ \begin{aligned} \max_{x} &\quad e_i^T (x-c) \\ \text{such that}&\quad (x - c)^TA(x-c) = 1. \end{aligned} $$ Sekarang biarkan $$A^{-1} = R^TR$$ menjadi faktorisasi $A^{-1}$, dan biarkan $r_i$ jadilah $i^\text{th}$ kolom $R$. Sebagai contoh,$R$ bisa menjadi faktor Cholesky, atau $R$ bisa jadi $A^{-1/2}$, atau $R$dapat menjadi faktor dalam faktorisasi lain dari bentuk ini. Melakukan perubahan variabel$u := R^{-T}(x-c),$ melakukan manipulasi aljabar sederhana, dan menggunakan fakta itu $e_i^T R^T = r_i^T$, masalah pengoptimalan menjadi $$ \begin{aligned} \max_{u} &\quad r_i^T u \\ \text{such that}&\quad \|u\| = 1. \end{aligned} $$ Solusi untuk masalah pengoptimalan ini diberikan oleh $u = r^i/\|r_i\|$, dan nilai optimal adalah $$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}.$$
Oleh karena itu, di $i^\text{th}$ arah, kotak pembatas untuk ellipsoid memanjang dari $c_i - \sqrt{d_i}$ untuk $c_i + \sqrt{d_i}$. Ini berlaku untuk semua arah koordinat$i$, yang menyiratkan hasil yang diinginkan. $\blacksquare$