¿Preservan (aproximadamente) la convexidad las proyecciones aleatorias?

Question

El lema de Johnson-Lindenstrauss implica que cualquier conjunto de $k$ puntos en $\mathbb{R}^d$ puede proyectarse aleatoriamente en $d' \approx \log(k)/\epsilon^2$ dimensiones tales que las distancias entre cada par de puntos se conserven aproximadamente, hasta un factor multiplicativo de $(1 \pm \epsilon)$ .

Mi pregunta es si dicha proyección también preservará aproximadamente la convexidad. Supongamos que la $k$ puntos se encuentran en la superficie de un cuerpo convexo en $\mathbb{R}^d$ . ¿Existe una proyección en $d'$ dimensiones tales que cada punto se encuentre cerca de la superficie de un cuerpo convexo?

Answer 1

Sí, si el cuerpo convexo es "suficientemente redondo". Si no lo es, la "proximidad" resultante al límite de un conjunto convexo es en términos absolutos y no relativos. No sé si puede mejorarse, pero las observaciones de Bill Johnson sugieren que no.

Sea $X=\{x_i\}$ , $i=1,\dots,k$ sea el conjunto en cuestión y $K$ el cuerpo convexo cuya frontera contiene $X$ . Para la normalización, supongamos que $diam(K)=1$ . Para cada $i$ , dejemos que $y_i$ sea un punto en $\mathbb R^d$ tal que el vector $y_i-x_i$ es la normal interior unitaria a un hiperplano de apoyo a $K$ en $x_i$ . Entonces $$ \langle y_i-x_i, x_j-x_i \rangle \ge 0 $$ para todos $j$ (los paréntesis angulares denotan el producto escalar). Apliquemos el lema de Johnson-Lindenstrauss al conjunto $X\cup\{y_i\}$ y que $x_i'$ y $y_i'$ sean las imágenes de $x_i$ y $y_i$ en $\mathbb R^{d'}$ de forma que se mantengan todas las distancias hasta un error relativo (y, por tanto, absoluto) $\varepsilon$ . Recordemos que el producto escalar puede recuperarse a partir de las distancias mediante la fórmula $$ \langle y_i-x_i, x_j-x_i \rangle = \frac12(|x_iy_i|^2+|x_ix_j|^2-|y_ix_j|^2) . $$ Como las distancias están casi preservadas y el producto es no negativo, para las imágenes obtenemos $$ \langle y_i'-x_i', x_j'-x_i' \rangle \ge -3\varepsilon $$ Esto significa que todos los $x_j'$ pertenecen al semiespacio $H_i$ definido por $$ H_i = \{ x'\in\mathbb R^{d'} : \langle x'-x_i', y_i'-x_i' \rangle \ge -3\varepsilon \} $$ Desde $|y_i'-x_i'|=1\pm\varepsilon $ el punto $x_i'$ se encuentra a poca distancia $3\varepsilon/(1-\varepsilon)\le 4\varepsilon$ desde el límite de $H_i$ (suponiendo $\varepsilon\le 0.1$ ). Por lo tanto, la proyección de $X$ está contenido en el conjunto convexo $K':=\bigcap_i H_i$ y se encuentra a poca distancia $4\varepsilon$ de su límite.

Answer 2

Resultado negativo:

Véase la p. 377 del capítulo 15 del libro de Matousek, que puede encontrarse aquí . En resumen, si desea que la imagen de la $k$ puntos que se encuentran entre la superficie de un cuerpo convexo $K$ y la superficie de $DK$ para algunos $D>1$ necesita que el operador tenga al menos el rango $k^{f(D)}$ para alguna función $f$ .

Resultado positivo en un problema relacionado:

En

Johnson, William B.; Lindenstrauss, Joram; Schechtman, Gideon On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. Geometrical aspects of functional analysis (1985/86), 177-184, Lecture Notes in Math., 1267, Springer, Berlín, 1987,

se demuestra que para alguna constante $C$ , si tiene $k$ puntos en la superficie de un cuerpo convexo simétrico, entonces se pueden poner los puntos isométricamente en un adecuado $\ell_\infty^m$ de tal manera que una proyección aleatoria de rango de orden $k^{1/D}$ situará los puntos entre la superficie de un cuerpo convexo simétrico $K$ y la superficie de $CDK$ ; véase el documento para una declaración precisa. No creo que la simetría tenga mucho que ver aquí. Nos interesaba la incrustación de puntos en un espacio de Banach y, por tanto, no pensábamos en cuerpos convexos generales. El teorema de incrustación que probamos quedó obsoleto más tarde, cuando Matousek demostró que un espacio métrico de tamaño $k$ incrusta en $\ell_\infty^{n}$ con distorsión $D$ con $n$ acerca de $Dk^{1/(2D)} \log k$ (véase la página 404 del enlace anterior).

Answer 3

No es una respuesta, sólo una idea.

Parece demasiado esperar. Aquí hay 300 puntos esparcidos al azar sobre la superficie de un elipsoide en $\mathbb{R}^3$ y, a continuación, se proyecta a dos dimensiones. No importa cómo se oriente el plano de proyección, los puntos proyectados no están cerca del límite de un conjunto convexo bidimensional, sino que rellenan el interior de dicho conjunto.

              

Answer 4

Obsérvese que la proyección de una esfera de alta dimensión sobre un dimensión parece gaussiana (un hecho observado por primera vez por Boltzmann, que yo sepa). Así pues, si se tiene un conjunto de puntos equidistribuidos en la $\mathbb{S}^n,$ su proyección sobre una dimensión será gaussiana en el intervalo, por lo que presentará lo contrario del comportamiento que conjeturas (fíjate que esto será para cualquier proyección sobre una dimensión). Dado que, como señala @Joseph en su respuesta, no hay mucha diferencia entre distintas dimensiones pequeñas, yo estaría bastante seguro de que la respuesta a tu pregunta es NO.