sieci w odniesieniu do normy cięcia

Przeciętna norma $||A||_C$ rzeczywistej macierzy $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ jest maksimum we wszystkich $I \subseteq [n], J \subseteq [n]$ ilości $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$ .

Zdefiniuj odległość między dwiema macierzami $A$ i $B$ aby mieć wartość $d_C(A,B) = ||A-B||_C$

Jaka jest liczność najmniejszej $\epsilon$ -sieci przestrzeni metrycznej $([0,1]^{n\times n}, d_C)$ ?

tzn. rozmiar najmniejszego podzbioru $S \subset [0,1]^{n\times n}$ taki, że dla wszystkich $A \in [0,1]^{n\times n}$ istnieje $A' \in S$ taki, że $d_C(A, A') \leq \epsilon$ .

(Edycja: zapomniał wspomnieć, ale ja również zainteresowany „nie właściwego” $\epsilon$ -nets z $S \subset \mathcal{R}_+^{n\times n}$ - to znaczy jeżeli elementy $\epsilon$ -net z pozycjami poza [0,1 ], to też jest interesujące.)

Interesują mnie zarówno górne, jak i dolne granice.

Zauważ, że techniki spararyzatora cięcia wymagają $\epsilon$ -net dla wyciętych metryk, ale dają coś silniejszego niż potrzebuję - dają $\epsilon$ -net, dla którego możesz efektywnie znaleźć punkt close do dowolnej macierzy, po prostu próbkując z tej macierzy. Można sobie wyobrazić, że istnieją znacznie mniejsze sieci dla których nie można po prostu próbkować, znaleźć punkt -close do dowolnej matrycy. $\epsilon$ $\epsilon$ $\epsilon$

Początkowo zadałem to pytanie tutaj na matematycznym przepływie.

graph-theory co.combinatorics metrics max-cut epsilon-nets Aaron Roth
źródło

Ponieważ norma cięcia A jest większa lub równa wartości bezwzględnej każdego wpisu A, jasne jest, że ε-net musi mieć rozmiar co najmniej (1 / (2ε)) ^ (n ^ 2). Jaka górna granica wynika z techniki cięcia sparyfikatora? (To chyba głupie pytanie, ale nie znam tej techniki.)

Tsuyoshi Ito

Dla pewności zmieniłem pierwszą połowę poprzedniego komentarza w odpowiedź (i dodałem do niej górną granicę). Nadal interesuje mnie górna granica wynikająca z techniki cięcia sparyfikatora.

Tsuyoshi Ito,

Powyższa technika daje macierze z wpisami w

zamiast w

. Zapomniałem wspomnieć o tym w poście, ale interesują mnie również tego rodzaju okładki

{0, m | | A | |_{1}}

$\{0, m||A||_1\}$

[0, 1]

$[0,1]$

ϵ

$\epsilon$

Aaron Roth

Sieć

którą otrzymujesz z wyciętej sparsifikacji, tak naprawdę nie leży w

. Interpretuj macierz jako rozkład prawdopodobieństwa na krawędziach ukierunkowanego wykresu i próbkuj krawędzie

z tego rozkładu. Obciąż każdą krawędź o

. Za pomocą argumentów wymiaru VC (lub po prostu związku związanego z cięciami) maksymalny błąd addytywny dla dowolnego cięcia będzie wynosił

ϵ

$\epsilon$

[0, 1]^{n \times n}

$[0,1]^{n×n}$

m = \tilde{O} (n / ϵ^{2})

$m=\tilde{O}(n/\epsilon^2)$

| | A | |_{1} / m

$||A||_1/m$

O (ϵ n^{2})

$O(\epsilon n^2)$ . Dlatego oznacza to, że zestaw (odpowiednio skorygowanych) wykresami

krawędzie tworzą

-Net, który nie jest trywialne dla

n^{5} / ϵ^{2}

$n^5/\epsilon^2$

ϵ

$\epsilon$

ϵ > n^{3 / 2}

$\epsilon>n^{3/2}$

Aaron Roth

Odpowiedzi:

