-nets con respecto a la norma de corte

La norma de corte de una matriz real es el máximo sobre todo de la cantidad. $||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|$

Defina la distancia entre dos matrices y para que sea $A$ $B$ $d_C(A,B) = ||A-B||_C$

¿Cuál es la cardinalidad de la -net más pequeña del espacio métrico ? $\epsilon$ $([0,1]^{n\times n}, d_C)$

es decir, el tamaño del subconjunto más pequeño tal que para todo , existe una tal que . $S \subset [0,1]^{n\times n}$ $A \in [0,1]^{n\times n}$ $A' \in S$ $d_C(A, A') \leq \epsilon$

(EDITAR: se me olvidó mencionar, pero también estoy interesado en "no apropiado" -nets, con - es decir, si los elementos de la -net tiene entradas fuera de [0,1], que también es interesante.) $\epsilon$ $S \subset \mathcal{R}_+^{n\times n}$ $\epsilon$

Estoy interesado en los límites superiores e inferiores.

Tenga en cuenta que las técnicas de sparsifier de corte implican -nets para las métricas de corte, pero dan algo más fuerte de lo que necesito: dan un -net para el que puede encontrar eficientemente un punto -close a cualquier matriz simplemente tomando muestras de eso matriz. Uno podría imaginar que existen redes mucho más pequeñas para las cuales no puede simplemente muestrear, encuentre un punto -close a una matriz arbitraria. $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$

Inicialmente hice esta pregunta aquí en Mathoverflow.

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

Debido a que la norma de corte de A es mayor o igual que el valor absoluto de cada entrada de A, está claro que una red ε debe tener un tamaño de al menos (1 / (2ε)) ^ (n ^ 2). ¿Cuál es el límite superior derivado de la técnica de corte espaciador? (Esta es probablemente una pregunta tonta, pero no conozco esa técnica.)

Tsuyoshi Ito

Solo para asegurarme, convertí la primera mitad de mi comentario anterior en una respuesta (y le agregué un límite superior). Todavía estoy interesado en el límite superior derivado de la técnica del espaciador de corte.

Tsuyoshi Ito

La técnica anterior produce matrices con entradas en lugar de en . Olvidé mencionarlo en la publicación, pero también estoy interesado en este tipo de -covers.

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

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

[0, 1]

$[0,1]$

ϵ

$\epsilon$

Aaron Roth

La -net que obtienes de la dispersión de corte no se encuentra realmente en . Interprete la matriz como una distribución de probabilidad sobre los bordes de un gráfico dirigido, y muestree bordes de la distribución. Pese cada borde en . Según los argumentos de la dimensión VC (o simplemente una unión vinculada a los cortes), el error aditivo máximo en cualquier corte será . Esto implica que el conjunto de gráficos (ponderados adecuadamente) en bordes forman una -net, que no es trivial para .

ϵ

$\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)$

n^{5} / ϵ^{2}

$n^5/\epsilon^2$

ϵ

$\epsilon$

ϵ > n^{3 / 2}

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

Aaron Roth

Respuestas:

Aquí hay una estimación fácil. Aquí llamamos a un conjunto S ⊆ X una red ε de un espacio métrico X cuando para cada punto x ∈ X , existe un punto s ∈ S tal que la distancia entre x y s es como máximo ε . Si desea una desigualdad estricta en la definición de ε -net, puede modificar ligeramente el valor de ε .

Sostiene que || A || _∞ ≤ || A || _C ≤ n ² || A || _∞ , donde || A || _∞ denota el entrywise max-norma de un n × n matriz A .

Es fácil construir una red ε del espacio métrico ([0,1] ^N , d _∞ ) con un tamaño ⌈1 / (2 ε ) ⌉ ^N , y no es difícil demostrar que este tamaño es el mínimo. (Para mostrar la minimidad, considere los puntos ⌈1 / (2 ε ) ⌉ ^N cuyas coordenadas son múltiplos de 1 / ⌈1 / (2 ε ) −1⌉ y demuestre que la distancia entre dos de estos puntos es mayor que 2 ε .) Al establecer N = n ² y combinar esto con la comparación antes mencionada entre la norma de corte y la norma máxima, la cardinalidad mínima de un ε-net con respecto a la norma de corte es al menos ⌈1 / (2 ε ) ⌉ ^{n ²} y como máximo ⌈ n ² / (2 ε ) ⌉ ^{n ²} .

Actualización : si mi cálculo es correcto, el argumento de volumen puede obtener un mejor límite inferior Ω ( n / ε ) ^{n ²} . Para hacer esto, necesitamos un límite superior en el volumen de una bola ε con respecto a la norma de corte.

Primero consideramos la "norma de corte" de un solo vector, que es el máximo entre la suma de elementos positivos y la suma negada de elementos negativos. No es difícil demostrar que el volumen de una bola ε en ℝ ⁿ con respecto a esta "norma de corte" es igual a

ε^{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}.$

A continuación, ya que la norma corte de un n × n matriz A es mayor que o igual a la norma de corte de cada fila, el volumen de un ε -ball en ℝ ^{n × n} es como máximo el n ésima potencia del volumen de una ε -ball en ℝ ⁿ . Por lo tanto, el tamaño de una red ε de [0,1] ^{n × n} debe ser al menos

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

donde la última igualdad es un cálculo aburrido en el que usamos la fórmula de Stirling : ln n ! = n ln n - n + O (log n ).

Tsuyoshi Ito
fuente

En respuesta a la edición (revisión 4) de la pregunta, el límite inferior indicado en esta respuesta también es aplicable a las redes ε "no apropiadas".

Tsuyoshi Ito

Parece correcto, bien hecho!

Hsien-Chih Chang 張顯之

@ Hsien-Chih: Gracias. La parte que más me gusta es el uso de coeficientes binomiales en el cálculo del volumen de una bola ε en ℝ ^ n.

Tsuyoshi Ito

Sospecho que el límite inferior del tamaño de la red (equivalentemente, el límite superior del volumen) se puede mejorar. Hice una pregunta relacionada sobre MathOverflow.

Tsuyoshi Ito