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

Лемма Джонсона-Линденштрауса грубо говорит о том, что для любого набора из точек в существует карта где такой, что для всех : Известно, что подобные выражения невозможны для метрики , но известно, есть ли способ обойти такое низкое значение границы, предлагая более слабые гарантии? Например, может ли быть версия вышеуказанной леммы дляп Р д е : R d → R K K = O ( журнал N / ε 2 ) х , у ∈ S ( 1 - ε ) | | f ( x ) - f ( y ) | | 2 ≤ | | х - у | | 2 ≤ ( 1 + ϵ ) $S$$n$$\mathbb{R}^d$$f:\mathbb{R}^d \rightarrow \mathbb{R}^k$$k = O(\log n/\epsilon^2)$$x, y \in S$ℓ 1 ℓ

$$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$$ $\ell_1$$\ell_1$метрика, которая только обещает сохранить расстояния большинства точек, но может оставить некоторые произвольно искаженными? Тот, который не дает мультипликативной гарантии для точек, которые «слишком близки»?

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

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

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

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

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

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

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

$\ell_1$$S$$c$$\mathbb{R}^d$$k$$c$$c$$V$$\ell_1^d$$L_1$$f:\ell_1^d \rightarrow \ell_1^k$$k = O(\epsilon^{-2}c\log c)$$x, y \in V$ f $(1-\epsilon)\|f(x) - f(y)\|_1 \leq \|x - y\|_1 \leq (1+\epsilon)\|f(x) - f(y)\|_1$$f$$S$

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