-jala sehubungan dengan norma pemotongan

Norma pemotongan $||A||_C$ dari matriks nyata $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ adalah maksimum dari semua $I \subseteq [n], J \subseteq [n]$ dari kuantitas $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$ .

Tentukan jarak antara dua matriks $A$ dan $B$ menjadi $d_C(A,B) = ||A-B||_C$

Berapakah kardinalitas $\epsilon$ -net terkecil dari ruang metrik $([0,1]^{n\times n}, d_C)$ ?

yaitu ukuran subset terkecil $S \subset [0,1]^{n\times n}$ sedemikian rupa sehingga untuk semua $A \in [0,1]^{n\times n}$ , terdapat $A' \in S$ sedemikian rupa sehingga $d_C(A, A') \leq \epsilon$ .

(EDIT: Saya lupa lagi, tapi saya juga tertarik pada "non-benar" $\epsilon$ -nets, dengan $S \subset \mathcal{R}_+^{n\times n}$ - yaitu jika unsur-unsur $\epsilon$ -net memiliki entri di luar [0,1 ], itu juga menarik.)

Saya tertarik pada batas atas dan batas bawah.

Perhatikan bahwa teknik cut sparsifier menyiratkan -net untuk cut metrics, tetapi berikan sesuatu yang lebih kuat dari yang saya butuhkan - mereka memberikan -net yang Anda dapat menemukan titik -cose ke matriks apa pun secara efisien hanya dengan mengambil sampel dari matriks tersebut. Orang mungkin membayangkan bahwa terdapat jauh lebih kecil -nets yang Anda tidak bisa hanya sampel do menemukan titik-dekat dengan matriks sewenang-wenang. $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$

Saya awalnya mengajukan pertanyaan ini di sini di mathoverflow.

graph-theory co.combinatorics metrics max-cut epsilon-nets Aaron Roth
sumber

Karena norma pemotongan A lebih besar atau sama dengan nilai absolut dari setiap entri A, jelas bahwa ε-net harus memiliki ukuran setidaknya (1 / (2ε)) ^ (n ^ 2). Apa batas atas yang diperoleh dari teknik cut sparsifier? (Ini mungkin pertanyaan bodoh, tapi saya tidak tahu teknik itu.)

Tsuyoshi Ito

Hanya untuk memastikan, saya mengubah bagian pertama dari komentar saya sebelumnya menjadi jawaban (dan menambahkan batas atas). Saya masih tertarik pada batas atas yang berasal dari teknik sparsifier cut.

Tsuyoshi Ito

Teknik di atas menghasilkan matriks dengan entri dalam

daripada di

. Saya lupa menyebutkannya di posting, tapi saya juga tertarik pada

-cover semacam ini.

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

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

[0, 1]

$[0,1]$

ϵ

$\epsilon$

Aaron Roth

The

-net Anda dapatkan dari cut sparsification tidak benar-benar terletak pada

. Menginterpretasikan matriks sebagai distribusi probabilitas pada tepi grafik berarah, dan sampel

tepi dari distribusi. Bobot masing-masing tepi dengan

. Dengan argumen dimensi-VC (atau hanya ikatan yang terikat pada pemotongan), kesalahan aditif maksimum pada setiap pemotongan akan whp menjadi

ϵ

$\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)$ . Jadi ini berarti bahwa bahwa himpunan grafik (tepat tertimbang) pada

tepi membentuk

-net, yang merupakan non-sepele untuk

n^{5} / ϵ^{2}

$n^5/\epsilon^2$

ϵ

$\epsilon$

ϵ > n^{3 / 2}

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

Aaron Roth

Jawaban:

Berikut ini perkiraan yang mudah. Di sini kita sebut satu set S ⊆ X merupakan ε -net dari ruang metrik X saat untuk setiap titik x ∈ X , terdapat titik s ∈ S sehingga jarak antara x dan s adalah paling ε . Jika Anda menginginkan ketimpangan yang ketat dalam definisi ε -net, Anda dapat mengubah sedikit nilai ε .

Ini menyatakan bahwa || A || _∞ ≤ || A || _C ≤ n ² || A || _∞ , di mana || A || _∞ menunjukkan entrywise max-norma dari n × n matriks A .

Mudah untuk membangun ε -net dari ruang metrik ([0,1] ^N , d _∞ ) dengan ukuran ⌈1 / (2 ε ) ⌉ ^N , dan tidak sulit untuk menunjukkan bahwa ukuran ini adalah minimum. (Untuk menunjukkan minimal, pertimbangkan ⌈1 / (2 ε ) ⌉ ^N titik yang koordinatnya adalah kelipatan 1 / ⌈1 / (2 ε ) −1⌉ dan tunjukkan bahwa jarak antara dua titik ini lebih besar dari 2 ε .) Dengan menetapkan N = n ² dan menggabungkan ini dengan perbandingan yang disebutkan sebelumnya antara norma potong dan norma-maks, kardinalitas minimum ε-net sehubungan dengan norma cut setidaknya ⌈1 / (2 ε ) ⌉ ^{n ²} dan paling banyak ⌈ n ² / (2 ε ) ⌉ ^{n ²} .

Pembaruan : Jika perhitungan saya benar, batas bawah yang lebih baik Ω ( n / ε ) ^{n ²} dapat diperoleh dengan argumen volume. Untuk melakukan ini, kita memerlukan batas atas pada volume bola- ε sehubungan dengan norma pemotongan.

Pertama kita mempertimbangkan "cut norm" dari satu vektor, yang merupakan maksimum antara jumlah elemen positif dan jumlah elemen negatif yang dinegasikan. Tidak sulit untuk menunjukkan bahwa volume bola- ε dalam ℝ ⁿ sehubungan dengan "norma pemotongan" ini sama dengan

ε^{n} \sum_{I \subseteq {1, \dots, n}} \frac{1}{| I |!} \cdot \frac{1}{(n - | I |)!} = ε^{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}.$

Selanjutnya, karena norma potong dari n × n matriks A lebih besar dari atau sama dengan norma potong setiap baris, volume bola- ε dalam ℝ ^{n × n} paling banyak adalah kekuatan ke- n dari volume volume suatu ε -bola di ℝ ⁿ . Oleh karena itu ukuran ε -net [0,1] ^{n × n} harus setidaknya

\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},$

di mana persamaan terakhir adalah perhitungan yang membosankan di mana kami menggunakan rumus Stirling : ln n ! = n ln n - n + O (log n ).

Tsuyoshi Ito
sumber

Menanggapi hasil edit (revisi 4) dari pertanyaan, batas bawah yang dinyatakan dalam jawaban ini juga berlaku untuk jaring ε “tidak layak”.

Tsuyoshi Ito

Terlihat benar, bagus sekali!

Hsien-Chih Chang 張顯之

@ Hsien-Chih: Terima kasih. Bagian yang paling saya sukai adalah penggunaan koefisien binomial dalam perhitungan volume bola ε dalam ℝ ^ n.

Tsuyoshi Ito

Saya menduga bahwa batas bawah pada ukuran jaring (ekuivalen, batas atas volume) dapat ditingkatkan. Saya mengajukan pertanyaan terkait pada MathOverflow.

Tsuyoshi Ito