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

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

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

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

Нехай ${\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-матриць, щоб обійти це обмеження.

Див. також

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

Примітки

1. Johnson, William B.; Lindenstrauss, Joram (1984). Extensions of Lipschitz mappings into a Hilbert space. У Beals, Richard; Beck, Anatole; Bellow, Alexandra та ін. (ред.). Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. Т. 26. Providence, RI: American Mathematical Society. с. 189—206. doi:10.1090/conm/026/737400. ISBN . MR 0737400.
2. Johnson, William B.; Lindenstrauss, Joram (1984). Extensions of Lipschitz mappings into a Hilbert space. У Beals, Richard; Beck, Anatole; Bellow, Alexandra та ін. (ред.). Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. Т. 26. Providence, RI: American Mathematical Society. с. 189–206. doi:10.1090/conm/026/737400. ISBN . MR 0737400.
3. Ailon, Nir; Chazelle, Bernard (2006). Approximate nearest neighbors and the fast Johnson–Lindenstrauss transform. Proceedings of the 38th Annual ACM Symposium on Theory of Computing. New York: ACM Press. с. 557—563. doi:10.1145/1132516.1132597. ISBN . MR 2277181.
4. Slyusar, V. I. (27 грудня 1996). (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 31 липня 2020.
5. Slyusar, V. I. (20 травня 1997). (PDF). Proc. ICATT-97, Kyiv: 108—109. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.
6. Slyusar, V. I. (15 вересня 1997). (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.
7. Slyusar, V. I. (13 березня 1998). (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379—384. doi:10.1007/BF02733426. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.
8. Slyusar, V. I. (2003). (PDF). Radioelectronics and Communications Systems. 46 (10): 9—17. Архів оригіналу (PDF) за 20 вересня 2020. Процитовано 31 липня 2020.
9. Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics — Theory and Methods, 38:19, P. 3501 [1] [ 26 квітня 2021 у Wayback Machine.]
10. Kasiviswanathan, Shiva Prasad, et al. «The price of privately releasing contingency tables and the spectra of random matrices with correlated rows.» Proceedings of the forty-second ACM symposium on Theory of computing. 2010.
11. Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157.
12. Ahle, Thomas; Kapralov, Michael; Knudsen, Jakob; Pagh, Rasmus; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Oblivious Sketching of High-Degree Polynomial Kernels. ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery. doi:10.1137/1.9781611975994.9.

Джерела

• 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), (PDF), Random Structures & Algorithms, 22 (1): 60—65, doi:10.1002/rsa.10073, архів оригіналу (PDF) за 5 серпня 2012, процитовано 31 липня 2020 {{}}: Cite має пустий невідомий параметр: |13= ().
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps [ 10 вересня 2016 у Wayback Machine.]».