Лемма Джонсона – Линденштрауса - Johnson–Lindenstrauss lemma

В математике Лемма Джонсона – Линденштрауса результат назван в честь Уильям Б. Джонсон и Иорам Линденштраус относительно низкого искажения вложения точек из многомерных в низкоразмерные Евклидово пространство. Лемма утверждает, что набор точек в пространстве большой размерности может быть вложен в пространство гораздо меньшей размерности таким образом, чтобы расстояния между точками были равны почти сохранился. Карта, используемая для вложения, не менее Липшиц, и даже может считаться ортогональная проекция.

Лемма имеет приложения в сжатое зондирование, многообразное обучение, уменьшение размерности, и вложение графа. Большая часть данных, которые хранятся и обрабатываются на компьютерах, включая текст и изображения, могут быть представлены в виде точек в многомерном пространстве (см. векторная космическая модель в случае текста). Однако основные алгоритмы работы с такими данными, как правило, очень быстро срабатывают по мере увеличения размеров.^[1] Поэтому желательно уменьшить размерность данных таким образом, чтобы сохранить их соответствующую структуру. Лемма Джонсона – Линденштрауса является классическим результатом в этом ключе.

Кроме того, лемма точна с точностью до постоянного множителя, т.е. существует набор точек размера м это требует измерения

${\displaystyle \Omega \left({\frac {\log(m)}{\varepsilon ^{2}}}\right)}$

чтобы сохранить расстояния между всеми парами точек в пределах ${\displaystyle (1\pm \varepsilon )}$.^[2]

Лемма

Данный ${\displaystyle 0<\varepsilon <1}$, множество ${\displaystyle X}$ из ${\displaystyle m}$ указывает в ${\displaystyle \mathbb {R} ^{N}}$, и число ${\displaystyle n>8\ln(m)/\varepsilon ^{2}}$, есть линейная карта ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}}$ такой, что

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

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

Формулу можно переставить:

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

Одно доказательство леммы требует ƒ быть подходящим кратным ортогональной проекции на случайное подпространство размерности ${\displaystyle n}$ в ${\displaystyle \mathbb {R} ^{N}}$, и использует феномен концентрация меры.

Очевидно, что ортогональная проекция, как правило, уменьшает среднее расстояние между точками, но лемму можно рассматривать как имеющую отношение к относительные расстояния, которые не меняются при масштабировании. Вкратце, вы бросаете кости и получаете случайную проекцию, которая уменьшит среднее расстояние, а затем вы увеличиваете расстояния, чтобы среднее расстояние вернулось к своему прежнему значению. Если вы продолжите бросать кости, вы за полиномиальное случайное время найдете проекцию, для которой (масштабированные) расстояния удовлетворяют лемме.

Альтернативное заявление

Родственная лемма - это лемма о распределении JL. Эта лемма утверждает, что для любого 0 <ε, δ <1/2 и положительное целое число d, существует распределение по р^{k × d} из которой матрица А нарисован так, что для k = О(ε⁻²журнал (1 /δ)) и для любого вектора единичной длины Икс ∈ р^d, справедливо следующее утверждение.^[3]

${\displaystyle P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta }$

Лемму JL можно получить из дистрибутивной версии, задав ${\displaystyle x=(u-v)/\|u-v\|_{2}}$ и ${\displaystyle \delta <1/n^{2}}$ для какой-то пары ты,v оба в Икс. Тогда лемма JL следует объединением всех таких пар.

Ускорение преобразования JL

Данный А, вычисление матричного векторного произведения принимает О(kd) время. Была проделана некоторая работа по получению распределений, для которых матричное векторное произведение может быть вычислено менее чем за О(kd) время.

Есть два основных направления работы. Первый, Быстрое преобразование Джонсона-Линденштрауса (FJLT),^[4] был представлен Эйлоном и Chazelle в 2006 г. Этот метод позволяет вычислить матричное векторное произведение всего за ${\displaystyle d\log d+k^{2+\gamma }}$ для любой постоянной ${\displaystyle \gamma >0}$.

