Лема Джонсона-Лінденштрауса

Нехай ${\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..
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps».