二维Sobol'序列的精确?∞-分离半径

《Journal of Approximation Theory》:Exact ?∞-separation radius of the Sobol’ sequence in dimension 2

【字体: 大 中 小 】 时间:2026年10月24日 来源:Journal of Approximation Theory 0.7

编辑推荐:

   # 准均匀性的近似性:二维Sobol'序列的分离半径 ## 摘要 准均匀性是点集的一项基本几何性质,对于核插值、高斯过程回归和空间填充实验设计等应用至关重要。尽管准蒙特卡罗方法以其低差异特性而广受认可,但理解其准均匀性对于实际应用仍然具有重要意义。对于二维Sobol'序列

  

# 准均匀性的近似性:二维Sobol'序列的分离半径

## 摘要

准均匀性是点集的一项基本几何性质,对于核插值、高斯过程回归和空间填充实验设计等应用至关重要。尽管准蒙特卡罗方法以其低差异特性而广受认可,但理解其准均匀性对于实际应用仍然具有重要意义。对于二维Sobol'序列,Sobol'和Shukhman(2007)猜想前$N$个点的分离半径达到最优速率$N^{-1/2}$,这将意味着准均匀性。该猜想被Goda(2024)推翻,他计算了稀疏子序列$N=2^{2v}-1$的$\ell_2$-分离半径的精确值。然而,Sobol'序列对任意$N$的一般行为仍不清楚。在本文中,我们推导了二维Sobol'序列前$N=2^m$个点(对所有$m\in\mathbb{N}$)的$\ell_\infty$-分离半径的精确表达式。作为直接推论,我们证明了Sobol'点的分离半径为$O(N^{-3/4})$,这严格劣于最优速率$N^{-1/2}$,揭示了二维Sobol'序列具有次优的网格比,且至少以$N^{1/4}$的速度增长。

## 引言

准蒙特卡罗(QMC)方法用精心构造的确定性点集代替随机采样,用于单位立方体上的数值积分;参见例如[4]、[5]、[6]、[15]、[16]、[21]。虽然经典QMC理论关注差异,即衡量与完美均匀分布的偏差,但它并不直接控制点之间的局部间距。然而,许多应用需要一种更具几何意义的均匀性概念。特别是,散点数据近似[25]、高斯过程回归[24]、核插值[20]以及计算机实验设计[7]、[17]、[19]等任务受益于确保间距和覆盖都得到良好控制的点集。这些性质被准均匀性这一术语所概括。

为了形式化准均匀性,对于有限点集$Q\subset[0,1]^d$,通常使用两个标准几何参数:覆盖半径$h_p(Q)$和分离半径$q_p(Q)$。具体而言,对于$\ell_p$范数$\|\cdot\|_p$,定义
$$h_p(Q) := \sup_{x\in[0,1]^d} \min_{y\in Q} \|x-y\|_p, \quad q_p(Q) := \frac{1}{2}\min_{\substack{x,y\in Q \\ x\neq y}} \|x-y\|_p.$$
直观地,$h_p(Q)$是使以每个点为中心的闭$\ell_p$球覆盖$[0,1]^d$的最小半径,而$q_p(Q)$是使围绕各点的开球互不重叠的最大半径。如[16, Section 6]、[23]和[18]所指出,这种几何解释意味着
$$h_p(Q) \in \Omega(|Q|^{-1/d}), \quad q_p(Q) \in O(|Q|^{-1/d}).$$
网格比$\rho_p(Q) := h_p(Q)/q_p(Q)$量化了$Q$接近理想堆积/覆盖配置的程度。序列$(x_n)_{n\geq 0}$在$\ell_p$中是准均匀的,如果对于$Q_N = \{x_0, \ldots, x_{N-1}\}$,网格比$\rho_p(Q_N)$独立于$N$有界。等价地,由(1),$h_p(Q_N)$和$q_p(Q_N)$都是$\Theta(N^{-1/d})$。

鉴于QMC点集是生成均匀点集的自然候选,重要的是要问它们是否为准均匀的。这个问题并非平凡,因为准均匀性并不必然蕴含低差异性质,对于$d\geq 2$,低差异性质也不蕴含准均匀性[2, Section 1.3]。正如[26]所指出,对于经典QMC构造,这一问题长期悬而未决。这一局面因Goda的开创性成果[9]而改变,该成果表明二维Sobol'序列不是准均匀的。

