WikiSort.ru - Не сортированное

Лемма о малом искажении (также известна как лемма Джонсона — Линденштрауса) утверждает, что множество из ${\displaystyle n}$ точек многомерного пространства можно отобразить в пространство размерности гораздо ниже ${\displaystyle n}$ таким образом, что расстояния между точками останутся почти без изменений. При этом такое отображение можно найти среди ортогональных проекций.

Лемма позволяет сжимать данные представляющиеся точками многомерного пространства, и, что более важно, сократить число размерностей данных без существенной потери информации.

Лемма была доказана Вильямом Джонсоном^[en] и Йорамом Линденштраусом^[en].^[1]

Формулировка

Пусть ${\displaystyle 0<\varepsilon <1}$ . Тогда для любого множества ${\displaystyle X}$ из ${\displaystyle n}$ точек в ${\displaystyle \mathbb {R} ^{N}}$ и  ${\displaystyle m>{\tfrac {8\cdot \ln n}{\varepsilon ^{2}}}}$ существует линейное отображение ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{m}}$ такое, что

${\displaystyle (1-\varepsilon )\cdot \|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\cdot \|u-v\|^{2}}$

для всех ${\displaystyle u,v\in X}$ .

Более того случайная ортогональная проекция ${\displaystyle f}$ на ${\displaystyle m}$ -мерное подпространство удовлетворяет условию с положительной вероятностью.

О доказательствах

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

Примечания

Дальнейшее чтение

• 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.
• Baraniuk, Richard; Davenport, Mark; DeVore, Ronald & Wakin, Michael (2008), "A simple proof of the restricted isometry property for random matrices", Constructive Approximation Т. 28 (3): 253–263, doi:10.1007/s00365-007-9003-x, <http://dsp.rice.edu/files/cs/JL_RIP.pdf>  (недоступная ссылка).
• Dasgupta, Sanjoy & Gupta, Anupam (2003), "An elementary proof of a theorem of Johnson and Lindenstrauss", Random Structures & Algorithms Т. 22 (1): 60–65, doi:10.1002/rsa.10073, <http://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf> .
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), "On fiber diameters of continuous maps".