机器算法验证 - 用稀疏向量覆盖单位球体 - 吾爱随笔录

我正在寻找覆盖维单位球体的参考资料 $d$

S^{d - 1} = {x \in R^{d} : ‖ x ‖ = 1}

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

我试图用具有个非零系数的向量覆盖甚至的倍数）。换句话说，我正在寻找一个集合这样和 $\mathbb{S}^{d-1}$ $k$ $\log d$ $\sqrt{d}$ $\mathcal{N}$ $\bar{x} \in \mathcal{N} \Rightarrow \| \bar{x} \|_0 \leq k$

\forall x \in S^{d - 1}, \exists \bar{x} \in N : ‖ x - \bar{x} ‖ \leq ε

$\forall x \in \mathbb{S}^{d-1}, \; \exists \bar{x} \in \mathcal{N} : \| x - \bar{x} \| \leq \varepsilon$ 用于一些小的常数

ε > 0

$\varepsilon > 0$ 。因此：

问题：覆盖所需的最小 $k$ 稀疏向量数量最多为？ $\mathbb{S}^{d-1}$ $\varepsilon$

编辑：我什至不确定是否存在对 $d$ 具有对数或平方根依赖性的稀疏向量覆盖。如果它存在，那么它的最小基数肯定在 $d$ 中是指数的，因为我们知道（例如从 [1] 中的推论 4.2.13）任何单位球面的 $\varepsilon$ -net 至少有 $\left( \frac{1}{\varepsilon} \right)^d$ 。

[1]：罗马 Vershynin。高维概率在数据科学中的应用，草稿编辑。.