-nets par rapport à la norme de coupe

10

La norme de coupe d'une matrice réelle est le maximum sur tout de la quantité. A = ( a i , j ) R n × n I [ n ] , J [ n ] | i I , j J a i , j |||A||CA=(ai,j)Rn×nI[n],J[n]|iI,jJai,j|

Définissez la distance entre deux matrices et pour êtreB d C ( A , B ) = | | A - B | | CABdC(A,B)=||AB||C

Quelle est la cardinalité du plus petit -net de l'espace métrique ?( [ 0 , 1 ] n × n , d C )ϵ([0,1]n×n,dC)

c'est-à-dire la taille du plus petit sous-ensemble telle sorte que pour tout , il existe un tel que . A [ 0 , 1 ] n × n A S d C ( A , A ) ϵS[0,1]n×nA[0,1]n×nASdC(A,A)ϵ

(EDIT: j'ai oublié de mentionner, mais je suis également intéressé par les " -nets " non appropriés , avec - c'est-à-dire si les éléments du -net a des entrées en dehors de [0,1], ce qui est également intéressant.)S R n × n + ϵϵSR+n×nϵ

Je m'intéresse aux limites supérieures et inférieures.

Notez que les techniques de réduction de sparsifier impliquent -nets pour les métriques de coupe, mais donnent quelque chose de plus fort que ce dont j'ai besoin - elles donnent un -net pour lequel vous pouvez trouver efficacement un point -close à n'importe quelle matrice simplement en échantillonnant à partir de cela matrice. On pourrait imaginer qu'il existe des réseaux beaucoup plus petits pour lesquels vous ne pouvez pas simplement échantillonner trouver un point -close vers une matrice arbitraire.ϵ ϵ ϵ ϵϵϵϵϵϵ

J'ai d'abord posé cette question ici sur mathoverflow.

Aaron Roth
la source
Parce que la norme de coupure de A est supérieure ou égale à la valeur absolue de chaque entrée de A, il est clair qu'un filet ε doit avoir une taille au moins (1 / (2ε)) ^ (n ^ 2). Quelle est la limite supérieure dérivée de la technique du sparsifiant coupé? (C'est probablement une question stupide, mais je ne connais pas cette technique.)
Tsuyoshi Ito
Juste pour être sûr, j'ai transformé la première moitié de mon commentaire précédent en réponse (et y ai ajouté une limite supérieure). Je m'intéresse toujours à la limite supérieure dérivée de la technique du sparsifiant coupé.
Tsuyoshi Ito
La technique ci-dessus donne des matrices avec des entrées dans plutôt que dans . J'ai oublié de le mentionner dans le post, mais je suis également intéressé par ces types de -covers. [ 0 , 1 ] ϵ{0,m||A||1}[0,1]ϵ
Aaron Roth
Le réseau que vous obtenez à partir de la sparsification coupée ne se situe pas réellement dans [ 0 , 1 ] n × n . Interpréter la matrice comme une distribution de probabilité sur les bords d'un graphique orienté et échantillonner m = ˜ O ( n / ϵ 2 ) bords de la distribution. Pondérer chaque bord par | | A | | 1 / m . Par des arguments de dimension VC (ou simplement une union liée à des coupes), l'erreur additive maximale sur n'importe quelle coupe sera O ( ϵ n 2 )ϵ[0,1]n×nm=O~(n/ϵ2)||A||1/mO(ϵn2). Alors que cela implique que l'ensemble des graphes ( de manière appropriée pondérée) sur bords forment un ε - net, qui est non triviale pour ε > n trois / deux . n5/ϵ2ϵϵ>n3/2
Aaron Roth

Réponses:

8

Voici une estimation simple. On appelle ici un ensemble SX un ε -net d'un espace métrique X quand pour chaque point xX , il existe un point sS tel que la distance entre x et s soit au plus ε . Si vous voulez une inégalité stricte dans la définition de ε -net, vous pouvez modifier légèrement la valeur de ε .

Il soutient que || A || ≤ || A || Cn 2 || A || , où || A || désigne la entrywise max-norme d'un n × n matrice A .

Il est facile de construire un ε -net de l'espace métrique ([0,1] N , d ) de taille ⌈1 / (2 ε ) ⌉ N , et il n'est pas difficile de montrer que cette taille est le minimum. (Pour montrer la minimalité, considérons les ⌈1 / (2 ε ) ⌉ N points dont les coordonnées sont des multiples de 1 / ⌈1 / (2 ε ) −1⌉ et montrent que la distance entre deux de ces points est supérieure à 2 ε .) En fixant N = n 2 et en combinant cela avec la comparaison susmentionnée entre la norme de coupe et la norme max, la cardinalité minimale d'un ε-net par rapport à la norme de coupe est au moins ⌈1 / (2 ε ) ⌉ n 2 et au plus ⌈ n 2 / (2 ε ) ⌉ n 2 .


Mise à jour : si mon calcul est correct, une meilleure borne inférieure Ω ( n / ε ) n 2 peut être obtenue par l'argument volume. Pour ce faire, nous avons besoin d'une limite supérieure sur le volume d'une boule ε par rapport à la norme de coupe.

Nous considérons d'abord la «norme de coupure» d'un seul vecteur, qui est le maximum entre la somme des éléments positifs et la somme négée des éléments négatifs. Il n'est pas difficile de montrer que le volume d'une boule ε en ℝ n par rapport à cette «norme de coupe» est égal à

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

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

Ensuite, comme la norme de coupe d'une matrice n × n A est supérieure ou égale à la norme de coupe de chaque ligne, le volume d'une boule ε dans ℝ n × n est au plus la n ème puissance du volume d'un ε -ball dans ℝ n . Par conséquent, la taille d'un ε -net de [0,1] n × n doit être au moins

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

où la dernière égalité est un calcul ennuyeux dans lequel nous utilisons la formule de Stirling : ln n ! = n ln n - n + O (log n ).

Tsuyoshi Ito
la source
En réponse à la révision (révision 4) de la question, la borne inférieure indiquée dans cette réponse est également applicable aux réseaux ε «non appropriés».
Tsuyoshi Ito
Semble correct, bien fait!
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Merci. La partie que j'aime le plus est l'utilisation de coefficients binomiaux dans le calcul du volume d'une ε-boule en ℝ ^ n.
Tsuyoshi Ito
Je soupçonne que la limite inférieure de la taille du filet (de manière équivalente, la limite supérieure du volume) peut être améliorée. J'ai posé une question connexe sur MathOverflow.
Tsuyoshi Ito