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

Пусть ${\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 верно следующее утверждение[2]

${\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}$.[3]

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

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

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

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

${\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[10] для решения задачи дифференциальной приватности (англ. differential privacy). Кроме того, аналогичные вычисления были применены для эффективной реализации ядерного метода и во многих других алгоритмах линейной алгебры[11].

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

Если матрицы ${\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})}$[12].

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

• 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. 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, Random Structures & Algorithms Т. 22 (1): 60–65, doi:10.1002/rsa.10073, <http://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf>.
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), "On fiber diameters of continuous maps".