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

Лема Джонсона — Лінденштрауса (англ. Johnson–Lindenstrauss lemma) твердить, що набір точок у багатовимірному просторі може бути вбудований у простір значно меншого виміру таким чином, що відстані між точками збережуться майже без викривлень. Відповідні проєкції можуть бути ортогональними. Лема названа на честь Вільяма Б. Джонсона та Джорама Лінденштрауса^[1].

Лема є основою алгоритмів стиснення зображень, машинного навчання. Значна частина даних, що зберігаються та обробляються на комп'ютерах, зокрема текст і зображення, може бути представлена ​​у вигляді точок у просторі, однак основні алгоритми роботи з такими даними, як правило, швидко втрачають продуктивність по мірі збільшення розмірності. Тому бажано зменшити розмірність даних таким чином, щоб зберегти відповідну структуру. Лема Джонсона — Лінденштрауса — класичний результат у цій сфері.

Формулювання

Нехай ${\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.

Швидке перетворення Джонсона&nbsp;— Лінденштрауса

Можливість отримання проєкцій меншої розмірності є дуже важливим результатом зазначених лем, однак необхідно, щоб такі проєкції можна було отримати за мінімальний час. Операція множення матриці 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].

Див. також

• Тензорний скетч