Срезанная норма вещественной матрицы A = ( a i , j ) ∈ R n × n - максимум по всем I ⊆ [ n ] , J ⊆ [ n ] величины | Σ я ∈ I , J ∈ J я , J | ,
Определите расстояние между двумя матрицами и как
Какова мощность наименьшей сети метрического пространства ?
т.е. размер наименьшего подмножества такой, что для всех A ∈ [ 0 , 1 ] n × n существует A ′ ∈ S такой, что d C ( A , A ′ ) ≤ ϵ .
(EDIT: Я забыл упомянуть, но я также заинтересован в «не правильный» -сетями с S ⊂ R п × п + - т.е. если элементы е -Net есть записи за пределами [0,1 ], это тоже интересно.)
Меня интересуют как верхние, так и нижние границы.
Следует отметить , что методы покроя sparsifier подразумевают -сеть для метрик огранки, но дать что - то сильнее , чем мне нужно - они дают ε -сети , для которых можно эффективно найти й -близко точку в любую матрицу просто путем выборки из этой матрицы. Можно было бы предположить , что существует гораздо меньше е -сетями , для которых вы не можете просто образец находим в е -близко точку в произвольной матрице.
Я изначально задавал этот вопрос здесь, на Mathoverflow.
Ответы:
Вот простая оценка. Здесь мы называем множество S ⊆ X ε -Net метрического пространства X , когда для каждой точки х ∈ Х , существует точка s ∈ S таким образом, что расстояние между х и ев является не более е . Если вы хотите строгое неравенство в определении ε-сети , вы можете слегка изменить значение ε .
Он считает, что || A || ∞ ≤ || A || C ≤ n 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 относительно этой «нормы отсечения» равен
Далее, так как разрезанная норма в п × п матрицы А больше или равен разрезанная норму каждой строки, объем ε -шара в ℝ п × п не превосходят в п - й степени объема ε- мяч в ℝ n . Следовательно, размер ε- сети [0,1] n × n должен быть не менее
где последнее равенство - скучный расчет, в котором мы используем формулу Стирлинга : ln n ! = n ln n - n + O (log n ).
источник