Изометрическое вложение L2 в L1

27

Известно , что дано n - точечное подмножество 2d (то есть, заданный n точек в Rd с евклидовым расстоянием) можно вставлять их изометрический в 1(n2) .

Является ли изометрия вычислимой за (возможно, рандомизированное) полиномиальное время?

Поскольку существуют проблемы с конечной точностью, точный вопрос

Для заданного множества X из n точек в Rd и ϵ>0 существует ли отображение f:XR(n2) вычисляемое (возможно, с использованием случайности) в полином по времени от n и логарифмический по 1/ϵ такой, что для каждого x,yX имеем

||f(x)f(y)||1||xy||2(1+ϵ)||f(x)f(y)||1

(Примечание: мне известно, что отображение с искажением (1+ϵ) можно найти с высокой вероятностью по полиному по времени от n и 1/ϵ , проецируя на O(ϵ2logn) случайные линии, но я не уверен, можно ли конструктивно уменьшить число измерений до (n2) или даже O(n2) когда 1/ϵ намного больше n , и я не знаю, есть ли метод полиномиального времени для обработки случая, когда 1/ϵ экспоненциально по n .)

Лука Тревизан
источник
1
это очень хороший вопрос @ Лука, ты подозреваешь, что это может быть трудно? (конечно, моей первой мыслью было просмотреть «Хэмминг встречает Евклида», а затем я увидел личность спрашивающего :)
Суреш Венкат
1
Эта ссылка, по-видимому, связана: Петр Индик, «Принципы неопределенности, экстракторы и явные вложения l2 в l1», Proc. STOC'07.
Мартин Шварц
2
@ Давид: это количество точек, я исправил место, где я использовал для измерения. То, что точек в евклидовом пространстве (любого измерения) могут быть вложены изометрически в , доказано здесь: www-math.mit.edu/~goemans/18409-2006/lec1.pdf, но не -конструктивно. (Теорема Каратеодори о переходе от конечной, но большой размерности к размерности с произвольно малой ошибкой и аргументе компактности о переходе от произвольно малой ошибки к нулевой ошибке.)nnn1(n2)(n2)
Лука Тревизан,
1
@Martin: спасибо за ссылку. Статья Петра посвящена более сложной задаче отображения всех (а не только фиксированного набора из точек) в . Для этой проблемы я считаю, что это открытая проблема даже для достижения конструктивно и искажения . (Петр получает и .)2dn1mm=poly(d,1/ϵ)(1+ϵ)m=dO(logd)ϵ=1/d
Лука Тревизан
1
@LucaTrevisan: re: сложность встраивания в l1, это правда (это упоминается в главе 1 или 2 книги Деза и Лорана - я думаю, через MAX CUT)
Суреш Венкат

Ответы:

7

Суреш попросил меня собрать мои комментарии выше в ответ, так что вот оно. Я не совсем уверен, что это ответ на первоначальный вопрос, так как не очевидно, как сделать это полиномиальным временем, когда размерность входного евклидова пространства непостоянна. По крайней мере, у него есть преимущество в том, чтобы избежать любой проблемы с большим как задает оригинальный вопрос, потому что он не включает в себя никакого приближения и выглядит многочленным для константы .1/ϵd

В любом случае: из интегральной геометрии существует стандартная мера на множествах гиперплоскостей в мерном евклидовом пространстве, инвариантная относительно евклидовых конгруэнций. Свойство состоит в том, что длина любой кривой ограниченной длины пропорциональна мере гиперплоскостей, пересекающих (с кратностью, что означает, что если гиперплоскость пересекает дважды, то она вносит двойной вклад в общую меру гиперплоскостей, пересекающих ). В частности, если является отрезком прямой, усложнение множественности не возникает, и мы можем нормализовать меру на гиперплоскостях, пересекающих точно равной длинеdCCCCCCC, (Гиперплоскости, содержащие имеют нулевую меру, поэтому не беспокойтесь о бесконечной кратности.)C

