Лемма о малом искажении

Лемма о малом искажении (также известна как лемма Джонсона — Линденштрауса) утверждает, что множество из $n$ точек многомерного пространства можно отобразить в пространство размерности гораздо меньше $n$ таким образом, что расстояния между точками останутся почти без изменений. При этом такое отображение можно найти среди ортогональных проекций.

Лемма позволяет сжимать данные, представленные точками многомерного пространства, и, что более важно, сократить размерность данных без существенной потери информации.

Лемма была доказана Вильямом Джонсоном и Йорамом Линденштраусом.

Формулировка

Пусть $0<\varepsilon <1$. Тогда для любого множества $X$ из $n$ точек в $\mathbb {R} ^{N}$ и  $m>{\tfrac {8\cdot \ln n}{\varepsilon ^{2}}}$ существует линейное отображение $f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{m}$ такое, что

$(1-\varepsilon )\cdot \|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\cdot \|u-v\|^{2}$

для всех $u,v\in X$.

Более того случайная ортогональная проекция $f$ на $m$-мерное подпространство удовлетворяет условию с положительной вероятностью.

О доказательствах

Одно из доказательств основано на свойстве концентрации меры.

Альтернативная формулировка

Родственной леммой является лемма Джонсона — Линденштрауса о распределении. Эта дистрибутивная лемма утверждает, что для любого 0 < ε, δ < 1/2 и положительного целого числа d существует распределение R^{k × d}, из которого извлекается матрица A так, что для k = O(ε⁻²log(1/δ)) и для любого вектора единичной длины x ∈ R^d верно следующее утверждение

$P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta$

Соответствующие матрицы A получили название матриц Джонсона — Линденштрауса (англ. JL matrices). По сути, данная лемма характеризует точность аппроскимации матричной проекции многомерного распределения.

Связь дистрибутивной версии леммы с её исходным эквивалентом можно получить, если задать $x=(u-v)/\|u-v\|_{2}$ и $\delta <1/n^{2}$ для некоторой пары u,v в X.

Возможность получения проекций меньшей размерности является очень важным результатом указанных лемм, однако необходимо, чтобы такие проекции можно было получить за минимальное время. Фигурирующая в дистрибутивной лемме операция умножения матрицы A на вектор x занимает время O(kd). Поэтому был проведен ряд исследований по получению распределений, для которых матрично-векторное произведение может быть вычислено быстрее, чем за время O(kd).

В частности, Эйлоном и Бернаром Шазелем в 2006 году было введено так называемое быстрое преобразование Джонсона — Линденштрауса (БПДЛ), которое позволяет вычислять матрично-векторное произведение за время $d\log d+k^{2+\gamma }$ для любой константы $\gamma >0$.

Особый случай представляют тензорные случайные проекции, для которых вектор единичной длины x имеет тензорную структуру и проецирующие JL-матрицы A могут быть выражены через торцевое произведение нескольких матриц с одинаковым количеством независимых строк.

Тензорные проекции многомерных пространств

Для представления тензорных проекций, используемых в БПДЛ в многомерном случае, в виде комбинации двух JL-матриц с одинаковым количеством строк, может быть использовано торцевое произведение (англ. face-splitting product), предложенное в 1996 году Слюсарем В.И..

Рассмотрим две JL-матрицы проекций многомерного пространства: ${C}\in \mathbb {R} ^{3\times 3}$ и ${D}\in \mathbb {R} ^{3\times 3}$. Их торцевое произведение ${C}\bullet {D}$ имеет вид:

${C}\bullet {D}=\left[{\begin{array}{c }{C}_{1}\otimes {D}_{1}\\\hline {C}_{2}\otimes {D}_{2}\\\hline {C}_{3}\otimes {D}_{3}\\\end{array}}\right].$

JL-матрицы, определённые таким образом, используют меньше случайных бит и могут быстро умножаться на векторы с тензорной структурой, благодаря следующему тождеству:

$(\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right]$,

где $\circ$ - поэлементное произведение Адамара.

Переход от проецирующей матрицы A к торцевому произведению позволяет заменить исходное умножение на произведение Адамара, оперирующее матрицами меньшей размерности. В указанном контексте идея торцевого произведения была использована в 2010 для решения задачи дифференциальной приватности (англ. differential privacy). Кроме того, аналогичные вычисления были применены для эффективной реализации ядерного метода и во многих других алгоритмах линейной алгебры.

В 2020 году было показано, что для создания проекций малой размерности в торцевом произведении достаточно использовать любые матрицы со случайными независимыми строками, однако более сильные гарантии достижения малых искажений многомерных пространств могут быть достигнуты с помощью действительных гауссовых матриц Джонсона-Линденштрауса.

Если матрицы $C_{1},C_{2},\dots ,C_{c}$ являются независимыми, содержащими элементы $\pm 1$, или гауссовыми матрицами, то объединённая матрица $C_{1}\bullet \dots \bullet C_{c}$ соответствует лемме Джонсона-Линденштрауса о распределении, если число строк не меньше

$O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})$.

Для больших $\epsilon$ дистрибутивная лемма Джонсона-Линденштрауса выполняется строго, при этом нижняя граница ошибки аппроксимации имеет экспоненциальную зависимость $(\log 1/\delta )^{c}$. Предлагаются альтернативные конструкции JL-матриц, чтобы обойти это ограничение.

Литература

• Achlioptas, Dimitris (2003), "Database-friendly random projections: Johnson-Lindenstrauss with binary coins", Journal of Computer and System Sciences, 66 (4): 671—687, doi:10.1016/S0022-0000(03)00025-4 {{citation}}: Указан более чем один параметр |DOI= and |doi= (справка). Journal version of a paper previously appearing at PODC 2001.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), "An elementary proof of a theorem of Johnson and Lindenstrauss" (PDF), Random Structures & Algorithms, 22 (1): 60—65, doi:10.1002/rsa.10073 {{citation}}: Указан более чем один параметр |DOI= and |doi= (справка).
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), "On fiber diameters of continuous maps".