www.wikidata.uk-ua.nina.az

Лема Джонсона Лінденштрауса англ Johnson Lindenstrauss lemma твердить що набір точок у багатовимірному просторі може бут

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

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

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

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

Нехай . Тоді для любої множини из точок в і  існує лінійне відображення таке, що

для усіх .

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

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

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

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

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

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

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

Зв'язок дистрибутивної версії леми з її еквівалентом можливо отримати, якщо задати і для якоїсь пари u,v в X.

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

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

Зокрема, Ейлоном і Бернаром Шазелем в 2006 р. було запропоновано швидке перетворення Джонсона — Лінденштрауса (ШПДЛ), яке дозволило виконати матрично-векторний добуток за час для любої константи .

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

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

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

Розглянемо дві JL-матриці проєкцій багатовимірного простору: и . Їх торцевий добуток має вид:

JL-матриці, що визначені у такий спосіб, мають менше випадкових біт і можуть швидко перемножуватися на вектори тензорної структури завдяки тотожності:

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

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

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

Якщо матриці є незалежними або гаусовими матрицями, то комбінована матриця задовольняє лемі Джонсона-Лінденштрауса про розподіл, якщо кількість строк становить не менше

Для великих дистрибутивна лема Джонсона-Лінденштрауса виконується строго, при цьому нижня границя величини викривлень апроксимації має експоненціальну залежність . Пропонуються альтернативні конструкції JL-матриць, щоб обійти це обмеження.

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

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

  1. Johnson, William B.; Lindenstrauss, Joram (1984). «Conference in modern analysis and probability (New Haven, Conn., 1982)». У Beals, Richard; Beck, Anatole; Bellow, Alexandra та ін.. Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 0-8218-5030-X. 
  2. Johnson, William B.; Lindenstrauss, Joram (1984). «Conference in modern analysis and probability (New Haven, Conn., 1982)». У Beals, Richard; Beck, Anatole; Bellow, Alexandra та ін.. Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 0-8218-5030-X. https://archive.org/details/conferenceinmode0000conf/page/189. 
  3. Ailon, Nir; Chazelle, Bernard (2006). «Proceedings of the 38th Annual ACM Symposium on Theory of Computing». Proceedings of the 38th Annual ACM Symposium on Theory of Computing. New York: ACM Press. pp. 557–563. doi:10.1145/1132516.1132597. ISBN 1-59593-134-1. 
  4. ↑ Slyusar, V. I. (27 грудня 1996). . Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50–53. Архів оригіналу за 27 липня 2020. Процитовано 31 липня 2020. 
  5. ↑ Slyusar, V. I. (20 травня 1997). . Proc. ICATT-97, Kyiv: 108–109. Архів оригіналу за 25 січня 2020. Процитовано 31 липня 2020. 
  6. ↑ Slyusar, V. I. (15 вересня 1997). . Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73–74. Архів оригіналу за 25 січня 2020. Процитовано 31 липня 2020. 
  7. ↑ Slyusar, V. I. (13 березня 1998). . Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379–384. doi:10.1007/BF02733426. Архів оригіналу за 25 січня 2020. Процитовано 31 липня 2020. 
  8. ↑ Slyusar, V. I. (2003). . Radioelectronics and Communications Systems 46 (10): 9–17. Архів оригіналу за 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). . Random Structures & Algorithms 22 (1): 60–65. doi:10.1002/rsa.10073. Архів оригіналу за 5 серпня 2012. Процитовано 31 липня 2020. .
  • Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps [ 10 вересня 2016 у Wayback Machine.]».
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Lema Dzhonsona Lindenshtrausa angl Johnson Lindenstrauss lemma tverdit sho nabir tochok u bagatovimirnomu prostori mozhe buti vbudovanij u prostir znachno menshogo vimiru takim chinom sho vidstani mizh tochkami zberezhutsya majzhe bez vikrivlen Vidpovidni proyekciyi mozhut buti ortogonalnimi Lema nazvana na chest Vilyama B Dzhonsona ta Dzhorama Lindenshtrausa 1 Lema ye osnovoyu algoritmiv stisnennya zobrazhen mashinnogo navchannya Znachna chastina danih sho zberigayutsya ta obroblyayutsya na komp yuterah zokrema tekst i zobrazhennya mozhe buti predstavlena u viglyadi tochok u prostori odnak osnovni algoritmi roboti z takimi danimi yak pravilo shvidko vtrachayut produktivnist po miri zbilshennya rozmirnosti Tomu bazhano zmenshiti rozmirnist danih takim chinom shob zberegti vidpovidnu strukturu Lema Dzhonsona Lindenshtrausa klasichnij rezultat u cij sferi Zmist 1 Formulyuvannya 2 Pro dovedennya 3 Alternativne formulyuvannya 4 Shvidke peretvorennya Dzhonsona Lindenshtrausa 5 Tenzorni proyekciyi bagatovimirnih prostoriv 6 Div takozh 7 Primitki 8 DzherelaFormulyuvannya red Nehaj 0 lt e lt 1 displaystyle 0 lt varepsilon lt 1 nbsp Todi dlya lyuboyi mnozhini X displaystyle X nbsp iz n displaystyle n nbsp tochok v R N displaystyle mathbb R N nbsp i m gt 8 ln n e 2 displaystyle m gt tfrac 8 cdot ln n varepsilon 2 nbsp isnuye linijne vidobrazhennya f R N R m displaystyle f mathbb R N rightarrow mathbb R m nbsp take sho 1 e u v 2 f u f v 2 1 e u v 2 displaystyle 1 varepsilon cdot u v 2 leq f u f v 2 leq 1 varepsilon cdot u v 2 nbsp dlya usih u v X displaystyle u v in X nbsp Vipadkova ortogonalna proyekciya f displaystyle f nbsp na m displaystyle m nbsp vimirnij pidprostir zadovolnyaye vimozi Odin z dokaziv lemi zasnovanij na vlastivosti koncentraciyi miri Pro dovedennya red Odne z doveden grunuyetsya na vlastivosti koncentraciyi miri Alternativne formulyuvannya red Sporidnenoyu lemoyu ye lema Dzhonsona Lindenshtrausa pro rozpodil Cya distributivna lema stverdzhuye sho dlya lyubogo 0 lt e d lt 1 2 i pozitivnogo cilogo chisla d isnuye rozpodil Rk d z yakogo viluchayetsya matricya A tak sho dlya k O e 2log 1 d i dlya lyubogo vektora odinichnoyi dovzhini x Rd spravedlive tverdzhennya 2 P A x 2 2 1 gt e lt d displaystyle P Vert Ax Vert 2 2 1 gt varepsilon lt delta nbsp Vidpovidni matrici A otrimali nazvu matric Dzhonsona Lindenshtrausa angl JL matrices Po suti dana lema harakterizuye tochnist aproksimaciyi matrichnoyu proyekciyeyu bagatovimirnogo rozpodilu Zv yazok distributivnoyi versiyi lemi z yiyi ekvivalentom mozhlivo otrimati yaksho zadati x u v u v 2 displaystyle x u v u v 2 nbsp i d lt 1 n 2 displaystyle delta lt 1 n 2 nbsp dlya yakoyis pari u v v X Shvidke peretvorennya Dzhonsona Lindenshtrausa red Mozhlivist otrimannya proyekcij menshoyi rozmirnosti ye duzhe vazhlivim rezultatom zaznachenih lem odnak neobhidno shob taki proyekciyi mozhna bulo otrimati za minimalnij chas Operaciya mnozhennya matrici A na vektor x sho figuruye v distributivnij lemi zajmaye chas O kd Tomu buli provedeni doslidzhennya shodo otrimannya rozpodiliv dlya yakih matrichno vektornij dobutok mozhe buti obchisleno shvidshe nizh za chas O kd Zokrema Ejlonom i Bernarom Shazelem v 2006 r bulo zaproponovano shvidke peretvorennya Dzhonsona Lindenshtrausa ShPDL yake dozvolilo vikonati matrichno vektornij dobutok za chas d log d k 2 g displaystyle d log d k 2 gamma nbsp dlya lyuboyi konstanti g gt 0 displaystyle gamma gt 0 nbsp 3 Osoblivij vipadok stanovlyat tenzorni vipadkovi proyekciyi dlya yakih vektor odinichnoyi dovzhini x maye tenzornu strukturu i JL matrici A mozhut buti virazheni cherez torcevij dobutok kilkoh matric z odnakovoyu kilkistyu nezalezhnih ryadkiv Tenzorni proyekciyi bagatovimirnih prostoriv red Dlya predstavlennya tenzornih proyekcij sho vikoristovuyutsya v ShPDL v bagatovimirnomu vipadku u viglyadi kombinaciyi dvoh JL matric mozhe buti vikoristano torcevij dobutok angl face splitting product zaproponovanij v 1996 r Slyusarem V I 4 5 6 7 8 9 Rozglyanemo dvi JL matrici proyekcij bagatovimirnogo prostoru C R 3 3 displaystyle C in mathbb R 3 times 3 nbsp i D R 3 3 displaystyle D in mathbb R 3 times 3 nbsp Yih torcevij dobutok C D displaystyle C bullet D nbsp 4 5 6 7 8 maye vid C D C 1 D 1 C 2 D 2 C 3 D 3 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 nbsp JL matrici sho viznacheni u takij sposib mayut menshe vipadkovih bit i mozhut shvidko peremnozhuvatisya na vektori tenzornoyi strukturi zavdyaki totozhnosti 6 C D x y C x D y C x 1 D y 1 C x 2 D y 2 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 nbsp de displaystyle circ nbsp poelementnij dobutok Adamara Perehid vid matrici A do torcevogo dobutku dozvolyaye operuvati matricyami menshogo rozmiru U comu konteksti ideya torcevogo dobutku bula vikoristana v 2010 10 dlya virishennya zavdannya diferencijnoyi privatnosti angl differential privacy Krim togo analogichni obchislennya buli zadiyani dlya efektivnoyi realizaciyi yadrovih metodiv mashinnogo navchannya ta v inshih algoritmah linijnoyi algebri 11 V 2020 r bulo pokazano sho dlya stvorennya proyekcij maloyi rozmirnosti v torcevomu dobutku dosit vikoristovuvati bud yaki matrici z vipadkovimi nezalezhnimi ryadkami odnak bilsh silni garantiyi dosyagnennya malih spotvoren proyekcij bagatovimirnih prostoriv mozhut buti dosyagnuti za dopomogoyu dijsnih gausovih matric Dzhonsona Lindenshtrausa 12 Yaksho matrici C 1 C 2 C c displaystyle C 1 C 2 dots C c nbsp ye nezalezhnimi 1 displaystyle pm 1 nbsp abo gausovimi matricyami to kombinovana matricya C 1 C c displaystyle C 1 bullet dots bullet C c nbsp zadovolnyaye lemi Dzhonsona Lindenshtrausa pro rozpodil yaksho kilkist strok stanovit ne menshe O ϵ 2 log 1 d ϵ 1 1 c log 1 d c displaystyle O epsilon 2 log 1 delta epsilon 1 tfrac 1 c log 1 delta c nbsp 12 Dlya velikih ϵ displaystyle epsilon nbsp distributivna lema Dzhonsona Lindenshtrausa vikonuyetsya strogo pri comu nizhnya granicya velichini vikrivlen aproksimaciyi maye eksponencialnu zalezhnist log 1 d c displaystyle log 1 delta c nbsp 12 Proponuyutsya alternativni konstrukciyi JL matric shob obijti ce obmezhennya 12 Div takozh red Tenzornij sketchPrimitki red Johnson William B Lindenstrauss Joram 1984 Conference in modern analysis and probability New Haven Conn 1982 U Beals Richard Beck Anatole Bellow Alexandra ta in Conference in modern analysis and probability New Haven Conn 1982 Contemporary Mathematics 26 Providence RI American Mathematical Society pp 189 206 doi 10 1090 conm 026 737400 ISBN 0 8218 5030 X Johnson William B Lindenstrauss Joram 1984 Conference in modern analysis and probability New Haven Conn 1982 U Beals Richard Beck Anatole Bellow Alexandra ta in Conference in modern analysis and probability New Haven Conn 1982 Contemporary Mathematics 26 Providence RI American Mathematical Society pp 189 206 doi 10 1090 conm 026 737400 ISBN 0 8218 5030 X https archive org details conferenceinmode0000conf page 189 Ailon Nir Chazelle Bernard 2006 Proceedings of the 38th Annual ACM Symposium on Theory of Computing Proceedings of the 38th Annual ACM Symposium on Theory of Computing New York ACM Press pp 557 563 doi 10 1145 1132516 1132597 ISBN 1 59593 134 1 a b Slyusar V I 27 grudnya 1996 End products in matrices in radar applications Radioelectronics and Communications Systems 1998 Vol 41 Number 3 50 53 Arhiv originalu za 27 lipnya 2020 Procitovano 31 lipnya 2020 a b Slyusar V I 20 travnya 1997 Analytical model of the digital antenna array on a basis of face splitting matrix products Proc ICATT 97 Kyiv 108 109 Arhiv originalu za 25 sichnya 2020 Procitovano 31 lipnya 2020 a b v Slyusar V I 15 veresnya 1997 New operations of matrices product for applications of radars Proc Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory DIPED 97 Lviv 73 74 Arhiv originalu za 25 sichnya 2020 Procitovano 31 lipnya 2020 a b Slyusar V I 13 bereznya 1998 A Family of Face Products of Matrices and its Properties Cybernetics and Systems Analysis C C of Kibernetika I Sistemnyi Analiz 1999 35 3 379 384 doi 10 1007 BF02733426 Arhiv originalu za 25 sichnya 2020 Procitovano 31 lipnya 2020 a b Slyusar V I 2003 Generalized face products of matrices in models of digital antenna arrays with nonidentical channels Radioelectronics and Communications Systems 46 10 9 17 Arhiv originalu za 20 veresnya 2020 Procitovano 31 lipnya 2020 Anna Esteve Eva Boj amp Josep Fortiana 2009 Interaction Terms in Distance Based Regression Communications in Statistics Theory and Methods 38 19 P 3501 1 Arhivovano 26 kvitnya 2021 u 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 a b v g 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 Dzherela red 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 amp Algorithms 22 1 60 65 doi 10 1002 rsa 10073 Arhiv originalu za 5 serpnya 2012 Procitovano 31 lipnya 2020 Landweber Peter Lazar Emanuel Patel Neel 2015 On fiber diameters of continuous maps Arhivovano 10 veresnya 2016 u Wayback Machine Otrimano z https uk wikipedia org w index php title Lema Dzhonsona Lindenshtrausa amp oldid 36466362