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

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

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

Формулювання ред.

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

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

для усіх $u,v\in X$ .

Випадкова ортогональна проєкція $f$ на $m$ -вимірний підпростір задовольняє вимозі.

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

Про доведення ред.

Одне з доведень ґрунується на властивості концентрації міри.

Альтернативне формулювання ред.

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

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

Відповідні матриці A отримали назву матриць Джонсона — Лінденштрауса (англ. JL matrices). По суті, дана лема характеризує точність апроксимації матричною проєкцією багатовимірного розподілу.

Зв'язок дистрибутивної версії леми з її еквівалентом можливо отримати, якщо задати $x=(u-v)/\|u-v\|_{2}$ і $\delta <1/n^{2}$ для якоїсь пари u,v в X.

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

Можливість отримання проєкцій меншої розмірності є дуже важливим результатом зазначених лем, однак необхідно, щоб такі проєкції можна було отримати за мінімальний час. Операція множення матриці A на вектор x, що фігурує в дистрибутивній лемі, займає час O(kd). Тому були проведені дослідження щодо отримання розподілів, для яких матрично-векторний добуток може бути обчислено швидше, ніж за час O(kd).

Зокрема, Ейлоном і Бернаром Шазелем в 2006 р. було запропоновано швидке перетворення Джонсона — Лінденштрауса (ШПДЛ), яке дозволило виконати матрично-векторний добуток за час $d\log d+k^{2+\gamma }$ для любої константи $\gamma >0$ .^[3]

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

Тензорні проєкції багатовимірних просторів ред.

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

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

{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]:

(\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]

,

де $\circ$ — поелементний добуток Адамара.

Перехід від матриці A до торцевого добутку дозволяє оперувати матрицями меншого розміру. У цьому контексті ідея торцевого добутку була використана в 2010^[10] для вирішення завдання диференційної приватності (англ. differential privacy). Крім того, аналогічні обчислення були задіяні для ефективної реалізації ядрових методів машинного навчання та в інших алгоритмах лінійної алгебри^[11].

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

Якщо матриці $C_{1},C_{2},\dots ,C_{c}$ є незалежними $\pm 1$ або гаусовими матрицями, то комбінована матриця $C_{1}\bullet \dots \bullet C_{c}$ задовольняє лемі Джонсона-Лінденштрауса про розподіл, якщо кількість строк становить не менше

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

^[12].

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

Див. також ред.

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

Примітки ред.

↑ 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 0-8218-5030-X. MR 0737400.
↑ 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 0-8218-5030-X. MR 0737400.
↑ 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 1-59593-134-1. MR 2277181.
↑ ^а ^б Slyusar, V. I. (27 грудня 1996). End products in matrices in radar applications (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 31 липня 2020.
↑ ^а ^б Slyusar, V. I. (20 травня 1997). Analytical model of the digital antenna array on a basis of face-splitting matrix products (PDF). Proc. ICATT-97, Kyiv: 108—109. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.
↑ ^а ^б ^в Slyusar, V. I. (15 вересня 1997). New operations of matrices product for applications of radars (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.
↑ ^а ^б Slyusar, V. I. (13 березня 1998). A Family of Face Products of Matrices and its Properties (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.
↑ ^а ^б Slyusar, V. I. (2003). Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels (PDF). Radioelectronics and Communications Systems. 46 (10): 9—17. Архів оригіналу (PDF) за 20 вересня 2020. Процитовано 31 липня 2020.
↑ 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.]
↑ 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.
↑ Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157.
↑ ^а ^б ^в ^г 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), An elementary proof of a theorem of Johnson and Lindenstrauss (PDF), Random Structures & Algorithms, 22 (1): 60—65, doi:10.1002/rsa.10073, архів оригіналу (PDF) за 5 серпня 2012, процитовано 31 липня 2020 {{citation}}: Cite має пустий невідомий параметр: |13= (довідка).
Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps [Архівовано 10 вересня 2016 у Wayback Machine.]».

[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 0-8218-5030-X. 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 0-8218-5030-X. 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 1-59593-134-1. MR 2277181.

[slyusar-4] а ^б Slyusar, V. I. (27 грудня 1996). End products in matrices in radar applications (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 31 липня 2020.

[slyusar1-5] а ^б Slyusar, V. I. (20 травня 1997). Analytical model of the digital antenna array on a basis of face-splitting matrix products (PDF). Proc. ICATT-97, Kyiv: 108—109. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.

[DIPED-6] а ^б ^в Slyusar, V. I. (15 вересня 1997). New operations of matrices product for applications of radars (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.

[slyusar2-7] а ^б Slyusar, V. I. (13 березня 1998). A Family of Face Products of Matrices and its Properties (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.

[general-8] а ^б Slyusar, V. I. (2003). Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels (PDF). Radioelectronics and Communications Systems. 46 (10): 9—17. Архів оригіналу (PDF) за 20 вересня 2020. Процитовано 31 липня 2020.

[Fortiana-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.

[woodruff-11] Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157.

[highdeg-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]