ハイパー楕円体の最小の軸整列バウンディングボックス
しましょう $E$ である $n$-によって定義される次元楕円体 $$E:=\{x \in \mathbb{R}^n: (x-c)^T A (x-c) \le 1\},$$ どこ $c \in \mathbb{R}^n$ は楕円体の中心であり、 $A \in \mathbb{R}^{n \times n}$ は対称正定行列です。
質問：楕円体をほとんど含まない座標軸に揃えられたバウンディングボックスを効率的に計算するにはどうすればよいですか？
2Dの例については、次の図を参照してください。
注：私はこの質問をし、自分で答えます。この質問（一般的な形式）は、10年以上経ってもmath.stackexchangeに驚くほど存在しないためです。この質問に対する良い答えは、インターネット上でより一般的に見つけるのは難しいです。グーグルした後、私は最終的にこれを自分で理解する必要があり、将来の人々に同じ問題を回避するためにここに投稿しています。多くのウェブサイトは、特別な場合の質問について話し合っています$2D$ そして $3D$、ただし、楕円の形式はSPD行列ではなく軸と角度で示され、式はn次元に一般化されません。良い答えは、次の閉じた質問へのコメントでachilles huiによって与えられます：楕円体のバウンディングボックスがそこに証明が提供されておらず、質問が閉じられているため、そこで証明を提供することはできません。その質問が再開されたとしても、SPD行列を使用したn次元の場合ではなく、軸と角度を使用した3Dの場合に焦点が当てられます。
回答
与えられたベクトル $\rm{c} \in \Bbb R^n$ およびマトリックス $\rm{Q} \succ \rm{O}_n$、
$$\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\}$$
しましょう $g (\rm{x}) := \left( \rm{x} - \rm{c} \right)^\top \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$。楕円体の境界に直交するベクトル場$\mathcal E$ です
$$\nabla g (\rm{x}) = 2 \, \rm{Q}^{-1} \left( \rm{x} - \rm{c} \right)$$
選びましょう $i \in [n]$ に焦点を当てる $i$-番目の軸。しましょう$\rm{P}_i := \rm{e}_i \rm{e}_i^\top$ に射影する射影行列である $i$-番目の軸。楕円体がある2点で$\mathcal E$ （最小の）バウンディングボックスに触れると、 $\rm{P}_i \nabla g (\rm{x}) = \nabla g (\rm{x})$、すなわち、
$$\left( \rm{I}_n - \rm{P}_i \right) \underbrace{ {\rm Q}^{-1} \left( \rm{x} - \rm{c} \right)}_{=: {\rm y}} = 0_n$$
したがって、 $y_i$ は無料で、他のすべてのエントリは $\rm y$ ゼロ、つまり ${\rm y} = t \, {\rm e}_i$、または、 ${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i$。この線を楕円体の境界と交差させる$\mathcal E$、 私達は手に入れました
$$t^2 = \left( {\rm e}_i^\top {\rm Q} \, {\rm e}_i \right)^{-1} = q_{ii}^{-1}$$ または、 $t = \pm \frac{1}{\sqrt{q_{ii}}}$。したがって、楕円体$\mathcal E$ ポイントで（最小の）境界ボックスに触れます
$${\rm x} = {\rm c} + t \, {\rm Q} \, {\rm e}_i = {\rm c} \pm \frac{1}{\sqrt{q_{ii}}} \, {\rm Q} \, {\rm e}_i$$
そして、に投影する $i$-番目の軸、
$$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}}$$
したがって、バウンディングボックスは
$$\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]}$$
バウンディングボックス、 $B$、 によって与えられます $$B = \prod_{i=1}^n\left[c_i - \sqrt{d_i}, c_i + \sqrt{d_i}\right],$$ どこ $d_i$ それは $i^\text{th}$ の対角線エントリ $A^{-1}$。
証明：
しましょう $e_i = (0,\dots,0,1,0,\dots,0)$ とのベクトルである $i^\text{th}$エントリが1に等しく、他のすべてのエントリがゼロに等しい。ザ・$i^\text{th}$ ポイント間の座標差 $x$ そしてポイント $c$ によって与えられます $e_i^T (x-c)$。楕円の表面上の点は$x \in \mathbb{R}^n: (x-c)^T A (x-c) = 1$。したがって、楕円の中心からバウンディングボックスまでの方向の距離$i$ 次の最適化問題の解決策です。 $$ \begin{aligned} \max_{x} &\quad e_i^T (x-c) \\ \text{such that}&\quad (x - c)^TA(x-c) = 1. \end{aligned} $$ さあ、 $$A^{-1} = R^TR$$ の因数分解である $A^{-1}$、そして $r_i$ である $i^\text{th}$ の列 $R$。例えば、$R$ コレスキー因子である可能性があります、または $R$ になり得る $A^{-1/2}$、または $R$この形式の他の因数分解の要因になる可能性があります。変数変換を行う$u := R^{-T}(x-c),$ 単純な代数操作を実行し、 $e_i^T R^T = r_i^T$、最適化問題は $$ \begin{aligned} \max_{u} &\quad r_i^T u \\ \text{such that}&\quad \|u\| = 1. \end{aligned} $$ この最適化問題の解決策は次のように与えられます。 $u = r^i/\|r_i\|$、および最適値は $$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}.$$
したがって、 $i^\text{th}$ 方向、楕円体のバウンディングボックスは $c_i - \sqrt{d_i}$ に $c_i + \sqrt{d_i}$。これはすべての座標方向に当てはまります$i$、これは望ましい結果を意味します。 $\blacksquare$