¿Cómo puedo incrustar un espacio métrico de N puntos en un hipercubo con baja distorsión?

Question

Tengo un espacio métrico de N puntos definido por la matriz de distancia entre pares. Quiero codificar estos N puntos con cadenas binarias, es decir, cada punto se asignará a un vértice en un hipercubo. Las longitudes de las aristas del hipercubo podrían ser diferentes para las distintas dimensiones. El hipercubo es básicamente un hiper-rectángulo. Ahora las preguntas son las siguientes 1. Dada la dimensión del hiperrectángulo, ¿cuál es el límite inferior de la distorsión del espacio métrico original? 2. ¿Cómo se consigue eso, es decir, las longitudes de las aristas, los vértices para cada punto? 3. ¿La incrustación óptima es P o NP?

$A = (P,C), |P| = N, C\in [0,1]^{N\times N}$ , encontrar un mapeo $f:P \rightarrow \times_{j=1}^D $ { $0,l_j $ }, $l_j > 0$ .

tal que para cualquier $\frac{1}{\mu} C_{ij} \le |f(P_i)-f(P_j)| \le \mu C_{ij} $ ,

donde $\mu \sim \Omega(g(D,N))$ es una función polinómica. ¡Muchas gracias!

Answer 1

Este es un bien estudiado (y por desgracia duro) problema. puesto que usted está permitiendo que el hipercubo tener un peso arbitrario, parece que te estás realmente integración en un $\ell_1$ espacio. en general, para estos espacios, se puede obtener un $\log n$ distorsión con $\log^2 n$ dimensiones, y esto es apretado (el camino más corto métrica para un expansor gráfico es un límite inferior). Hay un montón de trabajo sobre este tema en la zona denominada 'métrica incrustaciones'. un buen lugar para comenzar es la encuesta de 2004 por Indyk y Matousek aquí, y Tim Roughgarden tiene buenas notas de clase (y referencias)

El problema es NP-duro para $\ell_1$ en general.

Answer 2

Y. Bartal ha estudiado un problema de la incrustación de la métrica espacios para jerárquicamente separados de los árboles. Con $1 < \mu$ ser un fijo en el real, un número de $\mu$-HST es equivalente al conjunto de vértices de un rectángulo, cuyos bordes son de longitud $c, c\mu^{-1}, c\mu^{-2}, \dots, c\mu^{1-D}$ $l_\infty$- métrica. Es decir, si se piensa el espacio como el conjunto de secuencias de bits de longitud $D$, la distancia de dos secuencias es $c\mu^{-j}$ si primero se difieren en el bit $j$.

Ahora en su pregunta usted que no le $\infty$-métrica, pero para este conjunto de puntos, que en realidad no importa que la métrica de tomar debido a la distorsión entre el este y el $l_1$ o $l_2$ métrica está delimitado por una constante (si fix $\mu$ pero $D$ puede variar).

(Esta métrica puede ser considerado como un gráfico de la métrica en un árbol especial, es decir, uno donde los puntos son algunos (pero no necesariamente todos) los vértices de un árbol grafo con pesos en las aristas, y la distancia es el camino más corto. Aquí es donde "árbol" en el nombre proviene de.)

Ahora Bartal del resultado en [1] básicamente dice que se puede incrustar en cualquier espacio métrico al azar a un $\mu$-HST con la distorsión en la mayoría de los $\mu(2\ln n+2)(1+\log_\mu n)$ donde $n$ es el número de puntos. (También, esta incrustación puede ser calculadas de acuerdo con un estudio aleatorizado polinomio algoritmo.)

