Лемма о малом искажении

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

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

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

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

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

( 1 − ε ) ⋅ ‖ u − v ‖ 2 ≤ ‖ f ( u ) − f ( v ) ‖ 2 ≤ ( 1 + ε ) ⋅ ‖ u − v ‖ 2 {displaystyle (1-varepsilon )cdot |u-v|^{2}leq |f(u)-f(v)|^{2}leq (1+varepsilon )cdot |u-v|^{2}}

для всех u , v ∈ X {displaystyle u,vin X} .

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

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

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

Альтернативная формулировка

Родственной леммой является лемма Джонсона — Линденштрауса о распределении. Эта дистрибутивная лемма утверждает, что для любого 0 < ε, δ < 1/2 и положительного целого числа d существует распределение Rk × d, из которого извлекается матрица A так, что для k = O(ε−2log(1/δ)) и для любого вектора единичной длины x ∈ Rd верно следующее утверждение

P ( | ‖ A x ‖ 2 2 − 1 | > ε ) < δ {displaystyle P(|Vert AxVert _{2}^{2}-1|>varepsilon )<delta }

Соответствующие матрицы A получили название матриц Джонсона — Линденштрауса (англ. JL matrices). По сути, данная лемма характеризует точность аппроскимации матричной проекции многомерного распределения.

Связь дистрибутивной версии леммы с её исходным эквивалентом можно получить, если задать x = ( u − v ) / ‖ u − v ‖ 2 {displaystyle x=(u-v)/|u-v|_{2}} и δ < 1 / n 2 {displaystyle delta <1/n^{2}} для некоторой пары u,v в X.

Возможность получения проекций меньшей размерности является очень важным результатом указанных лемм, однако необходимо, чтобы такие проекции можно было получить за минимальное время. Фигурирующая в дистрибутивной лемме операция умножения матрицы A на вектор x занимает время O(kd). Поэтому был проведен ряд исследований по получению распределений, для которых матрично-векторное произведение может быть вычислено быстрее, чем за время O(kd).

В частности, Эйлоном и Бернаром Шазелем в 2006 году было введено так называемое быстрое преобразование Джонсона — Линденштрауса (БПДЛ), которое позволяет вычислять матрично-векторное произведение за время d log ⁡ d + k 2 + γ {displaystyle dlog d+k^{2+gamma }} для любой константы γ > 0 {displaystyle gamma >0} .

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

Тензорные проекции многомерных пространств

Для представления тензорных проекций, используемых в БПДЛ в многомерном случае, в виде комбинации двух JL-матриц с одинаковым количеством строк, может быть использовано торцевое произведение (англ. face-splitting product), предложенное в 1996 году Слюсарем В.И..

Рассмотрим две JL-матрицы проекций многомерного пространства: C ∈ R 3 × 3 {displaystyle {C}in mathbb {R} ^{3 imes 3}} и D ∈ R 3 × 3 {displaystyle {D}in mathbb {R} ^{3 imes 3}} . Их торцевое произведение C ∙ D {displaystyle {C}ullet {D}} имеет вид:

C ∙ D = [ C 1 ⊗ D 1 C 2 ⊗ D 2 C 3 ⊗ D 3 ] . {displaystyle {C}ullet {D}=left[{egin{array}{c }{C}_{1}otimes {D}_{1}hline {C}_{2}otimes {D}_{2}hline {C}_{3}otimes {D}_{3}end{array}} ight].}

JL-матрицы, определённые таким образом, используют меньше случайных бит и могут быстро умножаться на векторы с тензорной структурой, благодаря следующему тождеству:

( C ∙ D ) ( x ⊗ y ) = C x ∘ D y = [ ( C x ) 1 ( D y ) 1 ( C x ) 2 ( D y ) 2 ⋮ ] {displaystyle (mathbf {C} ullet mathbf {D} )(xotimes y)=mathbf {C} xcirc mathbf {D} y=left[{egin{array}{c }(mathbf {C} x)_{1}(mathbf {D} y)_{1}(mathbf {C} x)_{2}(mathbf {D} y)_{2}vdots end{array}} ight]} ,

где ∘ {displaystyle circ } - поэлементное произведение Адамара.

Переход от проецирующей матрицы A к торцевому произведению позволяет заменить исходное умножение на произведение Адамара, оперирующее матрицами меньшей размерности. В указанном контексте идея торцевого произведения была использована в 2010 для решения задачи дифференциальной приватности (англ. differential privacy). Кроме того, аналогичные вычисления были применены для эффективной реализации ядерного метода и во многих других алгоритмах линейной алгебры.

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

Если матрицы C 1 , C 2 , … , C c {displaystyle C_{1},C_{2},dots ,C_{c}} являются независимыми, содержащими элементы ± 1 {displaystyle pm 1} , или гауссовыми матрицами, то объединённая матрица C 1 ∙ ⋯ ∙ C c {displaystyle C_{1}ullet dots ullet C_{c}} соответствует лемме Джонсона-Линденштрауса о распределении, если число строк не меньше

O ( ϵ − 2 log ⁡ 1 / δ + ϵ − 1 ( 1 c log ⁡ 1 / δ ) c ) {displaystyle O(epsilon ^{-2}log 1/delta +epsilon ^{-1}({ frac {1}{c}}log 1/delta )^{c})} .

Для больших ϵ {displaystyle epsilon } дистрибутивная лемма Джонсона-Линденштрауса выполняется строго, при этом нижняя граница ошибки аппроксимации имеет экспоненциальную зависимость ( log ⁡ 1 / δ ) c {displaystyle (log 1/delta )^{c}} . Предлагаются альтернативные конструкции JL-матриц, чтобы обойти это органичение.