Лемма Джонсона – Линденштрауса.

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

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

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

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

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

Лемма

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

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

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

Формулу можно переставить: $(1+\varepsilon )^{-1}\|f(u)-f(v)\|^{2}\leq \|u-v\|^{2}\leq (1-\varepsilon )^{-1}\|f(u)-f(v)\|^{2}$

Альтернативно, для любого $\epsilon \in (0,1)$ и любое целое число $n\geq 15(\ln m)/\varepsilon ^{2}$ ^{[Примечание 1]} существует линейная функция $f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}$ такое, что ограничение $f|_{X}$ является $(1+\varepsilon )$ - билипшиц . ^{[Примечание 2]}

Классическое доказательство леммы предполагает, что ƒ является скаляром, кратным ортогональной проекции. $P$ на случайное подпространство размерности $n$ в $\mathbb {R} ^{N}$ . Ортогональная проекция сжимает некоторые измерения пространства, к которому она применяется, что уменьшает длину всех векторов, а также расстояние между векторами в пространстве. В условиях леммы концентрация меры обеспечивает ненулевую вероятность того, что случайная ортогональная проекция уменьшит попарные расстояния между всеми точками в $X$ примерно с постоянным коэффициентом $c$ . Поскольку вероятность не равна нулю, такие проекции должны существовать, поэтому мы можем выбрать одну $P$ и установить $f(v)=Pv/c$ .

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

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

Связанная с ней лемма — это лемма JL о распределении. Эта лемма утверждает, что для любого $0<\varepsilon ,\delta <1/2$ и положительное целое число $d$ , существует распределение по $\mathbb {R} ^{k\times d}$ из которого матрица $A$ нарисовано так, что для $k=O(\varepsilon ^{-2}\log(1/\delta ))$ и для любого вектора единичной длины $x\in \mathbb {R} ^{d}$ , то утверждение ниже справедливо. ^[5]

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

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

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

Учитывая A , вычисление произведения матрицы-вектора занимает $O(kd)$ время. Была проведена некоторая работа по получению распределений, для которых произведение матрицы-вектора можно вычислить менее чем за $O(kd)$ время.

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

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

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

Объединить две матрицы JL можно, взяв так называемое произведение граней , которое определяется как тензорное произведение строк (предложено В. Слюсарем ^[8] в 1996 году ^[9]^[10]^[11]^[12]^[13] для радаров и цифровых антенных решеток ).Более прямо, пусть ${C}\in \mathbb {R} ^{3\times 3}$ и ${D}\in \mathbb {R} ^{3\times 3}$ быть две матрицы.Тогда продукт, расщепляющий лицо ${C}\bullet {D}$ является ^[9]^[10]^[11]^[12]^[13]

{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].

Эту идею тензоризации использовали Касивисванатан и др. для дифференциальной конфиденциальности . ^[14]

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

(\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]

,

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

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

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

.

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

См. также

Примечания

^ Или любое целое число $n>128(\ln m)/(9\varepsilon ^{2}).$
^ Этот результат следует из приведенного выше результата. Схема доказательства: Примечание. $1/(1+\varepsilon )<{\sqrt {1-3\varepsilon /4}}$ и ${\sqrt {1+3\varepsilon /4}}<{\sqrt {1+\varepsilon }}<1+\varepsilon$ для всех $\varepsilon \in (0,1)$ . Выполните анализ для 1= m и 1< m , применив приведенный выше результат к $3\varepsilon /4$ в последнем случае, отметив $128/9<15.$

Ссылки

