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

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

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

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

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

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

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

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

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

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

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