Лема Джонсона — Лінденштрауса (англ. 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). «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.
- 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.
- 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.
- ↑ Slyusar, V. I. (27 грудня 1996). . Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50–53. Архів оригіналу за 27 липня 2020. Процитовано 31 липня 2020.
- ↑ Slyusar, V. I. (20 травня 1997). . Proc. ICATT-97, Kyiv: 108–109. Архів оригіналу за 25 січня 2020. Процитовано 31 липня 2020.
- ↑ 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.
- ↑ 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.
- ↑ Slyusar, V. I. (2003). . Radioelectronics and Communications Systems 46 (10): 9–17. Архів оригіналу за 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). . 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.]».