Wypukły korpus z minimalną oczekiwaną normą l2

Rozważmy wypukłe ciało wyśrodkowane na początku i symetryczne (tj. Jeśli to ). Chcę znaleźć inne ciało wypukłe tak aby i następująca miara zostały zminimalizowane: $K$ $x\in K$ $-x\in K$ $L$ $K\subseteq L$

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$ , gdzie jest punktem losowo wybranym losowo z L. $x$

Nic mi nie jest ze stałym przybliżeniem współczynnika do miary.

Kilka uwag - Pierwsze intuicyjne przypuszczenie, że sama jest odpowiedzią, jest złe. Na przykład należy uważać za cienki cylinder o bardzo dużych wymiarach. Następnie możemy uzyskać tak, że , pozwalając mieć większą objętość zbliżoną do źródła. $K$ $K$ $L$ $f(L)<f(K)$ $L$

cg.comp-geom approximation convex-geometry

— Ashwinkumar BV
źródło

Mimo że nic nie jest warte, problem wygląda na trudny. Nawet w 3D nie jest oczywiste, jak to rozwiązać.

— Sariel Har-Peled

Czy to oczywiste, jak zrobić to optymalnie w 2D? Oczywiście w 2d stałe przybliżenie współczynnika jest nieciekawe.

— Ashwinkumar BV

To nie jest dla mnie oczywiste. Przybliżenie współczynnika stałego jest oczywiste w każdym wymiarze poprzez przybliżenie kształtu przez elipsoidę www.math.sc.edu/~howard/Notes/john.pdf. Stała zależałaby od wymiaru.

— Sariel Har-Peled

Bardziej interesuje mnie przybliżenie współczynnika stałego, gdy stała nie zależy od wymiaru.

— Ashwinkumar BV

Naturalnie. Ale pozwolę sobie to cofnąć - nawet obudowa elipsoidy nie jest oczywista. Jeśli chcesz zaatakować ten problem, byłaby to pierwsza wersja do zbadania. Intuicyjnie musisz zdecydować, które wymiary zignorować, a które rozszerzyć. Wydaje się, że naturalnym rozwiązaniem jest wypukły kadłub połączenia elipsoidy z inną elipsoidą, gdzie osie nowej elipsoidy są albo równe jakiemuś parametrowi r, albo są równe drugiej elipsoidzie.

— Sariel Har-Peled

Odpowiedzi:

Jeśli ograniczymy i do obu elipsoid, problem można rozwiązać z dowolną dokładnością za pomocą SDP. Wiem, że nie o to pytałeś pierwotnie, ale wydaje się, że nie mamy rozwiązania nawet w tej ograniczonej sprawie i być może może to w ogóle pomóc. $K$ $L$

Więc powiedzmy, że jest elipsoida wejście i szukamy aby znaleźć optymalną otaczającą elipsoidy . Istnieje mapa liniowa st i mapa st , gdzie jest kulą jednostkową. Następnie . Ponadto , gdzie jest korpus polarny z . Dogodnie i . Wynika, że $E$ $J$ $F$ $E = FB_2$ $G$ $J = GB_2$ $B_2$ $\mathbb{E}_{x \sim J}[\|x\|_2^2] = \frac{1}{n}\mathsf{Tr}(G^TG)$ $E \subseteq J \Leftrightarrow J^\circ \subseteq E^\circ$ $E^\circ$ $E$ $E^\circ = \{x: x^TF^TFx \leq 1\}$ $J^\circ = \{x: x^TG^TGx \leq 1\}$ $J^\circ \subseteq E^\circ$ (a zatem ) wtedy i tylko wtedy, gdy jest dodatnią macierzą półfinałową. $E \subseteq J$ $G^TG - F^TF$

Zatem SDP jest zdefiniowany przez: biorąc pod uwagę symetryczną macierz PSD , znajdź symetryczną macierz PSD st oznacza PSD i jest zminimalizowane. można znaleźć rozwiązując SDP i wówczas SVD da osi i osi długości . $M$ $N$ $N - M$ $\mathsf{Tr}(N)$ $N$ $J$

— Sasho Nikolov
źródło

(Jak wspomniano w komentarzach, następujące podejście nie działa. Uzyskany obiekt nie jest wypukły. Charakteryzuje on obiekt w kształcie gwiazdy o minimalnej oczekiwanej odległości.)