Другой подход - построить распределение, поддерживаемое разреженными матрицами.^[5]Этот метод позволяет сохранить только ${\displaystyle \varepsilon }$ доля записей в матрице, что означает, что вычисление может быть выполнено всего за ${\displaystyle kd\varepsilon }$ время. Кроме того, если вектор имеет только ${\displaystyle b}$ ненулевые записи, Sparse JL требует времени ${\displaystyle kb\varepsilon }$, что может быть намного меньше, чем ${\displaystyle d\log d}$ время, используемое Fast JL.

Тензорные случайные проекции

Можно объединить две матрицы JL, взяв так называемые Продукт для разделения лиц определяется как тензорное произведение строк (было предложено В. Слюсарь^[6] в 1996 г.^{[7][8][9][10][11]} за радар и цифровая антенная решетка приложения) .Подробнее, пусть ${\displaystyle {C}\in \mathbb {R} ^{3\times 3}}$ и ${\displaystyle {D}\in \mathbb {R} ^{3\times 3}}$ - две матрицы. Продукт для разделения лиц ${\displaystyle {C}\bullet {D}}$ является^{[7][8][9][10][11]}

${\displaystyle {C}\bullet {D}=\left[{\begin{array}{c }{C}_{1}\otimes {D}_{1}\\\hline {C}_{2}\otimes {D}_{2}\\\hline {C}_{3}\otimes {D}_{3}\\\end{array}}\right].}$

Эту идею тензоризации использовали Kasiviswanathan et al. 2010 г.^[12] за дифференциальная конфиденциальность.

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

${\displaystyle (\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right]}$,

куда ${\displaystyle \circ }$ поэлементно (Адамар ) продукт. Такие вычисления были использованы для эффективного вычисления полиномиальные ядра и многие другие алгоритмы линейной алгебры.^[13]

В 2020 году^[14] было показано, что если матрицы ${\displaystyle C_{1},C_{2},\dots ,C_{c}}$ независимы ${\displaystyle \pm 1}$ или гауссовых матриц, комбинированная матрица ${\displaystyle C_{1}\bullet \dots \bullet C_{c}}$ удовлетворяет распределительной лемме JL, если количество строк не менее

