Обсуждение: Фактор растяжения

Терминология: Искажение

Я думаю, нам следует удалить термин «искажение» из статьи, так как он используется во многих разных значениях, иногда в более конкретном контексте, чем наш. (Например, предполагая, что f является инъективным.)

• Согласно Бураго и др. (2001), ^{[1] : стр} . ^{249, определение 7.1.4,} искажение f равно Следуя Вербику и Субхашу (2016), ^[2], мы могли бы назвать эту величину аддитивным искажением , чтобы отличать ее от мультипликативного искажения, определенного ниже. ${\displaystyle \operatorname {dis} f=\sup _{x,y\in X}|d(f(x),f(y))-d(x,y)|.}$
• Согласно Nayyeri & Raichel (2019), [ ^3] если f инъективно (так что мы можем говорить о ), то искажение f равно Nayyeri & Raichel интересно используют термины расширение для и сжатие для Albiac & Kalton (2016) ^[4] называют одну и ту же величину константой искажения (а не искажением ) f и используют обозначение , хотя они также заранее предполагают, что и оба являются липшицевыми. (Они называют такие f липшицевыми вложениями. ) Следуя Verbeek & Subhash (2016), ^[2] мы могли бы назвать эту величину мультипликативным искажением , чтобы отличать ее от аддитивного искажения, определенного выше. (Громов (1983) использует обозначение ^{[5] : стр. 113} ) ${\displaystyle f^{-1}:f^{\text{img}}(X)\to X}$ ${\displaystyle \operatorname {Lip} (f)\operatorname {Lip} (f^{-1}).}$ ${\displaystyle \operatorname {Lip} (f)}$ ${\displaystyle \operatorname {Lip} (f^{-1}).}$ ${\displaystyle \operatorname {dist} (f),}$ ${\displaystyle f}$ ${\displaystyle f^{-1}}$ ${\displaystyle \operatorname {Distor} (f).}$
• Для данного вещественного числа Деза и Деза (2014) ^[6] говорят , что f является C-билипшицевым, чтобы иметь в виду (Ср. Деза и Лоран (1997) ^{[7] : Определение 10.1.1} и Индик и др. (2017). ^{[8] [примечание 1]} ) Они определяют искажение f как «наименьшее C, для которого f является C -билипшицевым». Я думаю, что это определение согласуется с приведенным выше определением. (Я не проверял детали, но я думаю, что мы можем эквивалентно использовать , чтобы показать, что является таким и является наименьшим среди таких ^{[примечание 2]} ) ^{[примечание 3]} ${\displaystyle 1\leq C,}$ ${\displaystyle \exists r\in \mathbb {R} _{>0}\forall x,y\in X\quad rd(x,y)\leq d(fx,fy)\leq Crd(x,y).}$ ${\displaystyle r=1/\operatorname {Lip} (f^{-1})}$ ${\displaystyle \operatorname {Lip} (f)\operatorname {Lip} (f^{-1})}$ ${\displaystyle C}$ ${\displaystyle C.}$
• Сидиропулос и др. (2019) ^[9] используют термин искажение точно так же, как в статье в настоящее время, хотя и только для особого случая ( f, обладающего свойством , (они рассматривают только графы конечного порядка), и (?) («линия»)). Однако, учитывая существование множества других значений искажения (даже в контексте величин, назначаемых функциям между двумя метрическими пространствами) и доступность существующей терминологии ( коэффициент растяжения , константа Липшица , дилатация , расширение ), мало причин, по которым мы должны следовать их примеру. ${\displaystyle \forall x,y\in X\quad d(x,y)\leq d(fx,fy)}$ ${\displaystyle |X|<\aleph _{0}}$ ${\displaystyle Y\subseteq \mathbb {R} }$

Thatsme314 ( обсуждение ) 06:49, 3 июня 2022 (UTC) [ ответить ]

Ссылки