^ Например, описывая поиск ближайшего соседа в многомерных наборах данных, Джон Кляйнберг пишет: «Более сложные алгоритмы обычно достигают логарифмического по n времени запроса за счет экспоненциальной зависимости от размерности d ; действительно, даже Анализ среднего случая эвристик, таких как деревья kd, обнаруживает экспоненциальную зависимость от d во времени запроса. Кляйнберг, Джон М. (1997), «Два алгоритма поиска ближайших соседей в больших измерениях», Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений , STOC '97, Нью-Йорк, Нью-Йорк, США: ACM, стр. . 599–608, номер домена : 10.1145/258533.258653 , ISBN. 0-89791-888-6 .
^ Ларсен, Каспер Грин; Нельсон, Джелани (2017), «Оптимальность леммы Джонсона-Линденштрауса», Труды 58-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS) , стр. 633–638, arXiv : 1609.02094 , doi : 10.1109/FOCS.2017.64 , S2CID 16745
^ Нильсен, Франк (2016), «10. Быстрая аппроксимационная оптимизация в больших размерностях с использованием базовых наборов и быстрое уменьшение размерностей» , Введение в HPC с MPI для науки о данных , Springer, стр. 259–272, ISBN 978-3-319-21903-5
^ Фернандес-Гранда, Карлос. «Конспекты лекций 5: Случайные прогнозы» (PDF) . п. 6. Лемма 2.6 (лемма Джонсона-Линденштрауса)
^ Джонсон, Уильям Б .; Линденштраусс, Йорам (1984), «Расширения липшицевых отображений в гильбертово пространство», в Билсе, Ричарде; Бек, Анатоль; Беллоу, Александра; и др. (ред.), Конференция по современному анализу и вероятности (Нью-Хейвен, Коннектикут, 1982) , Современная математика, том. 26, Провиденс, Род-Айленд: Американское математическое общество, стр. 189–206 , doi : 10.1090/conm/026/737400 , ISBN 0-8218-5030-Х , МР 0737400 , S2CID 117819162
^ Эйлон, Нир; Шазель, Бернар (2006), «Приблизительные ближайшие соседи и быстрое преобразование Джонсона – Линденштрауса», Труды 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM Press, стр. 557–563, doi : 10.1145/1132516.1132597 , ISBN 1-59593-134-1 , МР 2277181 , S2CID 490517
^ Кейн, Дэниел М.; Нельсон, Джелани (2014), «Разреженные преобразования Джонсона-Линденштрауса», Журнал ACM , 61 (1): 1, arXiv : 1012.1577 , doi : 10.1145/2559902 , MR 3167920 , S2CID 7821848 . Предварительная версия этой статьи была опубликована в Трудах двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , 2012.
^ Эстев, Анна; Бой, Ева; Фортиана, Хосеп (2009), «Условия взаимодействия в регрессии на основе расстояния», Communications in Статистика , 38 (18–20): 3498–3509, doi : 10.1080/03610920802592860 , MR 2589790 , S2CID 122303508
^ Jump up to: ^а ^б Слюсарь В.И. (27 декабря 1996 г.), "Конечные продукты в матрицах в радиолокационных приложениях". (PDF) , Радиоэлектроника и системы связи , 41 (3): 50–53
^ Jump up to: ^а ^б Слюсарь В.И. (20 мая 1997 г.), "Аналитическая модель цифровой антенной решетки на основе матричных произведений лицевого разделения". (PDF) , Учеб. ICATT-97, Киев : 108–109.
^ Jump up to: ^а ^б ^с Слюсарь, В.И. (15 сентября 1997 г.), "Новые операции матричного произведения для применения в радиолокации" (PDF) , Учеб. Прямые и обратные задачи теории электромагнитных и акустических волн (ДИПЕД-97), Львов. : 73–74
^ Jump up to: ^а ^б Слюсарь В.И. (13 марта 1998 г.), "Семейство граничных произведений матриц и его свойства" (PDF) , Кибернетика и системный анализ К/К Кибернетика и Системный анализ.- 1999. , 35 (3): 379– 384, номер документа : 10.1007/BF02733426 , S2CID 119661450
^ Jump up to: ^а ^б Слюсарь, В.И. (2003), "Обобщенные грани-произведения матриц в моделях цифровых антенных решеток с неидентичными каналами" (PDF) , Радиоэлектроника и системы связи , 46 (10): 9–17
^ Касивишванатан, Шива Прасад; Рудельсон, Марк; Смит, Адам Д.; Уллман, Джонатан Р. (2010), «Цена частного выпуска таблиц непредвиденных обстоятельств и спектров случайных матриц с коррелированными строками», в Шульман, Леонард Дж. (ред.), Труды 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5–8 июня 2010 г., Ассоциация вычислительной техники, стр. 775–784, doi : 10.1145/1806689.1806795 , S2CID 5714334
^ Вудрафф, Дэвид П. (2014), Эскизы как инструмент числовой линейной алгебры , Основы и тенденции в теоретической информатике, том. 10, arXiv : 1411.4357 , doi : 10.1561/0400000060 , MR 3285427 , S2CID 51783444
^ Але, Томас; Капралов, Михаил; Кнудсен, Якоб; Паг, Расмус ; Велинкер, Амейя; Вудрафф, Дэвид; Занди, Амир (2020), «Забывчивое набросок полиномиальных ядер высокой степени», Симпозиум ACM-SIAM по дискретным алгоритмам , Ассоциация вычислительной техники, arXiv : 1909.01410 , doi : 10.1137/1.9781611975994.9

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