${\displaystyle O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$.

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

Смотрите также

• Случайная проекция

Примечания

1. Например, писать о поиск ближайшего соседа в многомерных наборах данных, Джон Кляйнберг пишет: "Более сложные алгоритмы обычно достигают времени запроса, которое логарифмически в п за счет экспоненциальной зависимости от размерности d; действительно, даже средний случайный анализ эвристик, таких как k-d деревья, показывает экспоненциальную зависимость от d во время запроса. Клейнберг, Джон М. (1997), "Два алгоритма поиска ближайшего соседа в больших измерениях", Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений, STOC '97, Нью-Йорк, Нью-Йорк, США: ACM, стр. 599–608, Дои:10.1145/258533.258653, ISBN  0-89791-888-6.
2. Каспер Грин Ларсен; Джелани Нельсон (2017). Оптимальность леммы Джонсона-Линденштрауса. Материалы 58-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS). п. 633-638. arXiv:1609.02094. Дои:10.1109 / FOCS.2017.64.
3. Джонсон, Уильям Б.; Линденштраус, Иорам (1984). «Расширения липшицевых отображений в гильбертово пространство». В Билсе, Ричард; Бек, Анатоль; Беллоу, Александра; и другие. (ред.). Конференция по современному анализу и вероятности (Нью-Хейвен, штат Коннектикут, 1982). Современная математика. 26. Провиденс, Род-Айленд: Американское математическое общество. стр.189–206. Дои:10.1090 / conm / 026/737400. ISBN  0-8218-5030-X. МИСТЕР  0737400.
4. Айлон, Нир; Шазель, Бернар (2006). «Приближенные ближайшие соседи и быстрое преобразование Джонсона – Линденштрауса». Материалы 38-го ежегодного симпозиума ACM по теории вычислений. Нью-Йорк: ACM Press. С. 557–563. Дои:10.1145/1132516.1132597. ISBN  1-59593-134-1. МИСТЕР  2277181.
5. Кейн, Дэниел М .; Нельсон, Джелани (2014). "Преобразования Спарсера Джонсона-Линденштрауса". Журнал ACM. 61 (1): 1. arXiv:1012.1577. Дои:10.1145/2559902. МИСТЕР  3167920.. Предварительная версия статьи опубликована в Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 2012.
6. Анна Эстеве, Ева Бой и Хосеп Фортиана (2009): Условия взаимодействия в дистанционной регрессии, коммуникации в статистике - теория и методы, 38:19, стр. 3501 [1]
7. Слюсарь В. И. (27 декабря 1996 г.). «Конечные продукты в матрицах в радиолокационных приложениях» (PDF). Радиоэлектроника и системы связи.– 1998, Вып. 41; Число 3: 50–53.
8. Слюсарь, В. И. (20.05.1997). «Аналитическая модель цифровой антенной решетки на основе матричных продуктов расщепления граней» (PDF). Proc. ICATT-97, Киев: 108–109.
9. Слюсарь, В. И. (15.09.1997). «Новые операции матричного продукта для приложений радаров» (PDF). Proc. Прямые и обратные задачи теории электромагнитных и акустических волн (ДИПЭД-97), Львов.: 73–74.
10. Слюсарь В. И. (13 марта 1998 г.). «Семейство граней произведений матриц и его свойства» (PDF). Кибернетика и системный анализ К / К Кибернетика и Системный анализ.- 1999.. 35 (3): 379–384. Дои:10.1007 / BF02733426.
11. Слюсарь В. И. (2003). «Обобщенные лицевые произведения матриц в моделях цифровых антенных решеток с неодинаковыми каналами» (PDF). Радиоэлектроника и системы связи. 46 (10): 9–17.
12. Касивисванатан, Шива Прасад и др. «Цена частного выпуска таблиц непредвиденных обстоятельств и спектров случайных матриц с коррелированными строками». Материалы сорок второго симпозиума ACM по теории вычислений. 2010 г.
13. Вудрафф, Дэвид П. «Создание эскизов как инструмент численной линейной алгебры». Теоретическая информатика 10.1-2 (2014): 1-157.
14. Ахле, Томас; Капралов, Михаил; Кнудсен, Якоб; Паг, Расмус; Велингкер, Амея; Вудрафф, Дэвид; Зандие, Амир (2020). Забывчивые наброски полиномиальных ядер высокой степени. Симпозиум ACM-SIAM по дискретным алгоритмам. Ассоциация вычислительной техники. Дои:10.1137/1.9781611975994.9.

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

• Ахлиоптас, Димитрис (2003), "Удобные для базы данных случайные проекции: Джонсон – Линденштраус с бинарными монетами", Журнал компьютерных и системных наук, 66 (4): 671–687, Дои:10.1016 / S0022-0000 (03) 00025-4, МИСТЕР  2005771. Журнальная версия статьи, ранее представленной на PODC 2001.
• Баранюк Ричард; Дэвенпорт, Марк; Деворе, Рональд; Вакин, Майкл (2008), «Простое доказательство свойства ограниченной изометрии для случайных матриц» (PDF), Конструктивная аппроксимация, 28 (3): 253–263, Дои:10.1007 / s00365-007-9003-х, МИСТЕР  2453366^{[постоянная мертвая ссылка ]}.
• Дасгупта, Санджой; Гупта, Анупам (2003), «Элементарное доказательство теоремы Джонсона и Линденштрауса» (PDF), Случайные структуры и алгоритмы, 22 (1): 60–65, Дои:10.1002 / rsa.10073, МИСТЕР  1943859.
• Ландвебер, Питер; Лазар, Эмануэль; Патель, Нил (2015), "О диаметрах волокон непрерывных отображений ".
• Слюсарь, В. И. (20.05.1997). «Аналитическая модель цифровой антенной решетки на основе матричных продуктов расщепления граней» (PDF). Proc. ICATT-97, Киев: 108–109.
• Слюсарь В. И. (13 марта 1998 г.). «Семейство граней произведений матриц и его свойства» (PDF). Кибернетика и системный анализ К / К Кибернетика и Системный анализ.- 1999.. 35 (3): 379–384. Дои:10.1007 / BF02733426.