Sobol'序列[22]是低差异序列最著名的例子之一,由于其高效的数字构造、可扩展到任意样本量以及在高分位积分中的有效性,在实践中被广泛使用。它可在标准软件包中使用,如Python的QMCPy [1]和MATLAB的统计与机器学习工具箱。同时,二维Sobol'序列是一个具有独立数学兴趣的自然对象,因为它是真正二维低差异序列的简单而核心的例子。Sobol'和Shukhman [23]猜想$d$维Sobol'序列前$N$个点的分离半径表现为$N^{-1/d}$,这将意味着准均匀性。对于$d=2$,Goda [9]证明该猜想对于形式为$N=2^{2v}-1$的稀疏子序列不成立,而$N=2^{2v}$的情况随后在[3]中得到了分析。然而,在主要情况$N=2^m$下分离半径的完整刻画仍然是开放的。这种刻画需要对局部点配置进行精细的微观分析。弥补这一差距正是本文的目标。

### 主要结果

设$Q_N$表示二维Sobol'序列(定义2.1)的前$N$个点。我们的主要贡献如下:

- 我们给出了$Q_{2^m}$对所有$m$的$\ell_\infty$-分离半径的精确公式。
- 我们证明了$q_\infty(Q_N) \in O(N^{-3/4})$且$\rho_\infty(Q_N) \in \Omega(N^{1/4})$。

这些结果总结在以下定理及其推论中。

**定理1.1** 设$m\in\mathbb{N}$且$N=2^m$。设$Q_N$为二维Sobol'序列的前$N$个点。若$m=2^v$或$2^v-1$,对某个$v\in\mathbb{N}$,则
$$q_\infty(Q_N) = 2^{-m-1}.$$
否则,将$m$分解为$m=2^v+2^w+c$,其中整数$v>w\geq 0$且$0\leq c<2^w$(注意情形$(w,c)=(v-1,2^{v-1}-1)$被排除,因为这属于第一种情况,因为$m=2^v+1-1$),则
$$q_\infty(Q_N) = 2^{-2^v-2^w}.$$

以下推论表明,二维Sobol'序列的分离半径以$O(N^{-3/4})$的速度衰减,这比最优阶$\Theta(N^{-1/2})$小$N^{-1/4}$倍。因此,Sobol'序列对所有$N$都具有次优的网格比。由于$\mathbb{R}^2$上所有$\ell_p$范数等价,下面给出的渐近阶对任意$p\in[1,\infty]$仍然有效。

**推论1.2** 对任意$m\in\mathbb{N}$,有
$$2^{-m-1} \leq q_\infty(Q_{2^m}) \leq 2^{-3m/4-5/4},$$
$$2^{-m-1} \leq q_\infty(Q_{2^m}) \leq 2^{-3m/4-3/2} \quad (m\neq 1,5),$$
当$m=2^v-2$(对某个$v\geq 2$)时,(3)中的上界取等。

**推论1.3** 对任意整数$N\geq 2$,以下界成立:
$$q_\infty(Q_N) \leq C_1 N^{-3/4}, \quad \rho_\infty(Q_N) \geq C_2 N^{1/4},$$
其中$C_1=C_2=2^{-1/2}$。此外,对于$N\geq 64$,常数可改进为$C_1=2^{-3/4}$和$C_2=2^{-1/4}$。

从逼近论的角度看,这些估计应主要视为一种局限性。它们并未改进基于差异的经典QMC积分误差界。相反,它们表明Sobol'序列的低差异性质并不能防止强烈的局部聚集。事实上,对于无穷多个形式为$N=2^m$的样本量,定理1.1给出$q_\infty(Q_N)=1/(2N)$,而二维准均匀点集的分离半径为$N^{-1/2}$阶。结合数字网的覆盖半径最优性,这意味着网格比不断增长。在核插值中,设$X=Q_N$为插值节点集,设$S_X\subset C([0,1]^2)$为有限维插值空间,使得在$X$上的插值可唯一求解。对于每个$\xi\in X$,设$\chi_\xi\in S_X$为对应的拉格朗日基函数,满足$\chi_\xi(\eta)=\delta_{\xi,\eta}$对所有$\eta\in X$成立,其中$\delta_{\xi,\eta}$是Kronecker $\delta$。插值算子定义为$I_X f = \sum_{\xi\in X} f(\xi)\chi_\xi$。其Lebesgue常数$\Lambda_X := \sup_{x\in[0,1]^2} \sum_{\xi\in X} |\chi_\xi(x)|$是$I_X$关于一致范数的算子范数。因此,标准Lebesgue引理给出
$$\|f - I_X f\|_\infty \leq (1+\Lambda_X) \inf_{s\in S_X} \|f-s\|_\infty.$$
在准均匀性假设下,此类Lebesgue常数的均匀界以及相关稳定性估计是已知的,其对数据点位的依赖反映在网格比中;参见例如[13, Theorems 5.6–5.8]。因此,这里所示的不断增长的网格比阻止了将这些估计统一应用于未修改的二维Sobol'点集。

Sobol'序列最常见且最有效的使用场景是点数是2的幂次($N=2^m$)。因此,我们的结果针对主要使用场景,对于绝大多数实际应用来说是充分的。尽管具有这种实际充分性,分离半径对任意$N$的精确值仍是一个自然的数学问题,我们在第4节中对此进行了研究。

### 相关工作

近年来,QMC点集的准均匀性受到了密集研究。标准QMC构造包括基于数字的构造,如Halton序列、数字网和序列(参见例如[6]、[16]),以及格点集,包括其无限类似物Kronecker序列(参见例如[4]、[21])。

对于格点集,准均匀性已被积极研究。在一维情况下,Kronecker序列的分离半径在[8]中被完全刻画。[2]提供了高维情况下的更一般结果,包括二维Fibonacci格的有界网格比、$d$维格规则的存在性结果,以及$d$维Kronecker序列的显式构造。

对于Halton序列,覆盖半径已知具有最优阶$N^{-1/d}$。因此,与数字序列类似,其准均匀性由分离半径的行为决定。最近,Goda、Hofer和Suzuki [10]证明了Halton序列在任意$d\geq 2$维中不是准均匀的。更精确地,他们证明了对于无穷多个$N$,分离半径比最优阶$N^{-1/d}$小一个对数因子。然而,Halton序列分离半径的精确阶仍然开放。

转向数字网和序列,以$b$为基数的一维van der Corput序列已知是准均匀的,因为其前$b^m$个点为$\{i/b^m \mid 0\leq iw\geq 0$和$i\geq 1$为整数,令$V:=2^v$且$W:=2^w$。则以下成立:

(i) $P[i][V]=1 \iff 1\leq i\leq V$。

(ii) $P[i][V+W]=1 \iff 1\leq i\leq W$ 或 $V+1\leq i\leq V+W$。

(iii) 对任意$\vec{p}\in\mathbb{F}_2^m$且$m\leq 2V-1$,有$(P^m\vec{p})[V]=\vec{p}[V]$且$(P^m\vec{p})[V+W]=\vec{p}[V+W]$。

## 第4节 一般$N$的分离半径

基于我们之前关于$N=2^m$(2的幂次点数)时精确分离半径$q_\infty(Q_{2^m})$的结果,本节建立了$N$为任意点数时$q_\infty(Q_N)$的上界。需要注意的是,此处的分析仅适用于radical inverse order下的Sobol'序列(定义2.1)。为激励我们的理论结果,我们首先进行了数值实验,以识别逐步更新最小距离的对$(p,q)$。

## 结论

我们建立了$N=2^m$情况下分离半径的完整刻画,并研究了其对于一般$N$的数值行为。我们的分析揭示,二维Sobol'序列具有次优的网格比,且至少以$N^{1/4}$的速度增长。这表明,尽管具有有利的差异性质,二维Sobol'序列可能出现聚集现象,这对于需要准均匀采样位置的逼近任务来说是不理想的。虽然数字随机化可能

## 生成式AI和AI辅助技术在手稿准备过程中的使用声明

作者确认在编辑和语言润色手稿过程中使用了OpenAI的ChatGPT 5和Google的Gemini 2.5。在使用这些工具后,作者根据需要审阅和编辑了内容,并对已发表文章的内容承担全部责任。

## 致谢

作者受日本学会振兴会(JSPS) KAKENHI Grant Number 24K06857资助。

Suzuki Kosuke
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号