1. Бураго, Дмитрий; Бураго, Юрий; Иванов, Сергей (2001). Курс метрической геометрии . Американское математическое общество. ISBN 0-8218-2129-6.
2. Verbeek, Kevin; Suri, Subhash (2016). «Метрическое вложение, гиперболическое пространство и социальные сети». Computational Geometry: Theory and Applications . 59 : 1–12. doi :10.1016/j.comgeo.2016.08.003.
3. Найери, Амир; Райхель, Бенджамин (2019). Просмотр колец дерева: вложения с минимальным искажением в деревья. Симпозиум ACM-SIAM по дискретным алгоритмам (SODA). стр. 2380–2399. doi :10.1137/1.9781611975482.146.
4. Albiac, Fernando; Kalton, Nigel J. (2016). Темы теории банахова пространства . Springer. стр. 366.
5. Громов, Михаил (1983). «Заполнение римановых многообразий». Журнал дифференциальной геометрии . 18 (1): 1-147. doi :10.4310/jdg/1214509283.
6. Деза, Мишель Мари; Деза, Елена (2014). Энциклопедия расстояний (третье изд.). Springer. С. 41–42.
7. Деза, Мишель Мари; Лоран, Моник (1997). Геометрия сечений и метрик . Springer. стр. 125. ISBN 0937-5511. {{cite book}}: Проверить |isbn=значение: длина ( помощь )
8. Indyk, Piotr; Matousek, Jiri; Sidiropoulos, Anastasio (2017). «Вложения с малым искажением конечных метрических пространств». В Goodman, Jacob E; O'Rourke, Joseph; Toth, Csaba D (ред.). Handbook of Discrete and Computational Geometry (3-е изд.). American Mathematical Society. стр. 211–231. ISBN 0-8218-0975-X.
9. Сидиропулос, Анастасиос; Бадою, Михай; Дхамдере, Кедар; Гупта, Анупам; Индик, Пиот; Рабинович Юрий; Раке, Харальд; Рави, Р. (2019). «Алгоритмы аппроксимации вложений с малыми искажениями в маломерные пространства». SIAM Journal по дискретной математике . 33 (1): 454–473. дои : 10.1137/17M1113527.

Примечания

1. Согласно Индику и др. (2017): Если Y — нормированное векторное пространство , то «мы обычно требуем r=1/c или r=1 ».
2. потому что если тогда и если тогда выбор различных дает ${\displaystyle 1\leq \operatorname {Lip} (f)\operatorname {Lip} (f^{-1})}$ ${\displaystyle |X|\leq 1}$ ${\displaystyle +\infty =\operatorname {Lip} (f)=\operatorname {Lip} (f^{-1})}$ ${\displaystyle 2\leq |X|}$ ${\displaystyle x,y\in X}$ ${\displaystyle 1={\frac {d(fx,fy)}{d(x,y)}}{\frac {d(x,y)}{d(fx,fy)}}\leq \operatorname {Lip} (f)\operatorname {Lip} (f^{-1}).}$
3. Примечание: Деза и Деза (2014) неверно оговаривают — например, если тогда по их соглашению мы имеем , которое не имеет наименьшего элемента. ${\displaystyle 1<C}$ ${\displaystyle |X|=1,}$ ${\displaystyle \{C\in \mathbb {R} _{>1}:f{\text{ is }}C{\text{-bi-Lipschitz}}\}=\mathbb {R} _{>1},}$

Вы смешиваете ссылки из совершенно разных литературных источников, приводя неубедительный аргумент о том, что люди в конкретной литературе используют этот термин непоследовательно. Что касается того, является ли это самой константой Липшица или ее произведением на обратную константу Липшица: это техническая особенность, используемая для того, чтобы избежать ограничения короткими или увеличивающими расстояние отображениями. Если вы нормализовали по обратной константе (что можно сделать, когда целевое пространство является евклидовым пространством или, по крайней мере, нормированным векторным пространством, как это обычно бывает в этом контексте), обратная константа тогда исчезнет из определения этого значения. — Дэвид Эппштейн ( обсуждение ) 07:01, 3 июня 2022 (UTC) [ ответить ]

Заметка для себя по материалу, написанному Матоусеком:

(2001) Вложение конечных метрических пространств в нормированные пространства (глава 15 в Лекциях по дискретной геометрии )

(20??) Обновленная версия вышеуказанной главы https://kam.mff.cuni.cz/~matousek/dg-nmetr.ps.gz (где-то между 24 августа 2007 г. и 26 декабря 2010 г., согласно поиску в Wayback Machine)

(2013) Конспект лекций по метрическим вложениям https://kam.mff.cuni.cz/~matousek/ba-a4.pdf

Thatsme314 ( обсуждение ) 07:10, 30 июля 2022 (UTC) [ ответить ]

Объединить со страницей "Липшицева непрерывность"

Вероятно, нам следует объединить эту страницу с непрерывностью Липшица . Thatsme314 ( обсуждение ) 06:44, 3 июня 2022 (UTC) [ ответить ]

Но понятие фактора растяжения, как описано здесь, в основном применяется к дискретным наборам точек или геометрическим фигурам, таким как кривые или узлы, в то время как понятие непрерывности Липшица в основном применяется к непрерывным функциям действительных чисел или другим пространствам, где (в отличие от дискретных точек) непрерывность является осмысленной концепцией. Хотя при абстрактном определении метрическими пространствами они имеют одинаковое определение, их области применения и основные результаты в значительной степени не связаны. По этой причине было бы серьезно вводить в заблуждение и сбивать с толку попытки объединить их. Как вы собираетесь говорить о геометрических остовах или лемме Джонсона–Линденштрауса в объединенной версии статьи о непрерывности Липшица, например? Это подтемы, которые являются центральными здесь, но даже не на карте там. Если бы вы повторно связали обсуждение растяжения в статьях о остове или лемме JL с непрерывностью Липшица вместо этого, ни один читатель этих статей не смог бы понять, о чем идет речь в ссылке, или даже о том, идет ли речь об одной и той же концепции. И если бы вы попытались включить какой-либо существенный контент о остовах или лемме JL в статью о непрерывности Липшица, все настоящие аналитики, пытающиеся прочитать статью, подумали бы: «А зачем нам вообще нужны конечные множества? Все, что с ними связано, тривиально», и посчитали бы это пустой тратой времени. — Дэвид Эппштейн ( обсуждение ) 06:50, 3 июня 2022 (UTC) [ ответить ]

