-nets par rapport à la norme de coupe

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||_C$$A = (a_{i,j}) \in \mathcal{R}^{n\times n}$$I \subseteq [n], J \subseteq [n]$$\left|\sum_{i \in I, j \in J}a_{i,j}\right|$

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

Quelle est la cardinalité du plus petit -net de l'espace métrique ?( [ 0 , 1 ] n × n , d C$\epsilon$$([0,1]^{n\times n}, d_C)$

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 \subset [0,1]^{n\times n}$$A \in [0,1]^{n\times n}$$A' \in S$$d_C(A, A') \leq \epsilon$

(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 +$\epsilon$$S \subset \mathcal{R}_+^{n\times n}$$\epsilon$

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.ϵ ϵ ϵ $\epsilon$$\epsilon$$\epsilon$$\epsilon$$\epsilon$

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

Voici une estimation simple. On appelle ici un ensemble S ⊆ X un ε -net d'un espace métrique X quand pour chaque point x ∈ X , il existe un point s ∈ S 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 || _C ≤ n ² || 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 ² 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 ε ) ⌉ ^{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 ℝ ⁿ par rapport à cette «norme de coupe» est égal à

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 ℝ ⁿ . Par conséquent, la taille d'un ε -net de [0,1] ^{n × n} doit être au moins

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 ).