Para esto, usted necesita saber lo que es una distorsión de la $\alpha$ random incrustación $f$ medios. Esto significa que para cualquier par de puntos $d(x,y) < d(f(x),f(y))$ es siempre verdadera y que el valor esperado de $d(f(x),f(y))$ es en la mayoría de las $\alpha d(x,y)$. Para muchas aplicaciones, esta es tan buena como la de un determinista de la incrustación con baja distorsión. De hecho, usted puede hacer un determinista de la incrustación con baja distorsión de ella imaginando la métrica $d^* $ sobre el espacio original donde $d^*(x,y) = E(d(f(x), f(y))$, pero esta noción no es demasiado útil, porque el resultado de la métrica no tienen buenas propiedades de más (no HST). De hecho, creo que la aleatoriedad es esencial aquí como me parece recordar haber leído en alguna parte que usted no puede insertar un gráfico del ciclo (con igualdad de borde de pesos) a un árbol gráfico con baja distorsión.

De todos modos, esto no puede realmente responder a su pregunta. En primer lugar, $D$ (el número de dimensiones de un rectángulo) no está determinado de antemano, pero que no es un verdadero problema, porque si usted tiene $D$ significativamente diferentes distancias en la entrada de la métrica, entonces usted necesita, al menos, que un gran $D$ para cualquier incrustación; y con esta incrustación usted no necesita un $D$ mayor que $\log_\mu (\Delta/\delta)$ donde $\Delta$ $\delta$ son las más grandes y las más pequeñas distancias en la entrada. El problema real es que usted parece querer saber un determinista de la incrustación, y el más alto posible distorsión necesario en ese caso, que esto no dice mucho. Por ejemplo, un gráfico del ciclo con un número $n$ de vértices puede ser incrustado isométrico a un cubo de dimensión $n/2$.

Encuesta [2] tiene algo más de referencias.

[1]: Yair Bartal, En la Aproximación Arbitraria Métricas por Árbol de Métricas. Anual de la ACM Simposio sobre Fundamentos de Ciencia de la computación, 37 (1996), 184-193.

[2]: Piotr Indyk, Jiří Matoušek, Baja distorsión de incrustaciones de finito de espacios métricos. El capítulo 8 del Manual de Discretos y de la Geometría Computacional, ed. Jacob E. Goodman y Joseph O'Rourke, CRC Press, 2004.

Answer 3

Tal vez no soy lo que estamos pidiendo a la perfección, pero si usted tiene $N$ puntos, y una matriz de distancias que se $N \times N$ en tamaño, se podría utilizar un $N$-dimensiones hipercubo.

Este hipercubo tendría la $N$ puntos en la $N$ vértices definidos por los vectores $P_1=(1,0,...,0)$, $P_2=(0,1,0,...,0)$, ..., $P_N=(0,0,...,0,1)$. Por lo tanto el $N$ puntos de todos los que existen en la distancia de Hamming $=1$ desde el origen (0,0,...,0). En esta incorporación, todos los de la $N$ puntos en los vértices de la $N$-dimenional unidad hipercubo. En el hipercubo unidad de incrustación, la distancia de Hamming entre cada par de puntos es $2$, y la de Minkowski de la distancia entre cada par de puntos si $\sqrt(2)$

Los pares de distancias, que ya tiene como un dado se utilizan para definir la longitud de la distancia entre dos vértices, y dar así la separación entre cada par de puntos. Por supuesto, si las distancias no son en un espacio Euclidiano, usted no puede utilizar una métrica de Minkowski para definir las distancias.

Si desea que este sea un espacio euclidiano, entonces usted puede utilizar diferentes técnicas para obtener deseada de pares distancia Euclídea,

$$d_{a,b}={(\sum_{i=1}^{i=N}} (a_i-b_i)^2) ^{0.5}$$

o usted puede usar cualquier otra métrica puede ser apropiado en su caso.

Para la distancia euclídea, puede ajustar cada punto a una distancia $d_n, 1 \le n \le N$, a continuación, calcular los pares de las distancias de todos los puntos de datos y tratar de mover los puntos en el fin de acercarse a la aproximación de su distancia original métrica.

Por lo tanto, ahora que usted podría tener cada punto de $P_n, 1\le n \le N$ $(v_1,v_2,...,v_N)$ donde$v_i=0$$i \ne n$, e $v_i=d_i$$i=n$. Esta incrustación de ahora los lugares de cada uno de los puntos en un vértice de un hiper-rectángulo en $N$-dimensiones del espacio, en lugar de en el hipercubo unidad.

Se podría utilizar un método de recocido o de un algoritmo genético con varios candidatos a mutar y se cruzan, o tratar de mover un punto en el tiempo para optimizar el punto de que los pares de distancia a todos los puntos.

¿Cuál es el orden de magnitud de su conjunto de datos de $N$?