Лемма о малом искажении
Лемма о малом искажении (также известна как лемма Джонсона — Линденштрауса) утверждает, что множество из точек многомерного пространства можно отобразить в пространство размерности гораздо меньше таким образом, что расстояния между точками останутся почти без изменений. При этом такое отображение можно найти среди ортогональных проекций.
Лемма позволяет сжимать данные, представленные точками многомерного пространства, и, что более важно, сократить размерность данных без существенной потери информации.
Лемма была доказана Вильямом Джонсоном[англ.] и Йорамом Линденштраусом[англ.].[1]
Формулировка
Пусть . Тогда для любого множества из точек в и существует линейное отображение такое, что
для всех .
Более того случайная ортогональная проекция на -мерное подпространство удовлетворяет условию с положительной вероятностью.
О доказательствах
Одно из доказательств основано на свойстве концентрации меры.
Альтернативная формулировка
Родственной леммой является лемма Джонсона — Линденштрауса о распределении. Эта дистрибутивная лемма утверждает, что для любого 0 < ε, δ < 1/2 и положительного целого числа d существует распределение Rk × d, из которого извлекается матрица A так, что для k = O(ε−2log(1/δ)) и для любого вектора единичной длины x ∈ Rd верно следующее утверждение[2]
Соответствующие матрицы A получили название матриц Джонсона — Линденштрауса (англ. JL matrices). По сути, данная лемма характеризует точность аппроскимации матричной проекции многомерного распределения.
Связь дистрибутивной версии леммы с её исходным эквивалентом можно получить, если задать и для некоторой пары u,v в X.
Возможность получения проекций меньшей размерности является очень важным результатом указанных лемм, однако необходимо, чтобы такие проекции можно было получить за минимальное время. Фигурирующая в дистрибутивной лемме операция умножения матрицы A на вектор x занимает время O(kd). Поэтому был проведен ряд исследований по получению распределений, для которых матрично-векторное произведение может быть вычислено быстрее, чем за время O(kd).
В частности, Эйлоном и Бернаром Шазелем в 2006 году было введено так называемое быстрое преобразование Джонсона — Линденштрауса (БПДЛ), которое позволяет вычислять матрично-векторное произведение за время для любой константы .[3]
Особый случай представляют тензорные случайные проекции, для которых вектор единичной длины x имеет тензорную структуру и проецирующие JL-матрицы A могут быть выражены через торцевое произведение нескольких матриц с одинаковым количеством независимых строк.
Тензорные проекции многомерных пространств
Для представления тензорных проекций, используемых в БПДЛ в многомерном случае, в виде комбинации двух JL-матриц с одинаковым количеством строк, может быть использовано торцевое произведение (англ. face-splitting product), предложенное в 1996 году Слюсарем В.И.[4][5][6][7][8][9].
Рассмотрим две JL-матрицы проекций многомерного пространства: и . Их торцевое произведение [4][5][6][7][8] имеет вид:
JL-матрицы, определённые таким образом, используют меньше случайных бит и могут быстро умножаться на векторы с тензорной структурой, благодаря следующему тождеству[6]:
- ,
где - поэлементное произведение Адамара.
Переход от проецирующей матрицы A к торцевому произведению позволяет заменить исходное умножение на произведение Адамара, оперирующее матрицами меньшей размерности. В указанном контексте идея торцевого произведения была использована в 2010[10] для решения задачи дифференциальной приватности (англ. differential privacy). Кроме того, аналогичные вычисления были применены для эффективной реализации ядерного метода и во многих других алгоритмах линейной алгебры[11].
В 2020 году было показано, что для создания проекций малой размерности в торцевом произведении достаточно использовать любые матрицы со случайными независимыми строками, однако более сильные гарантии достижения малых искажений многомерных пространств могут быть достигнуты с помощью действительных гауссовых матриц Джонсона-Линденштрауса[12].
Если матрицы являются независимыми, содержащими элементы , или гауссовыми матрицами, то объединённая матрица соответствует лемме Джонсона-Линденштрауса о распределении, если число строк не меньше
- [12].
Для больших дистрибутивная лемма Джонсона-Линденштрауса выполняется строго, при этом нижняя граница ошибки аппроксимации имеет экспоненциальную зависимость [12]. Предлагаются альтернативные конструкции JL-матриц, чтобы обойти это ограничение[12].
Примечания
- ↑ Johnson, William B.; Lindenstrauss, Joram (1984). "Extensions of Lipschitz mappings into a Hilbert space". In Beals, Richard; Beck, Anatole; Bellow, Alexandra; et al. (eds.). Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. Vol. 26. Providence, RI: American Mathematical Society. pp. 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". In Beals, Richard; Beck, Anatole; Bellow, Alexandra; et al. (eds.). Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. Vol. 26. Providence, RI: American Mathematical Society. pp. 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. pp. 557—563. doi:10.1145/1132516.1132597. ISBN 1-59593-134-1. MR 2277181.
- ↑ 1 2 Slyusar, V. I. (December 27, 1996). "End products in matrices in radar applications" (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архивировано (PDF) 27 июля 2020. Дата обращения: 30 июля 2020.
- ↑ 1 2 Slyusar, V. I. (1997-05-20). "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. Дата обращения: 30 июля 2020.
- ↑ 1 2 3 Slyusar, V. I. (1997-09-15). "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. Дата обращения: 30 июля 2020.
- ↑ 1 2 Slyusar, V. I. (March 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. Дата обращения: 30 июля 2020.
- ↑ 1 2 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.
- ↑ 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.
- ↑ 1 2 3 4 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
{{citation}}
: Указан более чем один параметр|DOI=
and|doi=
(). 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
{{citation}}
: Указан более чем один параметр|DOI=
and|doi=
(). - Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), "On fiber diameters of continuous maps".