-сетями относительно нормы разреза

10

Срезанная норма вещественной матрицы A = ( a i , j ) R n × n - максимум по всем I [ n ] , J [ n ] величины | Σ я I , J J я , J | ,||A||CA=(ai,j)Rn×nI[n],J[n]|iI,jJai,j|

Определите расстояние между двумя матрицами A и B как dC(A,B)=||AB||C

Какова мощность наименьшей ϵ сети метрического пространства ([0,1]n×n,dC) ?

т.е. размер наименьшего подмножества такой, что для всех A [ 0 , 1 ] n × n существует A S такой, что d C ( A , A ) ϵ . S[0,1]n×nA[0,1]n×nASdC(A,A)ϵ

(EDIT: Я забыл упомянуть, но я также заинтересован в «не правильный» -сетями с S R п × п + - т.е. если элементы е -Net есть записи за пределами [0,1 ], это тоже интересно.)ϵSR+n×nϵ

Меня интересуют как верхние, так и нижние границы.

Следует отметить , что методы покроя sparsifier подразумевают -сеть для метрик огранки, но дать что - то сильнее , чем мне нужно - они дают ε -сети , для которых можно эффективно найти й -близко точку в любую матрицу просто путем выборки из этой матрицы. Можно было бы предположить , что существует гораздо меньше е -сетями , для которых вы не можете просто образец находим в е -близко точку в произвольной матрице.ϵϵϵϵϵ

Я изначально задавал этот вопрос здесь, на Mathoverflow.

Аарон Рот
источник
Поскольку норма отсечения A больше или равна абсолютному значению каждой записи A, ясно, что ε-сеть должна иметь размер не менее (1 / (2ε)) ^ (n ^ 2). Какая верхняя граница получена при использовании техники разрезающего разреза? (Это, вероятно, глупый вопрос, но я не знаю эту технику.)
Tsuyoshi Ito
Просто чтобы убедиться, я превратил первую половину моего предыдущего комментария в ответ (и добавил к нему верхнюю границу). Я все еще интересуюсь верхней границей, полученной из техники разрезающего спарсификатора.
Цуёси Ито
{0,m||A||1}[0,1]ϵ
ϵ[0,1]n×nm=O~(n/ϵ2)||A||1/mO(ϵn2)n5/ϵ2ϵϵ>n3/2

Ответы:

8

Вот простая оценка. Здесь мы называем множество SX ε -Net метрического пространства X , когда для каждой точки хХ , существует точка sS таким образом, что расстояние между х и ев является не более е . Если вы хотите строгое неравенство в определении ε-сети , вы можете слегка изменить значение ε .

Он считает, что || A || ≤ || A || Cn 2 || A || , где || A || обозначает entrywise Max-норму в п × п матрицы А .

Легко построить ε- сеть метрического пространства ([0,1] N , d ) с размером ⌈1 / (2 ε ) ⌉ N , и нетрудно показать, что этот размер является минимальным. (Чтобы показать минимальность, рассмотрим точки ⌈1 / (2 ε ) ⌉ N , координаты которых кратны 1 / /1 / (2 ε ) −1⌉, и покажем, что расстояние между любыми двумя из этих точек больше 2 ε .) Установив N = n 2 и объединив это с вышеупомянутым сравнением между нормой среза и максимальной нормой, минимальная мощность ε-сеть относительно нормы среза составляет не менее ⌈1 / (2 ε ) ⌉ n 2 и не более ⌈ n 2 / (2 ε ) ⌉ n 2 .


Обновление : если мои вычисления верны, лучшая нижняя граница Ω ( n / ε ) n 2 может быть получена с помощью аргумента громкости. Для этого нам понадобится верхняя граница объема ε- шара относительно нормы разреза.

Сначала мы рассмотрим «норму среза» одного вектора, которая является максимумом между суммой положительных элементов и отрицательной суммой отрицательных элементов. Нетрудно показать, что объем ε- шара в ℝ n относительно этой «нормы отсечения» равен

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

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

Далее, так как разрезанная норма в п × п матрицы А больше или равен разрезанная норму каждой строки, объем ε -шара в ℝ п × п не превосходят в п - й степени объема ε- мяч в ℝ n . Следовательно, размер ε- сети [0,1] n × n должен быть не менее

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

где последнее равенство - скучный расчет, в котором мы используем формулу Стирлинга : ln n ! = n ln n - n + O (log n ).

Цуёси Ито
источник
В ответ на редактирование (редакция 4) вопроса нижняя граница, указанная в этом ответе, также применима к «ненастоящим» ε-сетям.
Цуёси Ито
Выглядит правильно, красиво сделано!
Сянь-Чи Чанг 之 之
@ Сянь-Chih: Спасибо. Больше всего мне нравится использование биномиальных коэффициентов при расчете объема ε-шара в ℝ ^ n.
Tsuyoshi Ito
Я подозреваю, что нижняя граница размера сети (эквивалентно верхней границе объема) может быть улучшена. Я задал связанный вопрос по MathOverflow.
Цуёси Ито