Oto łatwa ocena. Tutaj nazywamy zbiór S ⊆ X ε -NET z przestrzeni metrycznej X , gdy dla każdego punktu x ∈ X , to istnieje punkt y ∈ S takie, że odległość między x i y jest co najwyżej ε . Jeśli chcesz ścisłej nierówności w definicji ε- net, możesz nieznacznie podnieść wartość ε .

Trzyma to || A || _∞ ≤ || A || _C ≤ n ² || A || _∞ , gdzie || A || _∞ oznacza entrywise max-normę z n x n macierzy A .

Łatwo jest zbudować ε -net przestrzeni metrycznej ([0,1] ^N , d _∞ ) o rozmiarze ⌈1 / (2 ε ) ⌉ ^N i nietrudno wykazać, że ten rozmiar jest minimalny. (Aby pokazać minimalność, rozważ punkty ⌈1 / (2 ε ) ⌉ ^N, których współrzędne są wielokrotnościami 1 / ⌈1 / (2 ε ) −1⌉ i pokaż, że odległość między dowolnymi dwoma z tych punktów jest większa niż 2 ε .) Ustawiając N = n ² i łącząc to z wyżej wspomnianym porównaniem normy cięcia i normy maksymalnej, minimalna liczność ε-net w odniesieniu do normy cięcia wynosi co najmniej ⌈1 / (2 ε ) ⌉ ^{n ^2,} a co najwyżej ⌈ n ² / (2 ε ) ⌉ ^{n ²} .

Aktualizacja : Jeśli moje obliczenia są prawidłowe, można uzyskać lepszą dolną granicę Ω ( n / ε ) ^{n ²} za pomocą argumentu głośności. Aby to zrobić, potrzebujemy górnej granicy objętości piłki ε w odniesieniu do normy cięcia.

Najpierw rozważymy „normę cięcia” pojedynczego wektora, która jest maksimum między sumą elementów dodatnich a negowaną sumą elementów ujemnych. Nietrudno wykazać, że objętość kulki ε in with ⁿ w odniesieniu do tej „normy cięcia” jest równa

ε^{n} \sum_{ja \subseteq {1, \dots, n}} \frac{1}{| ja |!} \cdot \frac{1}{(n - | ja |)!} = ε^{n} \sum_{r = 0}^{n} (\binom{n}{r}) \frac{1}{r! (n - r)!}

$\varepsilon^n \sum_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!} = \varepsilon^n \sum_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!}$

= \frac{ε^{n}}{n!} \sum_{r = 0}^{n} {(\binom{n}{r})}^{2)} = \frac{ε^{n}}{n!} (\binom{2) n}{n}) = \frac{(2) n)! ε^{n}}{(n!)^{3)}} .

$= \frac{\varepsilon^n}{n!} \sum_{r=0}^n \binom{n}{r}^2 = \frac{\varepsilon^n}{n!} \binom{2n}{n} = \frac{(2n)!\varepsilon^n}{(n!)^3}.$

Następnie, ponieważ norma cięcia macierzy n × n A jest większa lub równa normie cięcia każdego rzędu, objętość kuli ε w ℝ ^{n × n} jest co najwyżej n- tą potęgą objętości ε -ball in ℝ ⁿ . Dlatego rozmiar sieci ε wynoszącej [0,1] ^{n × n} musi wynosić co najmniej

\frac{(n!)^{3) n}}{(2) n)!^{n} ε^{n^{2)}}} = {(Ω (\frac{n}{ε}))}^{n^{2)}},

$\frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2},$

gdzie ostatnia równość jest nudnym obliczeniem, w którym używamy wzoru Stirlinga : ln n ! = n ln n - n + O (log n ).

Tsuyoshi Ito
źródło

W odpowiedzi na edycję (wersja 4) pytania dolna granica podana w tej odpowiedzi ma również zastosowanie do „niewłaściwych” sieci ε.

Tsuyoshi Ito,

Wygląda poprawnie, ładnie zrobione!

Hsien-Chih Chang 31 之

@ Hsien-Chih: Dzięki. Najbardziej podoba mi się zastosowanie współczynników dwumianowych do obliczania objętości kuli ε w ℝ ^ n.

Tsuyoshi Ito

Podejrzewam, że dolną granicę wielkości sieci (równoważnie górną granicę objętości) można poprawić. Zadałem powiązane pytanie dotyczące MathOverflow.

Tsuyoshi Ito