Netze in Bezug auf die Schnittnorm

10

Die Schnittnorm ||A||C einer reellen Matrix A=(ai,j)Rn×n ist das Maximum über alle I[n],J[n] der Größe |iI,jJai,j|.

Definieren Sie den Abstand zwischen zwei Matrizen A und B als dC(A,B)=||AB||C

Was ist die Kardinalität des kleinsten ϵ Netzes des metrischen Raums ([0,1]n×n,dC) ?

dh die Größe der kleinsten Teilmenge S[0,1]n×n so dass für alle A[0,1]n×n ein AS so dass dC(A,A)ϵ .

(EDIT: Ich habe vergessen zu erwähnen, aber ich interessiere mich auch für "nicht richtige" ϵ Netze mit SR+n×n - dh wenn die Elemente des ϵ Netzes Einträge außerhalb von [0,1 haben ], das ist auch interessant.)

Ich interessiere mich sowohl für Ober- als auch für Untergrenzen.

Beachten Sie, dass Cut-Sparsifier-Techniken Netze für Cut-Metriken implizieren , aber etwas Stärkeres als ich benötige - sie geben ein ϵ- Net, für das Sie einen ϵ- Close-Punkt für jede Matrix effizient finden können, indem Sie einfach aus dieser Matrix abtasten. Man könnte sich vorstellen , dass es existieren viel kleiner ε -netze , für die kann man nicht einfach Probe einen finde ε -close Punkt auf eine beliebige Matrix.ϵϵϵϵϵ

Diese Frage habe ich hier zunächst bei mathoverflow gestellt.

Aaron Roth
quelle
Da die Schnittnorm von A größer oder gleich dem Absolutwert jedes Eintrags von A ist, ist es klar, dass ein ε-Netz eine Größe von mindestens (1 / (2ε)) ^ (n ^ 2) haben muss. Was ist die Obergrenze, die sich aus der Cut-Sparsifier-Technik ergibt? (Dies ist wahrscheinlich eine dumme Frage, aber ich kenne diese Technik nicht.)
Tsuyoshi Ito
Um sicherzugehen, habe ich die erste Hälfte meines vorherigen Kommentars in eine Antwort umgewandelt (und eine Obergrenze hinzugefügt). Ich interessiere mich immer noch für die Obergrenze, die sich aus der Cut-Sparsifier-Technik ergibt.
Tsuyoshi Ito
{0,m||A||1}[0,1]ϵ
ϵ[0,1]n×nm=O~(n/ϵ2)||A||1/mO(ϵn2)n5/ϵ2ϵϵ>n3/2

Antworten:

8

Hier ist eine einfache Schätzung. Hier nennen wir eine Menge SX ein ε- Netz eines metrischen Raums X, wenn für jeden Punkt xX ein Punkt sS existiert, so dass der Abstand zwischen x und s höchstens ε beträgt . Wenn Sie eine strikte Ungleichung in der Definition von ε -net wünschen, können Sie den Wert von ε leicht anpassen .

Es gilt, dass || A || ≤ || A || Cn 2 || A || , wobei || A || bezeichnet die entrywise Max-Norm eines n × n - Matrix A .

Es ist einfach , eine zu konstruieren ε -Netz des metrischen Raumes ([0,1] N , d ) mit der Größe ⌈1 / (2 ε ) ⌉ N , und es ist nicht schwer , zu zeigen , daß diese Grße das Minimum ist. (Um die Minimalität zu zeigen, betrachten Sie die Punkte ⌈1 / (2 ε ) ⌉ N, deren Koordinaten Vielfache von 1 / ⌈1 / (2 ε ) −1⌉ sind, und zeigen Sie, dass der Abstand zwischen zwei beliebigen dieser Punkte größer als 2 ist ε .) Durch Setzen von N = n 2 und Kombinieren dieser mit dem oben erwähnten Vergleich zwischen der Schnittnorm und der Max-Norm wird die minimale Kardinalität eines ε-Netz in Bezug auf die Schnittnorm ist mindestens ⌈1 / (2 ε ) ⌉ n 2 und höchstens ⌈ n 2 / (2 ε ) ⌉ n 2 .


Update : Wenn meine Berechnung korrekt ist, kann durch das Volumenargument eine bessere Untergrenze Ω ( n / ε ) n 2 erhalten werden. Dazu benötigen wir eine Obergrenze für das Volumen eines ε- Balls in Bezug auf die Schnittnorm.

Zunächst betrachten wir die „Schnittnorm“ eines einzelnen Vektors, die das Maximum zwischen der Summe der positiven Elemente und der negierten Summe der negativen Elemente darstellt. Es ist nicht schwer zu zeigen, dass das Volumen eines ε- Balls in ℝ n in Bezug auf diese „Schnittnorm“ gleich ist

εnI{1,,n}1|I|!1(n|I|)!=εnr=0n(nr)1r!(nr)!

=εnn!r=0n(nr)2=εnn!(2nn)=(2n)!εn(n!)3.

Da die Schnittnorm einer n × n- Matrix A größer oder gleich der Schnittnorm jeder Reihe ist, ist das Volumen eines ε- Balls in ℝ n × n höchstens die n- te Potenz des Volumens von a ε- Ball in ℝ n . Daher muss die Größe eines ε- Netzes von [0,1] n × n mindestens betragen

(n!)3n(2n)!nεn2=(Ω(nε))n2,

wobei die letzte Gleichheit eine langweilige Berechnung ist, in der wir die Stirlingsche Formel verwenden : ln n ! = n ln n - n + O (log n ).

Tsuyoshi Ito
quelle
Als Antwort auf die Bearbeitung (Revision 4) der Frage gilt die in dieser Antwort angegebene Untergrenze auch für „nicht richtige“ ε-Netze.
Tsuyoshi Ito
Sieht richtig aus, schön gemacht!
Hsien-Chih Chang 31 之
@ Hsien-Chih: Danke. Der Teil, den ich am meisten mag, ist die Verwendung von Binomialkoeffizienten bei der Berechnung des Volumens einer ε-Kugel in ℝ ^ n.
Tsuyoshi Ito
Ich vermute, dass die Untergrenze für die Größe des Netzes (entsprechend die Obergrenze für das Volumen) verbessert werden kann. Ich habe eine verwandte Frage zu MathOverflow gestellt.
Tsuyoshi Ito