Уменьшение размерности с провисанием?

11

Лемма Джонсона-Линденштрауса грубо говорит о том, что для любого набора из точек в существует карта где такой, что для всех : Известно, что подобные выражения невозможны для метрики , но известно, есть ли способ обойти такое низкое значение границы, предлагая более слабые гарантии? Например, может ли быть версия вышеуказанной леммы дляп Р д е : R dR K K = O ( журнал N / ε 2 ) х , у S ( 1 - ε ) | | f ( x ) - f ( y ) | | 2| | х - у | | 2( 1 + ϵ ) |SnRdf:RdRkk=O(logn/ϵ2)x,yS1 1

(1ϵ)||f(x)f(y)||2||xy||2(1+ϵ)||f(x)f(y)||2
11метрика, которая только обещает сохранить расстояния большинства точек, но может оставить некоторые произвольно искаженными? Тот, который не дает мультипликативной гарантии для точек, которые «слишком близки»?
Аарон Рот
источник

Ответы:

9

Стандартная ссылка на такой положительный результат - статья Петра Индика об устойчивых распределениях:

http://people.csail.mit.edu/indyk/st-fin.ps

Он показывает метод уменьшения размерности для где расстояние между любой парой точек не увеличивается (более чем в ) с постоянной вероятностью, а расстояния не уменьшаются (более чем в ) при высокой вероятность. Размерность вложения будет экспоненциальной в .11+ϵ1ϵ1/ϵ

Вероятно, есть последующие работы, о которых я не знаю.

Moritz
источник
8

См. Статью « Метрические вложения с расслабленными гарантиями », результаты которой (в условиях «изящно деградирующего искажения») и общим вложениям .1p

Также обратите внимание на практические процедуры для уменьшения измерения в бумаге.1

spinxl39
источник
7

Недавно Ньюман и Рабинович показали, что для n точек в происходит уменьшение размерности до размерности . Используя теорему Абрахама и соавт. (Метрическое вложение с ослабленными гарантиями, упомянутое выше) можно получить уменьшение размера в размерности которое работает для дроби пар.1O(n/ϵ)O(1/(δϵ))1δ

Яир
источник
4

1ScRdkccV1dL1f:1d1kk=O(ϵ2clogc)x,yV f S(1ϵ)f(x)f(y)1xy1(1+ϵ)f(x)f(y)1fS

Совсем недавно Вудрафф и Солер доказали результат, аналогичный результату Талагранда, но с добавленной особенностью, что , как и в JLT, является линейным отображением, выбранным из распределения, независимого от : вам нужно выбрать матрицу где каждая запись является случайной величиной Коида iid. Это в духе стабильных проекций Индика: Коши 1-устойчив. S k × dfSk×d

Сашо Николов
источник