Лема Джонсона — Лінденштрауса () твердить, що набір точок у багатовимірному просторі може бути вбудований у простір значно меншого виміру таким чином, що відстані між точками збережуться майже без викривлень. Відповідні проєкції можуть бути ортогональними. Лема названа на честь Вільяма Б. Джонсона та Джорама Лінденштрауса.
Лема є основою алгоритмів стиснення зображень, машинного навчання. Значна частина даних, що зберігаються та обробляються на комп'ютерах, зокрема текст і зображення, може бути представлена у вигляді точок у просторі, однак основні алгоритми роботи з такими даними, як правило, швидко втрачають продуктивність по мірі збільшення розмірності. Тому бажано зменшити розмірність даних таким чином, щоб зберегти відповідну структуру. Лема Джонсона — Лінденштрауса — класичний результат у цій сфері.
Формулювання Нехай . Тоді для любої множини из точок в і існує лінійне відображення таке, що
для усіх .
Випадкова ортогональна проєкція на -вимірний підпростір задовольняє вимозі.
Один з доказів леми заснований на властивості концентрації міри.
Про доведення Одне з доведень ґрунується на властивості концентрації міри.
Альтернативне формулювання Спорідненою лемою є лема Джонсона — Лінденштрауса про розподіл. Ця дистрибутивна лема стверджує, що для любого 0 < ε, δ < 1/2 і позитивного цілого числа d існує розподіл Rk × d, з якого вилучається матриця A так, що для k = O(ε−2log(1/δ)) і для любого вектора одиничної довжини x ∈ Rd справедливе твердження
Відповідні матриці A отримали назву матриць Джонсона — Лінденштрауса (). По суті, дана лема характеризує точність апроксимації матричною проєкцією багатовимірного розподілу.
Зв'язок дистрибутивної версії леми з її еквівалентом можливо отримати, якщо задати і для якоїсь пари u,v в X.
Швидке перетворення Джонсона — Лінденштрауса Можливість отримання проєкцій меншої розмірності є дуже важливим результатом зазначених лем, однак необхідно, щоб такі проєкції можна було отримати за мінімальний час. Операція множення матриці A на вектор x, що фігурує в дистрибутивній лемі, займає час O(kd). Тому були проведені дослідження щодо отримання розподілів, для яких матрично-векторний добуток може бути обчислено швидше, ніж за час O(kd).
Зокрема, Ейлоном і Бернаром Шазелем в 2006 р. було запропоновано швидке перетворення Джонсона — Лінденштрауса (ШПДЛ), яке дозволило виконати матрично-векторний добуток за час для любої константи .
Особливий випадок становлять тензорні випадкові проєкції, для яких вектор одиничної довжини x має тензорну структуру, і JL-матриці A можуть бути виражені через торцевий добуток кількох матриць з однаковою кількістю незалежних рядків.
Тензорні проєкції багатовимірних просторів
Для представлення тензорних проєкцій, що використовуються в ШПДЛ в багатовимірному випадку, у вигляді комбінації двох JL-матриць, може бути використано торцевий добуток (), запропонований в 1996 р. Слюсарем В. І.Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics — Theory and Methods, 38:19, P. 3501 .
Розглянемо дві JL-матриці проєкцій багатовимірного простору: и . Їх торцевий добуток має вид:
JL-матриці, що визначені у такий спосіб, мають менше випадкових біт і можуть швидко перемножуватися на вектори тензорної структури завдяки тотожності:
,
де — поелементний добуток Адамара.
Перехід від матриці A до торцевого добутку дозволяє оперувати матрицями меншого розміру. У цьому контексті ідея торцевого добутку була використана в 2010Kasiviswanathan, 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..
В 2020 р. було показано, що для створення проєкцій малої розмірності в торцевому добутку досить використовувати будь-які матриці з випадковими незалежними рядками, однак більш сильні гарантії досягнення малих спотворень проєкцій багатовимірних просторів можуть бути досягнуті за допомогою дійсних гаусових матриць Джонсона-Лінденштрауса.
Якщо матриці є незалежними або гаусовими матрицями, то комбінована матриця задовольняє лемі Джонсона-Лінденштрауса про розподіл, якщо кількість строк становить не менше .
Для великих дистрибутивна лема Джонсона-Лінденштрауса виконується строго, при цьому нижня границя величини викривлень апроксимації має експоненціальну залежність . Пропонуються альтернативні конструкції JL-матриць, щоб обійти це обмеження.
Див. також Тензорний скетч
Примітки
Джерела . Journal version of a paper previously appearing at PODC 2001. . Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps ».