当前位置：首页 > news >正文

汕尾海丰建设规划局网站小网站搜什么关键词好

news 2025/8/1 4:23:56

汕尾海丰建设规划局网站,小网站搜什么关键词好,蒲公英路由做网站,天津专业做网站的公司有哪些文章目录最短距离和连续极小值距离函数和覆盖半径格的平滑参数致谢最短距离和连续极小值除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为 λ1min⁡x,y∈L,x≠y∥x−y∥min⁡z∈L,z≠0∥z∥.\begin{aligned} …

文章目录

最短距离和连续极小值
距离函数和覆盖半径
格的平滑参数
致谢

最短距离和连续极小值

除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为
$λ1=min⁡x,y∈L,x≠y∥x−y∥=min⁡z∈L,z≠0∥z∥.\begin{aligned} \lambda_1 &= \min_{\bm{x,y} \in \mathcal{L}, \bm{x} \neq \bm{y}} \| \bm{x} - \bm{y} \| \\ &= \min_{\bm{z} \in \mathcal{L}, \bm{z} \neq \bm{0}} \| \bm{z} \|. \end{aligned}$

在这里插入图片描述

如上图所示，两两格点构成的向量都可以通过平移得到起始点为原点的向量，通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小，记为 $λ1\lambda_1$ 。

同理可定义第二至第 $n$ 连续极小 $λ2,…,λn\lambda_2, \dots, \lambda_n$ 。

在二维格上，可以用多项式时间算法求解出 $λ1\lambda_1$ ，但在多维格上求解 $λ1\lambda_1$ 则十分困难。注意，给定一组格基，最短向量不一定是格基之一。

定义1 在格 $L\mathcal{L}$ 中，第 $i$ 连续极小值（ $i=1,…,ni=1,\dots, n$ ） 为 $λi=min⁡{r:dimspan(B(r)∩L)≥i}\lambda_i = \min \{ r : \mathrm{dim} ~ \mathrm{span}(\mathcal{B}(r) \cap \mathcal{L}) \geq i \}$ 。

在定义1中， $B(r)\mathcal{B}(r)$ 表示半径为 $r$ 的超球体（Ball），该超球体与格 $L\mathcal{L}$ 交集产生的向量张成（ $span\mathrm{span}$ ）的空间的维度（ $dim\mathrm{dim}$ ）为 $i$ 。换而言之，第 $i$ 连续极小值即包含至少 $i$ 个线性无关格向量的最小球的半径。

把球的中心放在原点，若球中有非零格向量，那么球中不止一个格向量。以上图为例，红色区域包含了一个非零格向量以及它的逆向量，但这二者在同一条直线上，仅张成一维空间，该超球体的半径是 $λ1\lambda_1$ 。而以下图为例，一个更大的超球体包含了4个非零格向量，可以张成二维空间，该超球体的半径是 $λ2\lambda_2$ 。

在这里插入图片描述

在整数格 $Zn\mathbb{Z}^n$ 中，有 $λ1=λ2=⋯=λn\lambda_1 = \lambda_2 = \cdots = \lambda_n$ 。一般而言， $λ1≤λ2⋯≤λn\lambda_1 \leq \lambda_2 \cdots \leq \lambda_n$ 。

距离函数和覆盖半径

对任意点 $t∈Rn\bm{t} \in \mathbb{R}^n$ ，记距离函数 $μ(t,L)\mu(\bm{t}, \mathcal{L})$ 返回 $t\bm{t}$ 到最近格点的距离，即 $μ(x,L)=min⁡x∈L∥t−x∥\mu(\bm{x}, \mathcal{L}) = \min_{\bm{x} \in \mathcal{L}} \| \bm{t} - \bm{x} \|$ 。

通过移动 $t\bm{t}$ 可以找到 $μ\mu$ 的最大值，称为覆盖半径，即 $μ(L)=max⁡t∈span(L)μ(t,L)\mu(\mathcal{L}) = \max_{\bm{t} \in \mathrm{span}(\mathcal{L})} \mu(\bm{t}, \mathcal{L})$ 。以下图为例， $t\bm{t}$ 从①移动至②再移动至③，此时无论 $t\bm{t}$ 再怎么移动都会减小 $μ\mu$ 的值，故 $μ\mu$ 在步骤③时达到最大。

在这里插入图片描述

以下图为例，将所有格点作为球心，不断增大球的半径 $r$ ，当半径 $r$ 超过 $12λ1\frac{1}{2} \lambda_1$ 时这些球开始互相覆盖，而当空间中所有点都被这些球覆盖时 $r$ 刚好等于 $μ\mu$ 的最大值，名称“覆盖半径”由此而来。想象一下，在下图的第三张子图里，若再移动蓝色点 $t\bm{t}$ 均会落在球的内部从而使 $μ\mu$ 变小。

在这里插入图片描述

格的平滑参数

假设噪声 $γ\bm{\gamma}$ 随机采样自均匀分布 $U([0,r]n)\mathrm{U}([0, r]^n)$ ，记格点为 $x∈L\bm{x} \in \mathcal{L}$ ，为使 $γ+x\bm{\gamma} + \bm{x}$ 的分布看起来与 $U(Rn)\mathrm{U}(\mathbb{R}^n)$ 无异，要使 $r$ 足够大。以上图为例， $γ+x\bm{\gamma} + \bm{x}$ 的出现频数用红色深浅表示，当 $r$ 太小时有些地方是空白色，随着 $r$ 的增大有些区域红色的深浅程度不一，当 $r$ 无穷大时所有区域颜色一样。

当 $r$ 是无穷大时是最理想的状态。事实上，存在一个有限的 $r^\hat{r}$ 值可使 $γ+x\bm{\gamma} + \bm{x}$ 趋近于完全均匀分布，有 $max⁡μ≤∥r^∥≤log⁡(n)⋅nλn\max \mu \leq \| \hat{r} \| \leq \log(n) \cdot \sqrt{n} \lambda_n$ 。

注：下面笔记属于个人猜测，高斯噪声这块公开课讲得比较模糊，强烈建议查阅原始论文。

球的半径要取得很大是因为它的边界十分明显。为解决该问题，可以使球心到边界逐渐平滑，即采用球状高斯分布进行平滑，从而得到高斯噪声。以下图为例，高斯平滑缩小了 $r$ 值。对半径对应向量的每个分量 $vi\bm{v}_i$ ，应使得 $∥vi∥≈ηϵ≤log⁡(n)λn\| \bm{v}_i \| \approx \eta_\epsilon \leq \log(n) \lambda_n$ ，仅略大于 $λn\lambda_n$ ，此处 $ηϵ\eta_\epsilon$ 被称为平滑参数。一般而言， $ηϵ\eta_\epsilon$ 由一个错误参数 $ϵ\epsilon$ 决定， $ϵ\epsilon$ 表示当前噪声分布和均匀噪声分布之间的差异。