초 타원체의 축으로 정렬 된 가장 작은 경계 상자

Nov 28 2020

허락하다 $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에 의해 제공됩니다. Ellipsoid의 경계 상자 이지만 거기에 증거가 제공되지 않았고 질문 이 닫혀서 거기에 증거를 제공 할 수 없습니다. 이 질문이 다시 열리더라도 SPD 행렬의 n 차원 사례보다는 축과 각도가있는 3D 사례에 초점을 맞추고 있습니다.

답변

2 RodrigodeAzevedo Nov 30 2020 at 15:48

주어진 벡터 $\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$-번째 축. 타원체가있는 두 지점에서$\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$ 즉, 0입니다. ${\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]}$$

1 NickAlger Nov 28 2020 at 23:57

경계 상자, $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이고 다른 모든 항목은 0입니다. 그만큼$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$