Buscando Cubrir la arrogancia-que revienta ${\mathbb R}^{N\gg3}$ contraejemplos

Question

En la clase 4 de su Introducción a la Dinámica de Sistemas Lineales supuesto, después de interpretar el producto interior en ${\mathbb R}^N$ en términos del coseno del ángulo subtendido Stanford Stephen Boyd va en humor a un lado en el que él se burla de la noción de que uno puede "visualizar" y la razón acerca de la ${\mathbb R}^N$-para algunos $N$ mayor que, digamos, $5$ -, apoyándose en la intuitiva analogías con ${\mathbb R}^2$ o ${\mathbb R}^3$.

(Por lo que vale, he encontrado Boyd comentario muy gracioso. Se inicia en el 59'46" del vídeo de YouTube, y va por alrededor de 3 minutos).

En algún momento durante este riff, Boyd afirma que "[la tarde el profesor de Stanford Thomas] la Tapa tiene una serie de ejemplos que muestran que [cuando se trata de a ${\mathbb R}^{N\gg3}$] sabes nada!" Él añade algo como "yo realmente debería recoger algunos de estos a partir de él, porque ellos son realmente buenos... Hay cerca de cuatro de ellos..."

He sido positivamente encantada por este mítico lista de contraejemplos desde que escuché Boyd mención de él.

Si alguien puede me apunte a alguna versión de la Cubierta de la lista me gustaría ayudarme se lo agradeceria mucho.

El asunto va más allá de satisfacer mi curiosidad ociosa. Siento que este es un tema que realmente necesita un poco de sensibilización en la comunidad de investigación. Estoy rodeado por los investigadores, que alegremente se basan en su ${\mathbb R}^3$basadas en la intuición a la razón sobre los algoritmos de búsqueda a través de un "paisaje de la energía" (es decir, una hipersuperficie) en ${\mathbb R}^{1\; \mathrm{bazillion}}$, y que la caca-pooh cualquier preocupación sobre la aplicabilidad de dichas intuiciones, y de la solidez del razonamiento basado en ellos. (Heck, incluso suponiendo que lo sostiene, por ejemplo, ${\mathbb R}^2$ le necesariamente en ${\mathbb R}^3$, o sea que lo que se sostiene en ${\mathbb R}^1$ le necesariamente en ${\mathbb R}^2$, puede conseguir todo mojado...)

Así que mi esperanza es que la Cubierta de la lista de sonajero lo suficiente como para mostrar su arrogancia.

Answer 1

No sé si esto es en la Cubierta de la lista, pero tal vez debería ser:

Para$n=2$$3$, cualquier mosaico de ${\mathbb R}^n$ por unidad de $n$-cubos tiene dos con un completo faceta común. Pero no es cierto para $n \ge 10$: ver http://arxiv.org/pdf/math.MG/9210222.pdf

Answer 2

La más básica de la sorpresa, en mi opinión, es que la relación entre el volumen de la unidad de esfera para el volumen del cubo delimitar la esfera tiende a 0 como la dimensión del espacio tiende a $\infty$. En otras palabras, una alta dimensión de la esfera ocupa casi nada de espacio en el cubo que se circunscribe. Ver páginas 4 y 5 en http://www.cc.gatech.edu/~kingravi/ML%20and%20High%20Dim%20Spaces.pdf.

Otra de las sorpresas que se una al azar par de direcciones en un espacio de alta dimensión son probablemente va a ser casi ortogonales. Esto se discute en la página http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/ (búsqueda por el término "alta dimensión de la geometría") y p. 23 en http://www.cs.cmu.edu/~venkatg/docencia/CStheory-infoage/chap1-alta-dim-espacio.pdf.

Answer 3

La concentración de medir los fenómenos proporcionan excelentes ejemplos de cómo nuestra intuición basada en el espacio de pocas dimensiones es poco fiable en altas dimensiones.

Comparar unidad de bolas en la métrica de los espacios de $\mathbb R^n$ dotado, resp. la métrica Euclidiana $L_2$, frente a $L_1$, e $L_{\infty}$.

La unidad de bolas de $L_2$ están delimitadas por la "ronda" de las esferas y se intercalan entre las otras dos, es decir, que contienen el $L_1$ bolas que se encuentran en el $L_{\infty}$ bolas para cualquier $n$.

Para$n=2$, $L_2$ unidad de bola es un círculo, el $L_1$ unidad de bola es un diamante (convex hull de $\{e_1,e_2,-e_1,-e_2\}$) y el $L_{\infty}$ pelota es el cuadrado de $[-1,1]\times[-1,1]$.

Para $n=3$ $L_2$ pelota es el ordinario de la bola, el $L_1$ bola es (creo) un octaedro, y el $L_{\infty}$ ball es un cubo.

(Si tengo tiempo voy a añadir gráficos w/ Mathematica)

Como $n \to \infty$:

(1) la proporción de los volúmenes de $L_2$ $L_{\infty}$unidad de bolas y la relación de los volúmenes de las $L_1$ $L_2$pelotas de tanto ir a cero.

(2) Si la programación de los algoritmos genéticos o de forma aleatoria en las altas dimensiones y desea generar una dirección uniforme, otro problema viene con la ingenua algoritmo de elección de uniforme, independiente de incrementos: la medida de la $L_{\infty}$ "hipercubo" bolas se vuelve cada vez más concentrado en el crecimiento exponencial de ($2^n$) de las esquinas. Knuth desarrollado un ingenioso algoritmo que produce un uniforme de medida sobre la esfera en cualquier dimensión.

• Puede que también desee comprobar Diestel el libro de la Teoría de grafos - estoy bastante seguro de que hacia el final, los comentarios sobre lo mal que nuestra intuición falla en altas dimensiones. No me matan si estoy mal aquí - pasando por la memoria.

Answer 4

Esperamos que normalmente distribuida variable aleatoria tome valores cercanos a la media, y en bajas dimensiones. Pero en altas dimensiones, no. El volumen de una fina hyperspherical shell aumenta tan rápidamente como su radio aumenta, incluso si la variable tiene mayor densidad de probabilidad cerca de la media, la mayoría de la probabilidad de masa está muy lejos de la media, y una variable aleatoria es muy poco probable que tome un valor cercano a la media.

Específicamente, Deje $X$ ser normalmente una variable aleatoria distribuye en $n$ dimensiones, con una media en $\bf 0$ y la varianza $\sigma^2$. El esperado del cuadrado de la distancia de$\bf 0$$E\big(|X|^2\big) = n\sigma^2$, y la probabilidad de $X$ se encuentran más lejos de $\epsilon n\sigma^2$ a partir de esta distancia es exponencial en $\epsilon$. Para grandes $n$, $X$ toma valores cercanos a $\bf 0$ con una probabilidad de aproximadamente 0; es casi siempre se encuentran en una muy delgada capa esférica de radio $\sigma\sqrt n$.

Esto está en marcado contraste con la baja-dimensional de los casos, donde esperamos que normalmente distribuida variables que tienen valores cercanos a la media de la mayor parte del tiempo.

Como resultado de esto, la superposición de los dos normalmente distribuida variables con diferentes medios es esencialmente cero cuando el número de dimensiones es grande; esto es, nuevamente, contrario a la intuición de dimensiones inferiores.