Vectores casi ortogonales

Question

Esto tiene que ver con la geometría de altas dimensiones, con la que siempre soy un inútil. Supongamos que tenemos algún número entero grande $n$ y algunos pequeños $\epsilon>0$ . Trabajar en la esfera unitaria de $\mathbb R^n$ o $\mathbb C^n$ quiero elegir una gran familia de vectores $(u_i)_{i=1}^k$ que es casi ortogonal en el sentido de que $|(u_i|u_j)| < \epsilon$ cuando $i\not=j$ . Supongo que me interesa saber cómo la mayor elección de $k$ crece con $n$ y $\epsilon$ .

Por ejemplo, podemos dejar que $\{u_1,\cdots,u_n\}$ sea la base habitual y, a continuación, elija $u_{n+1} = (1,1,\cdots,1)/n^{1/2}$ que funciona si $n^{-1/2} < \epsilon$ . A continuación, puede dejar que $u_{n+2} = (1,\cdots,1,-1,\cdots,-1)/n^{1/2}$ y demás, pero no tengo claro hasta dónde se puede llegar.

Answer 1

Matt, para conseguir $k$ puntos, sólo necesita $n\ge C \epsilon^{-2} \log k$ . Véase http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma o busca en Google "Johnson-Lindenstrauss lemma".

Answer 2

El siguiente siempre ha sido uno de mis hechos favoritos en combinatoria extrema. Si quieres elegir vectores unitarios en R^n tales que el producto interior entre dos cualesquiera de ellos sea como máximo 0, entonces lo mejor que puedes hacer es elegir 2n vectores (una base ortonormal y menos esa base). Si relajas la condición a "como mucho épsilon", entonces puedes obtener exponencialmente muchos por un argumento de volumen o métodos probabilísticos, como han comentado otras personas. Y si vas en la otra dirección, insistiendo en que el producto interno es como máximo -epsilon, entonces el mayor número de vectores que puedes elegir está acotado por encima independientemente de n -- es de orden 1/epsilon. Para demostrar este último hecho, hay que calcular la norma de la suma de los vectores de dos maneras diferentes, un bonito ejercicio que no voy a hacer aquí. No sé cuánto se sabe si se impone la condición de que ningún producto interior es mayor que épsilon(n) para alguna función que tiende a cero desde arriba. No está claro que el simple argumento probabilístico dé el resultado correcto en este régimen. Pero en general me gusta mucho la forma en que la función tiene tres comportamientos tan diferentes.

Answer 3

De hecho, lo que escribió Bill Johnson puede valer incluso para puntos todas cuyas coordenadas son $\pm 1/\sqrt{n}$ . Elija primero $k = \exp(\epsilon^2 n/4)$ vectores $v_1, \dots, v_k$ eligiendo que cada coordenada sea $\pm 1$ con probabilidad $1/2$ cada uno. A continuación, defina $u_i = v_i/\sqrt{n}$ . Un límite de Chernoff muestra que la probabilidad de $|\langle u_i, u_j \rangle| \geq \epsilon$ es como máximo $2 \exp(-(\epsilon^2/2)n)$ . Esto equivale a $2/k^2$ por elección de $k$ y, por lo tanto, se puede tomar un límite de unión sobre el máximo de $\binom{k}{2} < k^2/2$ pares $(i,j)$ para demostrar que hay una probabilidad positiva de $|\langle u_i, u_j \rangle| < \epsilon$ para todos $i \neq j$ .

PD: Puede que me haya equivocado con las constantes, pero siempre se pueden ajustar para que las cosas salgan bien.

Answer 4

El lema de Johnson-Lindenstrauss afirma que se puede tener $k = 2^{\Omega(\epsilon^2 n)}$ . También se sabe que no se puede tener $k$ mayor que $2^{O(\epsilon^2 \log(1/\epsilon) n)}$ para que el lema de Johnson-Lindenstrauss te dé una respuesta casi ajustada. Véase la última sección de "Problems and results in Extremal Combinatorics Part I" de Noga Alon para una demostración de este último hecho.

Answer 5

Al menos en el caso real, la palabra de moda es "códigos esféricos".
http://mathworld.wolfram.com/SphericalCode.html
http://neilsloane.com/packings/

Se trata de encontrar un conjunto lo más amplio posible en un $n$ -esfera cuyas distancias están separadas al menos por una cantidad determinada. Es un análogo de geometría esférica del problema de empaquetamiento denso de esferas y generaliza el problema del número besador para esferas.

Como ocurre con estos problemas clásicos, muchos resultados parciales son parciales, pero son menos los que han demostrado ser óptimos.