Cubrir la esfera unitaria con vectores dispersos

Question

Estoy buscando referencias para cubrir el $d$ -Esfera unitaria de una dimensión

$$ \mathbb{S}^{d - 1} = \left\{ x \in \mathbb{R}^d : \| x \| = 1 \right\} $$

Estoy tratando de cubrir $\mathbb{S}^{d-1}$ con vectores con $k$ coeficientes no nulos (idealmente a lo sumo algún múltiplo de $\log d$ o incluso $\sqrt{d}$ ). En otras palabras, estoy buscando un conjunto $\mathcal{N}$ tal que $\bar{x} \in \mathcal{N} \Rightarrow \| \bar{x} \|_0 \leq k$ y

$$ \forall x \in \mathbb{S}^{d-1}, \; \exists \bar{x} \in \mathcal{N} : \| x - \bar{x} \| \leq \varepsilon $$ para alguna constante pequeña $\varepsilon > 0$ . Por lo tanto:

Pregunta : ¿Cuál es el número mínimo de $k$ -vectores dispersos necesarios para cubrir $\mathbb{S}^{d-1}$ con una distancia máxima de $\varepsilon$ ?

Editar : Ni siquiera estoy seguro de que una cobertura con vectores dispersos que tenga una dependencia logarítmica o de raíz cuadrada de $d$ existe. Si existe, entonces su cardinalidad mínima tiene que ser definitivamente exponencial en $d$ ya que sabemos (por ejemplo, por el corolario 4.2.13 de [1]) que cualquier $\varepsilon$ -La red de la esfera unitaria tiene un número de cobertura de al menos $\left( \frac{1}{\varepsilon} \right)^d$ .

[1]: Roman Vershynin. High Dimensional Probability with Applications in Data Science, borrador de ed. .

Answer 1

Después de pensarlo un poco, creo que podemos concluir que encontrar esa cubierta es imposible. Consideremos el vector de todos los $1$ con una escala adecuada:

$$ v = \frac{1}{\sqrt{d}} \left(1 \; \dots \; 1\right)^\top \in \mathbb{S}^{d-1} $$

y considerar una $k$ -vector disperso $\bar{v}$ . Entonces

$$ \#\{i: (v - \bar{v})_i \neq 0\} \geq d - k $$ por lo que el error de aproximación satisfará

$$ \|v - \bar{v}\|_2 \geq \sqrt{ \sum_{j=1}^{d - k} \left( \frac{1}{\sqrt{d}} \right)^2 } = \sqrt{\frac{d - k}{d}} = \sqrt{1 - \frac{k}{d}} $$

Es obvio que para que este error sea independiente de $d$ tendríamos que asegurarnos de que $k \sim c d$ de lo contrario, para un tamaño lo suficientemente grande $d$ este error de aproximación podría acercarse arbitrariamente a $1$ .