Лема Джонсона — Лінденштрауса (англ. 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-матриць, щоб обійти це обмеження.
Див. також
Примітки
- 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.
- 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.
- 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.
- Slyusar, V. I. (27 грудня 1996). (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 31 липня 2020.
- Slyusar, V. I. (20 травня 1997). (PDF). Proc. ICATT-97, Kyiv: 108—109. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 31 липня 2020.
- 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.
- 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.
- Slyusar, V. I. (2003). (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), (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.]».
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
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 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 FormulyuvannyaNehaj 0 lt e lt 1 displaystyle 0 lt varepsilon lt 1 Todi dlya lyuboyi mnozhini X displaystyle X iz n displaystyle n tochok v R N displaystyle mathbb R N i m gt 8 ln n e 2 displaystyle m gt tfrac 8 cdot ln n varepsilon 2 isnuye linijne vidobrazhennya f R N R m displaystyle f mathbb R N rightarrow mathbb R m 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 dlya usih u v X displaystyle u v in X Vipadkova ortogonalna proyekciya f displaystyle f na m displaystyle m vimirnij pidprostir zadovolnyaye vimozi Odin z dokaziv lemi zasnovanij na vlastivosti koncentraciyi miri Pro dovedennyaOdne z doveden grunuyetsya na vlastivosti koncentraciyi miri Alternativne formulyuvannyaSporidnenoyu 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 P A x 2 2 1 gt e lt d displaystyle P Vert Ax Vert 2 2 1 gt varepsilon lt delta 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 i d lt 1 n 2 displaystyle delta lt 1 n 2 dlya yakoyis pari u v v X Shvidke peretvorennya Dzhonsona LindenshtrausaMozhlivist 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 dlya lyuboyi konstanti g gt 0 displaystyle gamma gt 0 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 prostorivDlya 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 Rozglyanemo dvi JL matrici proyekcij bagatovimirnogo prostoru C R 3 3 displaystyle C in mathbb R 3 times 3 i D R 3 3 displaystyle D in mathbb R 3 times 3 Yih torcevij dobutok C D displaystyle C bullet D 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 JL matrici sho viznacheni u takij sposib mayut menshe vipadkovih bit i mozhut shvidko peremnozhuvatisya na vektori tenzornoyi strukturi zavdyaki totozhnosti 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 de displaystyle circ 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 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 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 Yaksho matrici C 1 C 2 C c displaystyle C 1 C 2 dots C c ye nezalezhnimi 1 displaystyle pm 1 abo gausovimi matricyami to kombinovana matricya C 1 C c displaystyle C 1 bullet dots bullet C c 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 Dlya velikih ϵ displaystyle epsilon 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 Proponuyutsya alternativni konstrukciyi JL matric shob obijti ce obmezhennya Div takozhTenzornij sketchPrimitkiJohnson William B Lindenstrauss Joram 1984 Extensions of Lipschitz mappings into a Hilbert space U Beals Richard Beck Anatole Bellow Alexandra ta in red Conference in modern analysis and probability New Haven Conn 1982 Contemporary Mathematics T 26 Providence RI American Mathematical Society s 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 U Beals Richard Beck Anatole Bellow Alexandra ta in red Conference in modern analysis and probability New Haven Conn 1982 Contemporary Mathematics T 26 Providence RI American Mathematical Society s 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 s 557 563 doi 10 1145 1132516 1132597 ISBN 1 59593 134 1 MR 2277181 Slyusar V I 27 grudnya 1996 PDF Radioelectronics and Communications Systems 1998 Vol 41 Number 3 50 53 Arhiv originalu PDF za 27 lipnya 2020 Procitovano 31 lipnya 2020 Slyusar V I 20 travnya 1997 PDF Proc ICATT 97 Kyiv 108 109 Arhiv originalu PDF za 25 sichnya 2020 Procitovano 31 lipnya 2020 Slyusar V I 15 veresnya 1997 PDF Proc Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory DIPED 97 Lviv 73 74 Arhiv originalu PDF za 25 sichnya 2020 Procitovano 31 lipnya 2020 Slyusar V I 13 bereznya 1998 PDF Cybernetics and Systems Analysis C C of Kibernetika I Sistemnyi Analiz 1999 35 3 379 384 doi 10 1007 BF02733426 Arhiv originalu PDF za 25 sichnya 2020 Procitovano 31 lipnya 2020 Slyusar V I 2003 PDF Radioelectronics and Communications Systems 46 10 9 17 Arhiv originalu PDF 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 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 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 DzherelaAchlioptas 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 amp Algorithms 22 1 60 65 doi 10 1002 rsa 10073 arhiv originalu PDF za 5 serpnya 2012 procitovano 31 lipnya 2020 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Cite maye pustij nevidomij parametr 13 dovidka Landweber Peter Lazar Emanuel Patel Neel 2015 On fiber diameters of continuous maps 10 veresnya 2016 u Wayback Machine