Myślę, że optymalnym obiektem byłoby połączenie i trochę piłki wycentrowanej na początku. Oto moje przemyślenia. Według twojej definicji , gdzie to odległość od początku do powierzchni wzdłuż określonego kierunku. Użyłem zamiast =, ponieważ upuściłem niektóre stałe. Teraz chcemy zminimalizować pod ograniczeniami, które $K$ $f(L)$

f (L) \sim \int_{S^{d - 1}} \int_{0}^{r_{L}} x \frac{d (x^{d} / x_{L}^{d})}{d x} \frac{r_{L}}{v o l (L)} d x d S \sim \int_{S^{d - 1}} \frac{r_{L}^{2}}{v o l (L)} d S \sim \frac{\int_{S^{d - 1}} r_{L}^{2} d S}{\int_{S^{d - 1}} r_{L} d S} \overset{d e f}{=} g (L),

$f(L) \sim \int_{{\mathbb S}^{d-1}} \int_{0}^{r_L} x\frac{\mathrm{d}(x^d/x_L^d)}{\mathrm dx}\frac{r_L}{\mathrm{vol}(L)} \mathrm dx\mathrm dS \sim \int_{{\mathbb S}^{d-1}} \frac{r_L^2}{\mathrm{vol}(L)}dS \sim \frac{\int_{{\mathbb S}^{d-1}} r_L^2 dS}{\int_{{\mathbb S}^{d-1}} r_L dS} \stackrel{\mathrm{def}}{=} g(L),$

r_{L}

$r_L$

L

$L$

\sim

$\sim$

g (L)

$g(L)$

r_{L} \geq r_{K}

$r_L \ge r_K$ wzdłuż dowolnego kierunku. Zauważ, że jeśli wzdłuż jakiegoś kierunku jest mniejszy niż , możemy go nieco zwiększyć, powiedzmy, zwiększ go o , aby . Jest tak, ponieważ zwiększamy wyliczający o , mniej niż współczynnik wzrostu mianownika. Dlatego możemy myśleć o stopniowym „deformowaniu” (poprzez kilkakrotne nieznaczne powiększanie obiektu i aktualizowanie ), aby zmniejszyć jego wartość . Niech będzie na końcu obiektem wypukłym. Następnie w dowolnym momencie

r_{K}

$r_K$

g (K) / 2

$g(K)/2$

ϵ \leq g (K) / 2 - r_{K}

$\epsilon \le g(K)/2 -r_K$

g (K)

$g(K)$

(r_{L} + ϵ)^{2} - r_{L}^{2} = ϵ (2 r_{L} + ϵ)

$(r_L+\epsilon)^2 -r_L^2 = \epsilon(2r_L + \epsilon)$

g (K)

$g(K)$

K

$K$

g (\cdot)

$g(\cdot)$

g (\cdot)

$g(\cdot)$

K^{*}

$K^*$

\partial K^{*} ∖ \partial K

$\partial K^*\setminus \partial K$ znajduje się w odległości od początku, tj. to suma i piłki o promieniu .

g (K^{*}) / 2

$g(K^*)/2$

K^{*}

$K^*$

K

$K$

g (K^{*}) / 2

$g(K^*)/2$

Rzeczywiście, rozważ inny wypukły obiekt taki, że . Następnie , ponieważ w przeciwnym razie możemy zwiększyć część wewnątrz aby zmniejszyć . Z drugiej strony, , ponieważ w innym przypadku, według tego samego pomysłu, możemy zmniejszyć część poza aby zmniejszyć . Istnieje więc unikalne optymalne rozwiązanie. $K'$ $g(K') = g(K)$ $K^*\subseteq K'$ $K'$ $K^*$ $g(K')$ $K'\subseteq K^*$ $K'\setminus K$ $K^*$ $g(K')$

— użytkownik7852
źródło

Może czegoś mi brakuje, ale dlaczego obiekt jest w ten sposób wypukły?

— mjqxxxx,

@mjqxxxx Masz rację. Jak mi tego brakowało ...

— user7852

