12 votos

Hacer una distancia l_2 a partir de una distancia l_1

Si pensamos en el l 1 como una distancia de cuadrícula entre puntos, entonces podemos pensar en l 2 distancia como lo que obtenemos cuando "atajamos" la cuadrícula al ir "dentro" de una celda.

Hacer la cuadrícula más fina no cambia la l 1 distancia, por lo que no hay un sentido obvio en el que el l 2 puede verse como una versión limitada de la distancia l 1 .

Así que esta es mi pregunta: ¿hay alguna manera de tomar un l 1 -y extraer un l 2 como la distancia de la misma (posiblemente como caso límite). Lo pregunto porque tengo una distancia definida en un espacio discreto que tiene un l 1 -y me gustaría generalizarlo a medida que el espacio discreto se hace más y más fino, pero quiero terminar con una distancia que vaya "directamente" a través del espacio como l 2 .

Disculpas si esto es demasiado vago.

5voto

Flow Puntos 14132

L_2 puede verse como el límite de una secuencia de métricas cuyas bolas métricas son (en el plano) polígonos regulares de 2n lados, donde n va al infinito. En dimensiones superiores no se dispone de suficientes polígonos regulares para hacer un límite con ellos, pero funciona igual de bien utilizar los irregulares. Esta técnica es a veces útil en geometría computacional, porque la métrica poligonal permite estructuras de datos de búsqueda de rangos más rápidas que la euclidiana.

Si quieres una distancia en algún tipo de gráfico discreto (del modo en que L_1 puede verse como distancia en una cuadrícula regular) pero que se acerque a L_2 planar en el límite, prueba a utilizar el mosaico del molinete. Si se mide el camino más corto a lo largo de los bordes de las baldosas entre dos puntos cualesquiera en los bordes de dos baldosas cualesquiera, y luego se subdivide repetidamente para producir un mosaico de molinete más fino, la distancia del camino más corto se acercará a la distancia euclidiana en el límite.

En cuanto a la sugerencia de Kore min de buscar incrustaciones métricas: cualquier métrica puede incrustarse en L_infinito sin ninguna distorsión. Y en el plano, L_1 es lo mismo que L_infinito (aunque son bastante diferentes en dimensiones superiores), así que podría tener algo que ver con lo que estás hablando. Véase, por ejemplo este artículo de Wikipedia .

4voto

Jake McGraw Puntos 16515

En algunos casos, se puede recuperar la información de L_2 en el límite considerando paseos aleatorios, o dicho de otro modo, básicamente contando caminos. Cuando dices "espacio discreto con comportamiento similar a L_1", me imagino una gran cuadrícula de puntos (algo así como Z ^d) que están conectados a sus vecinos más cercanos por aristas, definiéndose la distancia entre dos puntos de forma natural en la teoría de grafos como la longitud del camino más corto entre ellos. En este caso, se puede considerar un paseo aleatorio uniforme a lo largo de las aristas del grafo, y luego refinar sucesivamente la cuadrícula. Esto es importante: si se refina la cuadrícula, digamos, en un factor de dos (por lo que cada paso del paseo aleatorio se convierte en la mitad), entonces hay que refinar el paseo dando pasos cuatro veces más rápido. (En general, cuando se refina por un factor F, hay que dar pasos F^2 veces más rápidos). A medida que vas refinando, la probabilidad de que el paseo acabe cerca de un punto concreto en un momento fijo del futuro puede estabilizarse en algo parecido a una función de L_2 de distancia desde el punto de partida.

Si esta construcción funciona en tu caso, entonces puedes pensar que el logaritmo de la probabilidad de acabar en una vecindad pequeña es aproximadamente proporcional al volumen de la vecindad y al cuadrado de su distancia L_2 desde el punto de partida, pero excepto en casos muy especiales, la aproximación probablemente no será buena para todos los pares de puntos, especialmente si no están muy cerca unos de otros. Hay que tener en cuenta que el cálculo de estas probabilidades equivale básicamente a contar caminos de longitudes determinadas entre puntos, en lugar de limitarse a encontrar la longitud del camino más corto (que correspondería aproximadamente a la distancia L_1).

La medida en que ese cálculo se parezca realmente a una distancia similar a la de L_2 depende de muchas cosas. La construcción funcionará básicamente como se indica cuando se refina sucesivamente una cuadrícula como Z ^d debido al teorema del límite central. Si tu "espacio discreto" no es muy parecido a éste, entonces la construcción podría no funcionar en absoluto, o podría darte algo que no es del todo correcto pero que es "lo suficientemente cercano para el trabajo gubernamental", por así decirlo. Tendrás que juzgarlo tú.

1voto

Warren Blanchet Puntos 881

Supongo que estás pensando en algo relacionado con la incrustación de métricas. Cualquier métrica se puede incrustar en l_2 con la distorsión acotada por O(log n), que es ajustada en general.

Consulte las notas de esta conferencia para obtener más información: http://www-math.mit.edu/~goemans/18409.html

Además, la descomposición de Kashin está estrechamente relacionada con su problema, véase http://www.cwru.edu/artsci/math/szarek/SzarekICMslides.pdf

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X