-nets com relação à norma de corte

A norma de corte de uma matriz real é o máximo entre todos os da quantidade. $||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 a distância entre duas matrizes e para ser $A$ $B$ $d_C(A,B) = ||A-B||_C$

Qual é a cardinalidade da menor rede do espaço métrico ? $\epsilon$ $([0,1]^{n\times n}, d_C)$

isto é, o tamanho do menor subconjunto modo que, para todos os , exista um 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$

(EDIT: esqueci de mencionar, mas também estou interessado em redes "não apropriadas" , com - ou seja, se os elementos do -net tem entradas fora de [0,1], isso também é interessante.) $\epsilon$ $S \subset \mathcal{R}_+^{n\times n}$ $\epsilon$

Estou interessado nos limites superiores e inferiores.

Observe que as técnicas de sparsifier de corte implicam -nets para métricas de corte, mas fornecem algo mais forte do que eu preciso - elas fornecem uma -net para a qual você pode encontrar com eficiência um ponto -close para qualquer matriz simplesmente amostrando a partir disso matriz. Pode-se imaginar que existam redes muito menores, das quais você não pode simplesmente amostrar, encontre um ponto de fechamento para uma matriz arbitrária. $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$

Inicialmente, fiz esta pergunta aqui no mathoverflow.

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

Como a norma de corte de A é maior ou igual ao valor absoluto de cada entrada de A, fica claro que uma rede ε deve ter tamanho pelo menos (1 / (2ε)) ^ (n ^ 2). Qual é o limite superior derivado da técnica de sparsifier de corte? (Essa provavelmente é uma pergunta idiota, mas eu não conheço essa técnica.) #

Tsuyoshi Ito

Apenas para ter certeza, transformei a primeira metade do meu comentário anterior em uma resposta (e adicionei um limite superior). Ainda estou interessado no limite superior derivado da técnica do esparsificador de corte.

Tsuyoshi Ito

A técnica acima produz matrizes com entradas em vez de em . Esqueci de mencioná-lo no post, mas também estou interessado nesses tipos de -covers.

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

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

[0, 1]

$[0,1]$

ϵ

$\epsilon$

Aaron Roth

A -net que você obtém da esparsificação do corte não está de fato em . Interprete a matriz como uma distribuição de probabilidade sobre as arestas de um gráfico direcionado e prove arestas da distribuição. Pese cada extremidade em . Por argumentos de dimensão VC (ou apenas uma união ligada a cortes), o erro aditivo máximo em qualquer corte será . Portanto, isso implica que o conjunto de gráficos (adequadamente ponderados) nas bordas forma uma , que não é 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

Respostas:

Aqui está uma estimativa fácil. Aqui chamamos um conjunto S ⊆ X e ε- rede de um espaço métrico X quando, para cada ponto x ∈ X , existe um ponto s ∈ S tal que a distância entre x e s é no máximo ε . Se você deseja uma desigualdade estrita na definição de ε -net, pode ajustar um pouco o valor de ε .

Afirma que || A || _∞ ≤ || A || _C ≤ n ² || A || _Where , onde || A || _∞ indica o entrywise max-norma de um n × n matriz Uma .

É fácil construir uma rede ε do espaço métrico ([0,1] ^N , d _∞ ) com tamanho ⌈1 / (2 ε ) ⌉ ^N , e não é difícil mostrar que esse tamanho é o mínimo. (Para mostrar a minimalidade, considere os pontos ⌈1 / (2 ε ) ⌉ ^N cujas coordenadas são múltiplos de 1 / ⌈1 / (2 ε ) −1⌉ e mostre que a distância entre dois desses pontos é maior que 2 ε .) Ao definir N = n ² e combiná-lo com a comparação acima mencionada entre a norma de corte e a norma máxima, a cardinalidade mínima de um ε-net em relação à norma de corte é de pelo menos ⌈1 / (2 ε ) ⌉ ^{n ²} e no máximo ⌈ n ² / (2 ε ) ⌉ ^{n ²} .

Atualização : Se meu cálculo estiver correto, um limite inferior melhor Ω ( n / ε ) ^{n ²} pode ser obtido pelo argumento do volume. Para fazer isso, precisamos de um limite superior no volume de uma bola ε com relação à norma de corte.

Primeiro, consideramos a “norma de corte” de um único vetor, que é o máximo entre a soma dos elementos positivos e a soma negada dos elementos negativos. Não é difícil mostrar que o volume de uma bola ε em with ⁿ com relação a essa “norma de corte” é 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}.$

Em seguida, uma vez que a norma corte de um n × n matriz A é maior do que ou igual à norma corte de cada linha, o volume de uma ε -ball em ℝ ^{n × n} é no máximo o n ° de energia do volume de um bola em ℝ ⁿ . Portanto, o tamanho de uma rede ε de [0,1] ^{n × n} deve ser pelo 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},$

onde a última igualdade é um cálculo chato no qual usamos a fórmula de Stirling : ln n ! = n ln n - n + O (log n ).

Tsuyoshi Ito
fonte

Em resposta à edição (revisão 4) da pergunta, o limite inferior indicado nesta resposta também é aplicável às redes ε "não apropriadas".

Tsuyoshi Ito 30/01

Parece correto, bem feito!

Hsien-Chih Chang

@ Hsien-Chih: Obrigado. A parte que mais gosto é o uso de coeficientes binomiais no cálculo do volume de uma bola ε em ℝ ^ n.

Tsuyoshi Ito 31/01

Suspeito que o limite inferior do tamanho da rede (equivalente ao limite superior do volume) possa ser melhorado. Eu fiz uma pergunta relacionada no MathOverflow.

Tsuyoshi Ito