A co z następującym pomysłem: dobrze wiadomo, że wypukły obiekt może być aproksymowany przez jakąś elipsoidę, tj. Istnieje elipsoida taka, że . Następnie aproksymuje o przybliżonym stosunku . Dla dowolnego zawierającego , . Jeśli więc znajdziemy optymalną elipsoidę zawierającą , to . Nie wiem, jak obliczyć . Ale zgaduję, że jego osie są wyrównane z osiami i wszystkimi wartościami własnymi

E_{K}

$E_K$

E_{K} \subseteq K \subseteq \sqrt{d} E_{K}

$E_K\subseteq K\subseteq \sqrt{d}E_K$

f (\sqrt{d} E_{K})

$f(\sqrt{d} E_K)$

f (K)

$f(K)$

d

$d$

L

$L$

K

$K$

\sqrt{d} E_{K} \subseteq d E_{L}

$\sqrt{d}E_K \subseteq d E_L$

E

$E$

\sqrt{d} E_{K}

$\sqrt{d} E_K$

f (E) \leq d^{2} f (L)

$f(E) \le d^2 f(L)$

E

$E$

\sqrt{d} E_{K}

$\sqrt{d} E_K$

\sqrt{d} E_{K}

$\sqrt{d} E_K$ poniżej pewnego progu jest podnoszony do tego progu.

— user7852

Zgadzam się, że jeśli L nie jest ograniczony do ciała wypukłego, to jest to połączenie K i piłki.

— Ashwinkumar BV

Pomysł użycia elipsoidy nie da ci stałego czynnika. W najlepszym wypadku może dać przybliżenie . Moje przypuszczenie jest takie, że wypukły kadłub z kulą o odpowiednim promieniu jest stałym przybliżeniem współczynnika. Nie jestem pewien, jak udowodnić lub obalić przypuszczenie.

\sqrt{d}

$\sqrt{d}$

L

$L$

— Ashwinkumar BV

Poniższe rozwiązanie opiera się na założeniu / przypuszczeniu [do udowodnienia]:

Przypuszczenie : oczekiwanie funkcji wypukłej na jest mniejsze niż większe między oczekiwaniem na i oczekiwaniem na . $\textrm{conv}(K\bigcup K')$ $K$ $K'$

[Będziemy potrzebować powyższego tylko dla wypukłych , ale może to być prawda] $K,K'$

Weź teraz dowolny zestaw i zastosuj do niego obrót wyśrodkowany na początku, uzyskując . Będziesz miał , ponieważ obrót pozostawia długość elementów niezmiennikaJeśli mam rację co do przypuszczenia, . Ponieważ dla każdego optymalnego można rozważyć , gdzie oznacza we wszystkich obrotach i ma , wydaje się, że optymalne można wybrać jako najmniejszą kulę zawierającą $K$ $R$ $R(K)$ $f(K)=f(R(K))$ $K$ $f(\textrm{conv}(K\bigcup R(K)))\leq f(K)$ $L$ $L'=\bigcup_R R(L)=\textrm{conv}(\bigcup_R R(L))$ $\bigcup_R$ $f(L)\geq f(L') \geq f(L)$ $L$ $K$ .

— Marco
źródło

Wystarczy udowodnić, że na oczekiwanie funkcji wypukłej. To, że wydaje się łatwe.

E_{conv (A)} \leq E_{A}

$\mathbb{E}_{\textrm{conv}(A)}\leq \mathbb{E}_{A}$

E_{K ⋃ K^{'}} \leq max {E_{K}, E_{K}^{'}}

$\mathbb{E}_{K\bigcup K'}\leq \max\{\mathbb{E}_K,\mathbb{E}_K'\}$

— Marco

Nie jestem do końca pewien, czy otrzymam twoją odpowiedź. Ale zdecydowanie nie jest prawdą, że L można wybrać jako najmniejszą kulę zawierającą K. Rozważ długi cienki walec o wymiarach długości . Wtedy każda kula zawierająca powinna mieć . Ale jeśli gdzie U jest kulą lub promieniem mniej więcej , otrzymasz grubsza . (gdzie są stałymi)

d

$d$

t

$t$

S

$S$

K

$K$

f (S) \geq t

$f(S)\geq t$

L = c o n v (K \cup U)

$L=conv(K\cup U)$

c_{1} t / d

$c_1 t/d$

f (L)

$f(L)$

c_{2} t / d

$c_2 t/d$

c_{1}, c_{2}

$c_1,c_2$

— Ashwinkumar BV