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

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

Лемма была доказана и .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {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-матрицы, определённые таким образом, используют меньше случайных бит и могут быстро умножаться на векторы с тензорной структурой, благодаря следующему тождеству :

${\displaystyle (\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]}$ ,

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

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

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

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

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

Для больших ${\displaystyle \epsilon }$ дистрибутивная лемма Джонсона-Линденштрауса выполняется строго, при этом нижняя граница ошибки аппроксимации имеет экспоненциальную зависимость ${\displaystyle (\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 : {{ citation }} : Указан более чем один параметр |DOI= and |doi= ( справка ) . Journal version of a paper previously appearing at PODC 2001.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), (PDF) , Random Structures & Algorithms , 22 (1): 60—65, doi : {{ citation }} : Указан более чем один параметр |DOI= and |doi= ( справка ) .
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), " ".