拓扑数据分析：多参数持久同调的核

René Corbet a , Ulderico Fugacci a , Michael Kerber a , Claudia Landi b , Bei Wang c , ∗(M. Kerber), clandi@unimore.it (C. Landi), beiwang@sci.utah.edu (B. Wang). https://doi.org/10.1016/j.cagx.2019.10 0 0 05 2590-1486/© 2019 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license. ( http://creativecommons.org/licenses/by/4.0/ ) 0计算机与图形学：X 2 (2019) 10 0 0 050ScienceDirect提供的内容列表0计算机与图形学：X0期刊主页：www.elsevier.com/locate/cagx0SMI 2019专栏0多参数持久同调的核0a 奥地利格拉茨科技大学 b 摩德纳和雷焦埃米利亚大学 c犹他大学，美国0文章信息0文章历史：2019年3月13日收到2019年5月18日修订2019年5月21日接受2019年5月31日在线发表0关键词：拓扑数据分析 机器学习持久同调 多元分析0摘要0拓扑数据分析及其主要方法持久同调为计算高维和嘈杂数据集的拓扑信息提供了工具包。已经建立了一参数持久同调的核来将持久同调与机器学习技术连接起来，适用于形状分析、识别和分类。我们通过整合沿直线加权的一参数核来为多参数持久性构建核。我们证明了我们的核是稳定的和高效计算的，从而为多变量数据分析建立了拓扑数据分析和机器学习之间的理论联系。0© 2019 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license. (http://creativecommons.org/licenses/by/4.0/ )01. 引言0拓扑数据分析（TDA）是数据科学中一个活跃的领域，在科学和工程的许多应用中引起了越来越多的兴趣和显著的成功。TDA从无定形固体中提取了深层的几何信息，确定了基因组数据集中的演变的稳健拓扑特性，并在高维临床数据集中识别了不同的糖尿病亚组和一种新的乳腺癌亚型，等等。在形状分析的背景下，TDA技术已经用于2D/3D形状和表面的识别、分类、总结和聚类。这些技术经常捕捉和突出显示数据中的结构，这些结构常规技术无法处理或无法正确地揭示。TDA采用了单纯复合的数学概念0[14]用于在系统中编码更高阶的相互作用，并且在其核心使用持久同调的计算框架[15-19]来提取数据的多尺度拓扑特征。特别地，TDA从高维和嘈杂的数据集中提取了丰富的拓扑特征，这些特征补充了几何和统计特征，为机器学习提供了不同的视角。问题是，我们如何建立和丰富TDA和机器学习之间的理论联系？非正式地说，同调是为了通过检查其拓扑特征（如连通分量、隧道、空洞和更高维度的孔）来对拓扑空间进行分类；0� 通讯作者。邮箱地址：maths@rene-corbet.de (R. Corbet), kerber@tugraz.at0持久同调研究数据集的同调在多个尺度上。这种信息由持久图表汇总，它是平面上的有限多重集。持久图表提供了数据集拓扑特性的完整描述，使其成为定义考虑拓扑的数据特征的有吸引力的工具。此外，持久同调的一个著名定理是持久图表的稳定性[20]——数据的微小变化导致相应图表的微小变化，使其适用于稳健的数据分析。然而，直接将持久图表与机器学习接口存在技术困难，因为持久图表包含平面上没有内积结构的点集，这允许测量长度和角度。换句话说，这样的图表缺乏基于核的学习方法（如核SVM或PCAs）的希尔伯特空间结构。最近的工作提出了几种特征映射的变体，将持久图表转换为R 2 上的L 2-函数。这个想法立即使拓扑特征能够应用于基于核的机器学习方法，因为建立核函数隐式地定义了希尔伯特空间结构。标准持久同调及其与机器学习的初始接口的一个严重限制是仅限于单一尺度参数，从而将其适用性限制在单变量设置中。然而，在许多现实世界的应用中，例如数据采集和几何建模，我们经常遇到由多变量数据集描述的更丰富的信息。例如，气候模拟中同时计算多个物理参数，如温度和压力；我们对理解2 R. Corbet, U. Fugacci and M. Kerber et al. / Computers & Graphics: X 2 (2019) 10 0 0 05 ⟨X , Y⟩ � := �(2) �X �Y dμ. (1) d �(X , Y) := � � (�X − �Y ) 2 dμ. (2) 0这些参数之间的相互作用。再举一个例子，在多变量形状分析中，各种函数族携带着关于3D形状对象的几何信息，比如网格密度、离心率[29]或热核签名[30]；我们有兴趣从这些函数中创建形状的多变量签名。与单变量设置不同，很少有拓扑工具用于研究多变量数据[29,31,32]，更不用说将多变量拓扑特征与机器学习整合。多参数持久同调的活跃领域0[26]研究了将持续性扩展到两个或更多（独立的）尺度参数。像持久性图这样的完整离散不变量在多于一个参数时是不存在的[26]。为了获得部分信息，通常研究切片，即，所有参数都由线性方程连接的一维仿射子空间。在本文中，我们首次建立了拓扑特征与机器学习算法之间的理论联系，通过多参数持久同调的核方法。这样的理论基础对于多变量数据分析的应用是必要的。0我们的贡献。我们提出了多参数持久同调的第一个核构造。我们的核是通用的，稳定的，并且可以在多项式时间内近似。为简单起见，我们将所有结果都表述为两个参数的情况，尽管它们可以扩展到两个以上的参数。我们的输入是一个数据集，根据两个尺度参数进行过滤，并且具有有限的描述大小；我们称之为双重滤波，并将其正式定义推迟到第2节。我们的主要贡献是定义一个特征映射，将双重滤波X分配给一个函数� X：� (2) → R，其中� (2)是R 4的子集。此外，� 2 X在�(2)上是可积的，有效地将双重滤波的空间包括到Hilbert空间L 2 (�(2))中。因此，基于L 2 (�(2))中的标准标量积，定义了一个双参数核，使得对于给定的两个双重滤波X和Y，我们有0我们通过将� (2)的一个点解释为R2中一对（不同的）点来构造我们的特征映射，这些点定义了一个唯一的切片。沿着这个切片，数据简化为单滤波（即，依赖于单个尺度参数的滤波），我们可以从标准的一参数持久性的大类特征映射和核构造中进行选择。为了使特征映射定义良好，我们将注意力限制在一个有限的矩形R上。我们包含到Hilbert空间中引入了双重滤波之间的距离0我们证明了一个稳定性界限，将这个距离度量与匹配距离和交错距离联系起来（见下面关于相关工作的段落）。我们还证明了这个稳定性界限在常数因子上是紧密的（见第4节）。最后，我们证明了我们的核构造具有高效的近似方案。固定一个绝对误差界限ϵ，我们给出了一个多项式时间算法，其中1/ϵ和双重滤波X和Y的大小来计算一个值r，使得r ≤  � X , Y � �  ≤ r +ϵ。在高层次上，该算法将域分割成越来越小宽度的盒子，并在每个子域内通过下限和上限和来评估（1）的积分，当达到所需的精度时终止该过程。技术上的困难在于在子域内移动参数时准确和可证明地近似特征映射的变化。0相关工作。我们的方法在很大程度上依赖于对单单�ltrations构造稳定且高效可计算的特征映射。这一研究方向始于Reininghaus等人[21]，他们的方法在第2节中进行了详细讨论。[24,33]中出现了替代核构造。核构造适用于将持久图的空间包含在具有更有利特性的更大空间中。这一思想的其他例子包括持久景观[22]和持久图像[34]，它们也可以被解释为核构造。对于单单�ltrations定义的核和相关变种已被用于区分和分类形状和表面[21,25]。另一种方法来自于在持久图上定义适当的（多项式）函数，以得到Rd中的固定维度向量，从而可以进行机器学习任务；参见[35–38]。如前所述，多参数持久性的持久图不存在[26]。然而，bi-�ltrations仍然具有有意义的距离度量，这导致了两个bi-�ltrations的接近概念。最突出的这种距离是交错距离[39]，然而最近已经证明计算和近似交错距离是NP完全的[40]。计算上具有吸引力的替代方法是（多参数）瓶颈距离[41]和匹配距离[42,43]，它比较所有切片上的持久图（适当加权）并选择最差的差异作为bi-�ltrations的距离。这种距离可以通过适当的线段子样本近似到精度ϵ[42]，并且也可以在多项式时间内精确计算[43]。我们的方法在这些工作的基础上进行了扩展，不仅定义了一种距离，而且在bi-�ltrations上定义了一个内积，将其包含到希尔伯特空间中。在类似的精神中，软件库RIVET[44]提供了一种可视化工具，通过扫描切片来探索bi-�ltrations。02.预备知识0我们介绍了这项工作中所需的基本拓扑术语。我们将自己限制在单纯复合体的情况下，以便更清晰地直观理解概念，但我们的结果可以推广到更抽象的输入类型（如持久模块的最小表示）而不会出现问题。0单单�ltrations。给定一个顶点集V，一个（抽象）单纯形是V的非空子集，一个（抽象）单纯复合体是这样的子集的集合，它在取非空子集的操作下是封闭的。单纯复合体X的子复合体是一个满足Y �X的单纯复合体Y。固定一个有限单纯复合体X，X的单单�ltration是一个将每个实数α映射到X的子复合体X(α)的映射，满足当α ≤ β时，X(α) �X(β)。X的大小是X的单纯形的数量。由于X是有限的，当α从-∞连续增长到+∞时，X(α)只在有限多个地方发生变化；我们称这些值为关键值。更正式地说，如果不存在α的开邻域，使得单单�ltration将邻域中的每个值分配给相同的子复合体，则α是关键的。对于X的单纯形σ，我们称σ的关键值为所有α的下确界，其中σ ∈X(α)。为简单起见，我们假设这个下确界是一个最小值，因此每个单纯形在单单�ltration中都有一个唯一的关键值。0Bi-�ltrations。对于R 2中的点，如果a ≤ c且b ≤ d，则我们写作(a，b)≤ (c，d)。类似地，如果a < c且b < d，则我们说(a，b) <(c，d)。对于有限单纯复合体X，X的bi-�ltration是一个映射，它为R2中的每个点p分配一个X的子复合体X(p)，使得每当p ≤ q时，X(p) �X(q)。同样，如果对于任意ϵ >0，X(p1−ϵ，p2)和X(p1，p2−ϵ)都是关键点p = (p1，p2)对于XR. Corbet, U. Fugacci and M. Kerber et al. / Computers & Graphics: X 2 (2019) 10 0 0 05 3 0图1.三个黑点标记了X中某个单形σ的三个临界点。阴影区域表示单形在双单调序列中的位置。在给定的切片上（红线），虚线表示对应临界点“影响”切片的第一个位置。这个位置要么是临界点在切片上的上垂直投影，要么是右水平投影，具体取决于临界点是在线的下方还是上方。对于σ，我们看到它在蓝点标记的位置进入切片。0与X(p)不完全相同。请注意，与单调序列的情况不同，临界点的集合可能不是有限的。如果一个双单调序列只有有限多个这样的临界点，我们称其为温顺的。对于一个单形σ，如果对于任意ϵ>0，σ既不在X(p1−ϵ,p2)中，也不在X(p1,p2−ϵ)中，而在X(p1+ϵ,p2)和X(p1,p2+ϵ)中，那么p是σ的临界点。再次为了简单起见，我们假设在这种情况下σ∈X(p)。温顺的一个结果是每个单形有有限多个临界点。因此，我们可以通过指定X中每个单形的临界点集合来表示有限单纯复合X的双单调序列。在所有单形的临界点上的数量之和称为双单调序列的大小。因此，我们在本文中始终假设双单调序列总是以这种形式表示的；特别是，我们在整个本文中都假设了温顺。生成双单调序列的一个标准例子是通过具有以下性质的任意函数F:X→R2。如果τ�σ是X的两个单形，那么F(τ)≤F(σ)。我们定义子水平集XF(p)为0XF(p):={σ∈X|F(σ)≤p},0并让XF表示其对应的子水平集双单调序列。很容易验证XF产生了一个（温顺的）双单调序列，而F(σ)是单形σ在双单调序列中的唯一临界值。0双单调序列的切片。双单调序列X包含一个无限的单调序列集合。让L是R2中所有斜率为正的非垂直线的集合。固定任意的线ℓ∈L，我们观察到当沿着这条线的正方向遍历时，双单调序列的子复合是相互嵌套的。注意ℓ与反对角线x=−y相交于一个唯一的基点b。将ℓ参数化为b+λ∙a，其中a是ℓ的（正的）单位方向向量，我们得到了单调序列0Xℓ(α):=X(b+α∙a).0我们将把这个单调序列Xℓ称为X在ℓ上的一个切片（有时也称ℓ本身为切片，滥用符号）。切片的临界值可以通过计算的方式推断出双单调序列的临界点。我们不会给出正式的描述，我们将图1作为图形描述。另外，如果双单调序列的大小为n，则它的每个切片的大小最多为n。0持久同调。单调序列X产生了一个持久图。形式上，我们通过将同调函子应用于X，得到了一个向量空间和它们之间的线性映射的序列，并使用表示理论将这个序列分解为不可分解的部分。与其展开0整个理论（例如在[45]中解释），我们在这里给出一个直观的描述。持久同调测量数据集的拓扑特征在考虑不同的尺度参数α时是如何演化的。最常见的例子涉及到Rd中的点云，其中考虑固定尺度α意味着用半径为α的球取代点。随着α的增加，数据集经历各种拓扑配置，从α=0时作为不相连的点云开始，到α趋近于∞时作为拓扑球结束；例如在R2中的示例见图2（a）。这个过程的拓扑信息可以总结为平面上的有限多重集合，称为持久图。图中的每个点对应于一个拓扑特征（例如，连通分量、隧道、空洞等），其坐标指定了特征在数据中出现和消失的尺度。如图2（a）所示，所有五个（连通的）分量在α=0时诞生（即出现）。绿色分量在α=2.5时消亡（即消失），当它与红色分量合并时；类似地，橙色、蓝色和粉色分量分别在尺度3、3.2和3.7时消亡。红色分量在α趋近于∞时永不消亡。0维持久图被定义为每个分量具有出生和死亡值作为其坐标（图2（c））。特征的持久性仅仅是它与对角线的距离。虽然我们关注分量，但这个概念可以推广到更高的维度，比如隧道（1维同调）和空洞（2维同调）。例如，在图2（a）中，一个隧道在α=4.2时出现，在α=5.6时消失，这在1维持久图中产生了一个紫色点（4.2,5.6）（图2（c））。从计算的角度来看，由球的并集形成的嵌套空间序列（图2（a））可以通过取它们的神经元来替换为单纯复合的嵌套序列，从而形成单纯复合的单调序列，它捕获了相同的拓扑信息，但占用的空间更小（图2（b）。在形状分析的背景下，我们应用持久同调来捕获2D和3D形状对象的拓扑信息，通过使用各种类型的单调序列。图3中举了一个简单的例子：我们从2D形状对象的边界中提取采样的点云，并使用Vietoris-Rips复合过滤器计算持久图。0持久同调的稳定性。瓶颈距离表示持久图之间的相似度度量。设D，D′是两个持久图。不失一般性，我们可以假设两者都包含无限多个对角线上的点的副本。D和D′之间的瓶颈距离定义为0dB（D，D′）:=infγ supx∈D∥x−γ（x）∥∞，（3）0其中γ遍历从D到D′的所有双射。我们还将使用dB（X，Y）表示两个单调滤波的瓶颈距离，而不是dB（D（X），D（Y））。持久同调的一个关键结果是稳定性定理，已在[46]中证明，并以我们的符号重新表述如下。给定两个函数f，g：X→R，其次级集形成有限单纯复合X的两个单调滤波，诱导的持久图满足0dB（Df，Dg）≤∥f−g∥∞:=supσ∈X|f（σ）−g（σ）|。（4）0单调滤波的特征映射。文献中提出了几种旨在构造单调滤波核的特征映射[21–23]。我们讨论一个例子：持续尺度空间核[21]将一个单调滤波X分配给一个在�（1）上定义的L2-函数φX：=�（x1，x2）∈R2|x10，对于任意大小为n的单调滤波X和任意x∈�（1），0≤φX（x）≤v1∙n。0•利普希茨性。存在一个常数v2>0，对于任意大小为n的单调滤波X和任意x，x′∈�（1），|φX（x）−φX（x′）|≤v2∙n∙∥x−x′∥2。0•内部稳定性。存在一个常数v3>0，对于任意大小为n的一对单调滤波X，Y和任意x∈�（1），|φX（x）−φY（x）|≤v3∙n∙dB（X，Y）。0•效率性。对于任意x∈�（1），φX（x）可以在X的大小的多项式时间内计算，即在O（nk）对于某个k≥0。0很容易验证，上面的尺度空间特征图满足所有这些性质。例如，如果高斯峰被线性峰所取代（即在（5）中用三角形核替换高斯核），情况也是如此。03. 多参数持续同调的特征映射0设φ为一个特征映射（例如尺度空间核），它将单调滤波映射到L2(�(1))中的函数。从φ开始，我们构造一个特征映射�，它在所有双调滤波�上的值在Hilbert空间中。特征映射�将双调滤波X分配给一个函数�X:�(2)→R。我们设定0�(2):=�(p,q)|p∈R2,q∈R2,p 0和δ∈[0,1]，使得0∥�X−�Y∥L2≤C∙nδ∙dmatch（X，Y）0对于所有的双滤波X和Y，那么�是平凡的。0证明。假设相反，存在一个双滤波X，使得∥�X∥L2>0。然后，写O表示空的双滤波，通过可加性，我们得到∥��ni=1X−�O∥L2=n∥�X−�O∥L2> 0。0C∙nδ∙dmatch（X，O）0C∙dmatch（X，O）0n→∞−→∞，0矛盾。□2 2 ̸06 R. Corbet, U. Fugacci and M. Kerber et al. / Computers & Graphics: X 2 (2019) 10 0 0 050图4.多参数持久同调特征映射的构造示意图。（a）给定双滤波X和点（p，q）∈�（2），描绘通过它们的直线ℓ，并计算参数λp和λq。（b）点（λp，λq）被嵌入Xℓ的持久图中，Xℓ是沿着ℓ的切片得到的。（c）点（λp，λq）通过特征映射φ被赋予值φXℓ（λp，λq）。0a b0图5.（a）给定的两个切片实现了穿过粉色箱子对的所有切片中最大和最小的斜率。很容易看出，中心线的单位向量与这两条线中的一条的单位向量的差实现了给定箱子对的A。（b）计算箱子对的中心切片和穿过切片的变化。05.可近似性0我们提供了一个近似算法来计算两个双滤波X和Y的核，直到任意误差ϵ>0。回想一下，我们的特征映射�取决于边界框R的选择。在本节中，为了简单起见，我们假设R是单位正方形[0,1]×[0,1]。我们证明了以下定理，显示我们的核构造接受一个多项式时间的有效近似方案，该方案与1/ϵ和双滤波的大小成多项式关系。0定理5.假设φ绝对有界，Lipschitz，内部稳定且可有效计算。给定大小为n且ϵ>0的两个双滤波X和Y，我们可以计算一个数字r，使得r≤�X，Y��≤r+ϵ，该计算在n和1/ϵ的多项式时间内完成。0定理5的证明将在以下段落中进行说明，将大部分技术细节推迟到附录A中。0算法。给定大小为n且ϵ>0的两个双滤波X和Y，我们的目标是通过某个数字r有效地近似�X，Y��。在最高级别上，我们计算一系列逼近区间（长度递减）J1，J2，J3，...，每个区间都包含所需的核值�X，Y��。计算在找到宽度最多为ϵ的某个Js时终止，此时我们返回左端点作为r的近似值。对于s∈N（N为自然数集），我们计算Js如下。我们将R分成2s×2s个相等的正方形（每个的边长为2−s），我们称之为箱子。当s=3时，请参见图5（a）的示例。我们称这样的一对箱子为箱子对。然后，从（1）中的积分可以分解为所有24s个箱子的积分之和。0�X，Y�� = �0�（2）�X�Y dμ = �0（B1，B20�0�（2）∩（B1×B2）�X�Ydμ。0对于每一对箱子，我们计算积分的近似区间，并使用区间算术将它们相加，得到 J s。我们首先给出�X，Y�的一些（几乎平凡的）边界。让（B1，B2）是中心位于c1和c2的一对箱子。通过构造，vol（B1×B2）= 2-4s。由于φ的绝对有界性，我们有�0�（2）∩（B 1×B 2）� X� Y d μ≤ �0（B 1×B 2）0� 1 √02 v 1 n ∙  √02 v 1n �0d μ（7）0= v 2 102 vol（B 1× B 2）= v 2 1 n 202 4 s + 1，（8）02 4 s + 1。如果c 1 ≤  c 2，则我们可以选择[0，U]作为近似区间。否则，如果c 1�≤ c 2，则�（2）∩（B 1×B2）=�；我们只需选择[0,0]作为近似区间。我们可以推导出�X，Y��的第二个下限和上限如下。我们在中心对（c 1，c 2）处评估� X和�Y，这是由于φ的效率假设而可能的。让v X = � X（c 1，c 2）和v Y = � Y（c 1，c2）。然后，我们计算相对于盒子对的变化δ X，δ Y≥0，满足对于任意对（p，q）∈B 1×B 2，� X（p，q）∈[v X −  δ X，v X + δ X]，�Y（p，q）∈[v Y −  δ Y，v Y + δ Y]。换句话说，变化描述了� X（或� Y）的值在B1×B 2内与其在（c 1，c2）处的值相差多远。结合从（7）开始的推导，我们对于B 1×B2内的任意对（p，q），得到0max { 0，（v X −  δ X）（v Y −  δ Y）}（9）. (11) 2 ∥ a − a ′ ∥ ∞ + ∥ b − b ′ ∥ ∞ ˆ ℓ ˆ ℓ ′ . D ≤ 2+ v 1 nW + v 2 nL. (12) s 0 � s =1 O 2 4 s poly (n ) . 0R. Corbet，U. Fugacci和M. Kerber等人/计算机与图形学：X 2（2019）100 0 05 70≤ � X ( p , q )� Y ( p , q )（10）0≤  min� v 2 1 n 02，（v X + δ X）（v Y+ δ Y）�0通过将（9）中获得的边界乘以�（2）∩（B 1×B 2）的体积，我们得到盒子对（B1，B 2）上的� X�Y的积分的下限和上限。通过对所有可能的盒子对求和，得到的下限和上限是Js的端点。0变化。我们需要计算相对于盒子对的变化。为简单起见，我们设置δ：=δX，并仅对X解释该过程；Y的处理类似。我们说一个切片ℓ穿过（B 1，B2），如果它至少在一个点与两个盒子相交。其中一个这样的切片是中心切片ℓc，它是通过c 1和c2的切片。有关说明，请参见图5（b）。我们将D设置为中心切片和穿过盒子对的每个其他切片的最大瓶颈距离（更准确地说，是沿着相应切片的持久图的距离）。我们将W设置为中心切片和穿过盒子对的任何其他切片的权重的最大差异，其中权重w的定义如第3节所述。将λ c 1表示中心切片上c1的参数值。对于穿过盒子对的任何切片ℓ和任何点p∈ℓ∩B 1，我们有一个值λp，得到沿着ℓ的p的参数值。我们定义L 1为λ p和λ c1在所有p和ℓ的选择中的最大差异。我们以相同的方式为B 2定义L2，并设置L：=max {L 1，L 2}。有了这些符号，我们得到下面的引理6。0引理6.对于所有（p，q）∈B 1×B 2，0| � X ( p , q ) −  � X ( c 1 , c 2 ) |n √02 D + v 1 nW + v 2nL。0证明。将(6)代入并使用三角不等式，我们得到0| 20= ��  ˆ ℓ φ X ℓ ( λ p , λ q ) − ˆ ℓ c0≤ ˆ ℓ �� φ X ℓ（λ p，λ q）−  φ X ℓ c（λ p，λ q）��+ℓ c ��0+ ˆ ℓ c �� φ X ℓ c ( λ p , λ q ) −φ X ℓ c ( λ c 1 , λ c 2 ) ��0并分别限制三个部分。第一个求和项上界为v 3 nD√02是因为特征的内部稳定性0映射φ和因为ˆ ℓ ≤ 1 √02对于任意切片ℓ。第二个总和-0项上界为v 1 nW，由于φ的绝对有界性。第三项上界为v 2 nL，因为∥（λ p，λq）−（λ c 1，λ c 2）∥2 ≤√02 ∥ ( λ p , λ q ) −  ( λ c 1 , λ c 2 ) ∥ ∞ ≤  L，并且由于φ是Lipschitz的，�� φ X ℓ c (λ p , λ q ) −  φ X ℓ c ( λ c 1 , λ c 2 ) ��  ≤ √02 v 2 nL，且ˆ ℓ ≤ 1 √02 . 结果如下。□0sult follows. □0接下来，我们用简单的几何量来界定D。我们使用以下引理，其证明出现在[48]中：0引理7。[48]设ℓ和ℓ'是两个带有参数化b + λa和b' +λa'的切片。那么沿着这些切片的两个持续图的瓶颈距离上界由0我们将A定义为中心切片ℓc的方向向量的最大无穷距离和任何其他切片ℓ之间的最大无穷距离。我们将B定义为ℓc的基点和任何其他ℓ之间的最大无穷距离。最后，我们将M设置为最小权重0在所有穿过箱子对的切片中。使用引理7，我们看到0M ˆ ℓ c，0我们设置0δ：= v 3 n ( 2 A +B ) √0从引理6和7可以得出，δ确实满足所需的变化性质。我们注意到，如果箱子对允许一条穿过的切片是水平或垂直的，那么δ很可能等于∞，在这种情况下，从变化中导出的下界和上界是空虚的。虽然（12）看起来很复杂，但值v1，v2，v3是来自考虑的特征映射φ的常数，所有其余的值都可以使用箱子对的基本几何属性在常数时间内计算出来。我们只解释了图5（a）中A的计算，并略过了其他值的细节。0分析。在这一点上，我们并没有声称算法保证终止。然而，它的正确性立即就能得出，因为Js确实包含了所需的核值。此外，处理一个箱子对的复杂度是n的多项式，因为主导步骤是在中心（c1，c2）处评估�X。因此，如果算法在迭代s0处终止，其复杂度是0这是因为在迭代s中，需要考虑2 4s个箱子对。显然，上面的几何级数由最后一次迭代主导，因此该方法的复杂度为O（2 4 s 0poly（n））。最后（也是技术上最具挑战性的一步）是要证明s0 = O（log n + log 10ϵ )，这意味着算法确实终止，并且其复杂度在n和1/ϵ中是多项式的。为了看到我们可以实现核值的任意精度，即间隔宽度趋于0，我们观察到，如果两个箱子B1，B2足够远，并且分辨率s足够大，则（12）中的幅度A，B，W和L都很小，因为穿过箱子对的两个切片的参数化是相似的（见附录A中的引理11-14）。此外，如果穿过箱子对的每个切片具有足够大的权重（即切片靠近对角线），则（12）中的值M足够大。这两个性质的结合意味着这样一个箱子对的变化（我们称之为好类型）随着s趋于∞而趋于0。因此，基于变化的界限趋于对好箱对的正确值。然而，无论分辨率有多高，总会有一些坏的箱子对，其中B1，B2要么靠近，要么远但接近水平和垂直，因此产生非常大的变化。对于这些箱子对中的每一个，从变化中导出的界限是空虚的，但我们仍然有基于φ的绝对有界性的平凡界限[0，U]。此外，当s趋于∞时，这些坏箱对的总体积趋于0（见附录A中的引理9和10）。因此，这些箱对的贡献趋于0。这两个性质完成了定理5的证明。我们对我们算法的复杂性进行更仔细的调查表明，我们的算法的复杂性是O（n80+k（1/ϵ）40），其中k是特征映射的效率常数（第2节）。我们没有太多努力来优化这个界限中的指数。06. 结论和未来发展0我们重新陈述了多滤波器X具有d个参数的主要结果：存在一个特征映射，将Xs := �log c + e 1 log n + log 1 ϵe 2 �= O �log n + log 1 ϵ�⟨X , Y⟩ � = ⟨X , Y⟩ null + ⟨X , Y⟩ close + ⟨X , Y⟩ non −diag + ⟨X , Y⟩ good , width (J close ) ≤ v 2 1 n 2 2 vol (B close ) . (A.1) vol (B close ) ≤ 4 πu . ∥ p − q ∥ 2 ≤ ∥