Integración isométrica de L2 en L1

Se sabe que dado un subconjunto -punto de (es decir, dado puntos en con la distancia euclidiana) es posible incrustarlos isométricamente en \ ell ^ {n \ eligen 2 } _1 .$n$$\ell_2^d$$n$${\mathbb R}^d$$\ell^{n\choose 2}_1$

¿La isometría es computable en tiempo polinomial (posiblemente aleatorio)?

Dado que hay problemas de precisión finita, la pregunta precisa es

Dado un conjunto $X$ de $n$ puntos en ${\mathbb R}^d$ y $\epsilon >0$ , ¿hay un mapeo $f: X \to {\mathbb R}^{n\choose 2}$ computable (posiblemente, utilizando aleatoriedad) en tiempo polinomial en $n$ y logarítmico en $1/\epsilon$ tal que para cada $x,y\in X$ tenemos

$|| f(x)-f(y)||_1 \leq ||x-y||_2 \leq (1+ \epsilon) \cdot || f(x)-f(y) ||_1$

(Nota: Soy consciente de que un mapeo con la distorsión $(1+\epsilon)$ se puede encontrar con alta probabilidad en polinomio tiempo en $n$ y $1/\epsilon$ mediante la proyección en $O(\epsilon^{-2} \cdot \log n)$ líneas aleatorias, pero no estoy seguro de si el número de dimensiones puede reducirse constructivamente a $n\choose 2$ o incluso $O(n^2)$ cuando $1/\epsilon$ es mucho mayor que $n$ , y no sé si existe es un método de tiempo polinómico para manejar el caso en el que $1/\epsilon$ es exponencial en $n$ .)

Suresh me pidió que reuniera mis comentarios anteriores en una respuesta, así que aquí está. Sin embargo, no estoy realmente seguro de que sea una respuesta a la pregunta original, ya que no es obvio cómo hacer que sea un tiempo polinómico cuando la dimensión del espacio euclidiano de entrada no es constante. Al menos tiene la ventaja de evitar cualquier problema con grande como se hace en la pregunta original, porque no implica ninguna aproximación y parece polinomial para la constante .$1/\epsilon$$d$

De todos modos: desde la geometría integral, existe una medida estándar en conjuntos de hiperplanos en el espacio euclidiano dimensional que es invariante bajo congruencias euclidianas. Tiene la propiedad de que la longitud de cualquier curva de longitud limitada es proporcional a la medida de los hiperplanos que cruzan (con multiplicidad, lo que significa que si un hiperplano cruza dos veces, entonces contribuye dos veces a la medida total de los hiperplanos que cruzan ) En particular, si es un segmento de línea, entonces no surge la complicación de multiplicidad y podemos normalizar la medida en los hiperplanos que cruzan para que sea exactamente la longitud de$d$$C$$C$$C$$C$$C$$C$$C$. (Los hiperplanos que contienen tienen medida cero, así que no se preocupe por la multiplicidad infinita).$C$

Ahora, dado un conjunto de n puntos en el espacio d-dimensional, haga una coordenada para cada una de las particiones de los puntos en dos subconjuntos inducidos por un hiperplano que no pase por ninguno de los puntos. Dé a los puntos en un lado del valor de coordenadas de la partición cero y los puntos en el otro lado del valor de coordenadas de la partición sean iguales a la medida del conjunto de hiperplanos que inducen esa partición.$\ell_1$

Si y son dos de los puntos, dejar que sea el conjunto de hiperplanos cruzan segmento de línea , y dejar que ser los subconjuntos de formados por cada posible partición hiperplano que tiene en un lado y en el otro. Entonces es la unión disjunta de , y las diferencias de coordenadas entre y son solo las medidas de los subconjuntos . Por lo tanto, la distancia entre las coordinaciones de y$p$$q$$n$$K$$pq$$K_i$$K$$p$$q$$K$$K_i$$p$$q$$K_i$$\ell_1$$p$$q$ (la suma de las medidas de ) es la medida de , que es solo la distancia original entre y .$K_i$$K$$\ell_2$$p$$q$

Para los geómetras computacionales, una descripción alternativa de la misma construcción puede ser útil: utilice la dualidad proyectiva para transformar los puntos de entrada en hiperplanos y separe los hiperplanos en puntos. La medida de geometría integral en conjuntos de hiperplanos se transforma luego en una medida más estándar en conjuntos de puntos, la distancia entre y dualiza a la medida de la cuña doble entre dos hiperplanos, y la disposición del hiperplano divide esta cuña doble en celdas más pequeñas . El valor de coordenadas para un punto es la medida de una de las celdas en la disposición (si el hiperplano dual está por debajo de la celda de esa coordenada) o cero (si el hiperplano dual está por encima de la celda). Por lo tanto, la$n$$n$$p$$q$$\ell_1$ distancia entre y es solo la suma de las medidas de las celdas en la cuña doble, que es la misma que la medida de la cuña doble completa. Este doble punto de vista también facilita el cálculo de la dimensión de la incrustación encontrada de esta manera: es solo el número de celdas en la disposición del hiperplano, que es , o más precisamente .$p$$q$$O(n^d)$$\sum_{i=0}^d{n\choose i}$

Hasta ahora, esto proporciona una inserción completamente determinista y exacta en . Pero queríamos una dimensión más pequeña, . Aquí es donde entra el comentario de Luca sobre el teorema de Carathéodory . El conjunto de métricas representables forma un cono poliédrico en el espacio dimensional de todas las funciones, desde pares de puntos desordenados hasta números reales, y el argumento geométrico anterior dice que la métrica euclidiana pertenece a este cono. Los puntos en los rayos extremos del cono son unidimensionales$\ell_1^{O(n^d)}$$\ell_1^{n\choose 2}$$\ell_1$$n\choose 2$$\ell_1$pseudometría (en la que los puntos se dividen en dos conjuntos, todas las distancias dentro de un solo conjunto son cero y todas las distancias a través de la división son iguales), y Carathéodory dice que cualquier punto dentro del cono (incluido el que nos interesa) puede ser representado como una combinación convexa de puntos en rayos extremos cuyo número es como máximo la dimensión del espacio ambiental, . Pero una combinación convexa de a lo sumo métricas unidimensionales es una métrica .$n\choose 2$$n\choose 2$$\ell_1$$\ell_1^{n\choose 2}$

Finalmente, ¿cómo podemos hacer para computar realmente la incrustación bidimensional ? En este punto no solo tenemos un punto en el cono convexo métricas (la métrica de distancia con la que comenzamos), sino que también tenemos un conjunto de puntos extremos del cono (correspondiente a las particiones de la entrada en dos subconjuntos inducidos por hiperplanos) de modo que nuestra métrica es una combinación convexa de estos puntos extremos: para pequeña , esta es una gran mejora sobre los rayos extremos que tiene el cono en general. Ahora todo lo que tenemos que hacer es aplicar un algoritmo codicioso que elimine los puntos extremos de nuestro conjunto, uno por uno, hasta que solo$n\choose 2$$n\choose 2$$\ell_1$$O(n^d)$$d$$2^n-2$$n\choose 2$de ellos quedan En cada paso, debemos mantener como invariable que nuestra métrica todavía está dentro del casco convexo de los puntos extremos restantes, lo cual es solo un problema de viabilidad de programación lineal, y si hacemos esto, Carathéodory se asegurará de que siempre quede un conjunto de puntos extremos cuyo casco convexo contenga la métrica de entrada.$n\choose 2$