Теперь, учитывая набор из n точек в d-мерном пространстве, сделайте координату для каждого из разбиений точек на два подмножества, индуцированных гиперплоскостью, которая не проходит ни через одну из точек. Приведите точки на одной стороне значения координаты разбиения к нулю, а точки на другой стороне значения координаты разбиения равны мере набора гиперплоскостей, индуцирующих это разбиение.1

Если и - любые две из точек, пусть - множество гиперплоскостей, пересекающих отрезок прямой , и пусть - подмножества образованные каждым возможным разбиением гиперплоскости, у которого на одной стороне и на другой. Тогда является непересекающимся объединением , а разности координат между и являются просто мерами подмножеств . Следовательно, расстояние между координатами иpqnKpqKiKpqKKipqKi1pq (сумма мер ) является мерой , которая является просто исходным расстоянием между и .KiK2pq

Для вычислительных геометров может быть полезно альтернативное описание той же конструкции: используйте проективную двойственность для преобразования входных точек в гиперплоскостей и разделения гиперплоскостей на точки. Мера интегральной геометрии на наборах гиперплоскостей затем преобразуется в более стандартную меру на наборах точек, расстояние между и удваивается к мере двойного клина между двумя гиперплоскостями, а расположение гиперплоскости разбивает этот двойной клин на меньшие ячейки , Значение координаты для точки является либо мерой одной из ячеек в расположении (если двойная гиперплоскость находится ниже ячейки этой координаты), либо нулем (если двойная гиперплоскость находится выше ячейки). Следовательноnnpq1Расстояние между и - это просто сумма мер ячеек в двойном клине, которая совпадает с мерой всего двойного клина. Эта двойная точка зрения также позволяет легко вычислить размерность вложения, найденного таким образом: это просто число ячеек в расположении гиперплоскости, которое равно , или, точнее, самое большее .pqO(nd)i=0d(ni)

Пока что это дает полностью детерминированное и точное вложение в . Но мы хотели меньшее измерение, . Вот где вступает комментарий Луки о теореме Каратеодори . Множество представимых метрик образует многогранный конус в мерном пространстве всех функций от неупорядоченных пар точек до действительных чисел, а приведенный выше геометрический аргумент говорит, что евклидова метрика принадлежит этому конусу. Точки на крайних лучах конуса являются одномерными1O(nd)1(n2)1(n2)1псевдометрика (в которой точки делятся на два набора, все расстояния в одном наборе равны нулю, а все расстояния через разбиение равны), и Каратеодори говорит, что любая точка в конусе (включая ту, которая нам нужна) может быть представленный в виде выпуклой комбинации точек на экстремальных лучах, число которых не превосходит размерности окружающего пространства, . Но выпуклая комбинация не более чем одномерные метрики является метрикой .(n2)(n2)11(n2)

Наконец, как мы можем на самом деле вычислить мерное вложение? На данный момент у нас есть не только точка в мерный выпуклый конус метрики (метрика расстояния, с которой мы начали), но у нас также есть множество крайних точек конуса (соответствует разбиению входных данных на два подмножества, индуцированных гиперплоскостями), так что наша метрика представляет собой выпуклую комбинацию этих крайних точек - для малых это большое улучшение по сравнению с крайними лучами, которые имеет конус в целом. Теперь все, что нам нужно сделать, это применить жадный алгоритм, который избавляет от крайних точек из нашего множества, один за другим, пока только(n2)(n2)1O(nd)d2n2(n2)из них остались. На каждом этапе нам нужно поддерживать в качестве инварианта, что наша метрика все еще находится внутри выпуклой оболочки оставшихся крайних точек, что является просто проблемой выполнимости линейного программирования, и если мы сделаем это, Каратеодори будет гарантировать, что всегда остается набор крайние точки, выпуклая оболочка которых содержит входную метрику.(n2)

Дэвид Эппштейн
источник