Ахлиоптас, Димитрис (2003), «Случайные проекции, удобные для баз данных: Джонсон – Линденштраусс с двоичными монетами», Journal of Computer and System Sciences , 66 (4): 671–687, doi : 10.1016/S0022-0000(03)00025- 4 , МР 2005771 . Журнальная версия статьи, ранее публиковавшейся на PODC 2001.
Баранюк, Ричард ; Давенпорт, Марк; ДеВор, Рональд ; Вакин, Майкл (2008), «Простое доказательство свойства ограниченной изометрии для случайных матриц», Constructive Approximation , 28 (3): 253–263, doi : 10.1007/s00365-007-9003-x , hdl : 1911/21683 , МР 2453366 , S2CID 15911073 .
Дасгупта, Санджой; Гупта, Анупам (2003), «Элементарное доказательство теоремы Джонсона и Линденштрауса» (PDF) , Случайные структуры и алгоритмы , 22 (1): 60–65, doi : 10.1002/rsa.10073 , MR 1943859 , S2CID 10327785 .
Ландвебер, Питер ; Лазар, Эмануэль А.; Патель, Нил (2016), «О диаметрах волокон непрерывных карт», American Mathematical Monthly , 123 (4): 392–397, arXiv : 1503.07597 , doi : 10.4169/amer.math.monthly.123.4.392 , S2CID 51751732
Слюсарь В.И. (20 мая 1997 г.), "Аналитическая модель цифровой антенной решетки на основе матричных произведений лицевого разделения". (PDF) , Учеб. ICATT-97, Киев : 108–109.
Слюсарь В.И. (13 марта 1998 г.), "Семейство граничных произведений матриц и его свойства" (PDF) , Кибернетика и системный анализ К/К Кибернетика и Системный анализ.- 1999. , 35 (3): 379– 384, номер документа : 10.1007/BF02733426 , S2CID 119661450 .
Лекция № 4 «Современный алгоритмический набор инструментов: уменьшение размерности» (PDF) , 2023 г.

[5] Или любое целое число $n>128(\ln m)/(9\varepsilon ^{2}).$

[6] Этот результат следует из приведенного выше результата. Схема доказательства: Примечание. $1/(1+\varepsilon )<{\sqrt {1-3\varepsilon /4}}$ и ${\sqrt {1+3\varepsilon /4}}<{\sqrt {1+\varepsilon }}<1+\varepsilon$ для всех $\varepsilon \in (0,1)$ . Выполните анализ для 1= m и 1< m , применив приведенный выше результат к $3\varepsilon /4$ в последнем случае, отметив $128/9<15.$

[1] Например, описывая поиск ближайшего соседа в многомерных наборах данных, Джон Кляйнберг пишет: «Более сложные алгоритмы обычно достигают логарифмического по n времени запроса за счет экспоненциальной зависимости от размерности d ; действительно, даже Анализ среднего случая эвристик, таких как деревья kd, обнаруживает экспоненциальную зависимость от 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 , doi : 10.1109/FOCS.2017.64 , S2CID 16745

[3] Нильсен, Франк (2016), «10. Быстрая аппроксимационная оптимизация в больших размерностях с использованием базовых наборов и быстрое уменьшение размерностей» , Введение в HPC с MPI для науки о данных , Springer, стр. 259–272, ISBN 978-3-319-21903-5

[4] Фернандес-Гранда, Карлос. «Конспекты лекций 5: Случайные прогнозы» (PDF) . п. 6. Лемма 2.6 (лемма Джонсона-Линденштрауса)