Я опоздал с обсуждением, но статья Ассафа Наора по ICM является хорошим примером тесной связи между аналитическими и дискретно-математическими аспектами этого предмета.

Я агностик относительно того, стоит ли объединять его с непрерывностью Липшица . Эта страница уже своего рода свалка. Но мне это определенно не кажется немыслимым.

— platypeanArchcow ( обсуждение ) 07:31, 18 сентября 2022 (UTC) [ ответить ]

Я только что добавил примечание о лемме JL в разделе "См. также" статьи о непрерывности Липшица. И вы ошибаетесь, полагая, что все аналитики считают дискретную математику бесполезной или что читатели статьи JL не смогут понять статью Липшица.

• Я перешел к статье JL, потому что она мне была нужна для машинного обучения, и я думал, что билипшицева формулировка была наиболее естественной / самой простой для понимания. Кроме того, метрические пространства — это моя любимая среда для размышлений о липшицевых функциях.
• Многие математики, включая Белу Боллобаса , Тимоти Гауэрса и Теренса Тао , интересуются анализом, но также интересуются и комбинаторикой.
• В качестве примера людей, интересующихся дискретными пространствами в анализе, рассмотрим двойственность Канторовича-Рубинштейна , которая для любого полного, сепарабельного метрического пространства X дает формулу для расстояния Вассерштейна между любыми двумя вероятностными мерами Бореля на X. Уэйнрайт в своей книге «Высокоразмерная статистика» (пример 3.17) рассматривает случай, когда X счетно, и мы помещаем дискретную метрику на X , где метрика Вассерштейна совпадает с расстоянием полной вариации. Этот пример сосредоточен вокруг дискретных пространств и по-прежнему интересен — он связывает две популярные метрики вероятностных мер Бореля.

После более внимательного прочтения статьи я согласен, что геометрические остовные ключи не относятся к статье Липшица. Что меня сейчас беспокоит, так это вся эта история с S и T , которые различны, и эта функция f . Я считаю, что концепцию «коэффициента растяжения»/«искажения» можно было бы лучше развить в контексте одного метрического пространства, без какого-либо упоминания функции f . Во всех трех примерах с геометрическими остовными ключами, теорией узлов и потоками укорачивания кривых мы имеем S = T , у нас нет функции f , и, похоже, внутренняя метрика играет важную роль. Похоже, ваши предложения о внутреннем и внешнем расстоянии являются перефразированием замечаний Громова для случая S = T и без f (ну, f =id, но в этой ситуации f является своего рода отвлечением). Я сомневаюсь в целесообразности обобщения на случай, когда у нас есть и S , и T , и дополнительная функция f . Я предполагаю, что вы написали это обобщение, чтобы вы могли поговорить о лемме JL, гипотезе CNRS и алгоритмах аппроксимации. У меня нет опыта в гипотезе CNRS и почти нет опыта в алгоритмах аппроксимации, но мое впечатление о лемме JL таково, что она не относится к этой статье. Даже если некоторые статьи используют термин «искажение», говоря о лемме JL, они, похоже, используют его в другом смысле, чем статьи о геометрических остовах/теории узлов/потоках укорачивания кривых; лемма JL лежит гораздо ближе к непрерывности Липшица/билипшица, и (если я не ошибаюсь) она имеет дело с внешней метрикой, а не с внутренней метрикой. Thatsme314 ( talk ) 11:16, 3 июня 2022 (UTC) [ ответить ]

Проблема со ссылкой на лемму Джонсона-Линденштрауса

В цитате из леммы Джонсона-Линденштрауса говорилось: « Лемма Джонсона-Линденштрауса утверждает, что любое конечное метрическое пространство с n точками может быть вложено в евклидово пространство размерности O (log  n ) с искажением 1 + ε ...» Это определенно неверно, и то, каким образом это не выполняется, является важной частью изучения геометрии CAT(0). (Например, 4-точечное пространство с попарными расстояниями d(x,y) = d(y,z) = d(x,z) = 2 и d(w,x) = d(w,y) = d(w,z) = 1 не может быть вложено ни в какое евклидово пространство с искажением, меньшим, чем sqrt(2/sqrt(3)) (реализованным как вершины и центр равностороннего треугольника). Я не эксперт по этой лемме, но надеюсь, что исправил ее до истинного утверждения. Дилан Терстон ( обсуждение ) 22:25, 21 июля 2022 (UTC) [ ответ ]