[7] Джонсон, Уильям Б .; Линденштраусс, Йорам (1984), «Расширения липшицевых отображений в гильбертово пространство», в Билсе, Ричарде; Бек, Анатоль; Беллоу, Александра; и др. (ред.), Конференция по современному анализу и вероятности (Нью-Хейвен, Коннектикут, 1982) , Современная математика, том. 26, Провиденс, Род-Айленд: Американское математическое общество, стр. 189–206 , doi : 10.1090/conm/026/737400 , ISBN 0-8218-5030-Х , МР 0737400 , S2CID 117819162

[8] Эйлон, Нир; Шазель, Бернар (2006), «Приблизительные ближайшие соседи и быстрое преобразование Джонсона – Линденштрауса», Труды 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM Press, стр. 557–563, doi : 10.1145/1132516.1132597 , ISBN 1-59593-134-1 , МР 2277181 , S2CID 490517

[9] Кейн, Дэниел М.; Нельсон, Джелани (2014), «Разреженные преобразования Джонсона-Линденштрауса», Журнал ACM , 61 (1): 1, arXiv : 1012.1577 , doi : 10.1145/2559902 , MR 3167920 , S2CID 7821848 . Предварительная версия этой статьи была опубликована в Трудах двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , 2012.

[Fortiana-10] Эстев, Анна; Бой, Ева; Фортиана, Хосеп (2009), «Условия взаимодействия в регрессии на основе расстояния», Communications in Статистика , 38 (18–20): 3498–3509, doi : 10.1080/03610920802592860 , MR 2589790 , S2CID 122303508

[slyusar-11] Jump up to: ^а ^б Слюсарь В.И. (27 декабря 1996 г.), "Конечные продукты в матрицах в радиолокационных приложениях". (PDF) , Радиоэлектроника и системы связи , 41 (3): 50–53

[slyusar1-12] Jump up to: ^а ^б Слюсарь В.И. (20 мая 1997 г.), "Аналитическая модель цифровой антенной решетки на основе матричных произведений лицевого разделения". (PDF) , Учеб. ICATT-97, Киев : 108–109.

[DIPED-13] Jump up to: ^а ^б ^с Слюсарь, В.И. (15 сентября 1997 г.), "Новые операции матричного произведения для применения в радиолокации" (PDF) , Учеб. Прямые и обратные задачи теории электромагнитных и акустических волн (ДИПЕД-97), Львов. : 73–74

[slyusar2-14] Jump up to: ^а ^б Слюсарь В.И. (13 марта 1998 г.), "Семейство граничных произведений матриц и его свойства" (PDF) , Кибернетика и системный анализ К/К Кибернетика и Системный анализ.- 1999. , 35 (3): 379– 384, номер документа : 10.1007/BF02733426 , S2CID 119661450

[general-15] Jump up to: ^а ^б Слюсарь, В.И. (2003), "Обобщенные грани-произведения матриц в моделях цифровых антенных решеток с неидентичными каналами" (PDF) , Радиоэлектроника и системы связи , 46 (10): 9–17

[16] Касивишванатан, Шива Прасад; Рудельсон, Марк; Смит, Адам Д.; Уллман, Джонатан Р. (2010), «Цена частного выпуска таблиц непредвиденных обстоятельств и спектров случайных матриц с коррелированными строками», в Шульман, Леонард Дж. (ред.), Труды 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5–8 июня 2010 г., Ассоциация вычислительной техники, стр. 775–784, doi : 10.1145/1806689.1806795 , S2CID 5714334

[woodruff-17] Вудрафф, Дэвид П. (2014), Эскизы как инструмент числовой линейной алгебры , Основы и тенденции в теоретической информатике, том. 10, arXiv : 1411.4357 , doi : 10.1561/0400000060 , MR 3285427 , S2CID 51783444

[highdeg-18] Але, Томас; Капралов, Михаил; Кнудсен, Якоб; Паг, Расмус ; Велинкер, Амейя; Вудрафф, Дэвид; Занди, Амир (2020), «Забывчивое набросок полиномиальных ядер высокой степени», Симпозиум ACM-SIAM по дискретным алгоритмам , Ассоциация вычислительной техники, arXiv : 1909.01410 , doi : 10.1137/1.9781611975994.9

[1]

[2]

[3]

[4]

[Примечание 1]

[Примечание 2]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]