从低维类模型集合中选择对象类的特定模型的方法

摘要

从类的低维模型集合中选择对象类的特定模型，其中模型是图，每个图包括表示类中对象的多个顶点和连接这些顶点的边缘。测量类中对象的高维样本子集之间的第一距离。将第一距离与类的低维模型集合组合，以产生受第一距离约束的模型子集，并且从模型子集中选择具有最为分散的顶点的特定模型。

说明书

技术领域

本发明一般涉及对采样数据建模，特别是涉及用低维模型表示高维数据。

背景技术

如图1所示，非线性降维(NLDR)从高维采样数据101产生低维表示120。数据101对嵌入在环境空间R^D 110中的d维流形(ddimensional manifold)M 105采样，其中D＞d。目的是将嵌入的非本征几何(即流形M 105如何在环境空间R^D内成形)与它的本征几何(即流形M的d维坐标系120)分开115。流形可以表示104为具有由边缘(edge)130连接的顶点125的图，如图理论领域中所熟知的。顶点125表示高维坐标系内流形上的采样数据点101，而边缘130为连接顶点125的线或弧。因此，图被嵌入流形。术语“图”(graph)不应该与如在解析几何内的函数图(即曲线图(plot))相混淆。

例如，如果已知诸如人的面部之类的对象的流形怎样嵌入面部图像的环境空间，就可用模型的本征几何对面部图像进行编辑、比较和分类，而可用非本征几何来检测图像内的面部和合成新的面部图像。

作为另一个例子，可用嵌入在语音空间内的元音对象的流形来对元音内的声音变化的空间建模，这可用来区分元音的类(class)。

已知的通过嵌入图和将数据流形浸在低维空间内产生高维数据的低维模型的频谱法由于约束集合不充分和/或约束集合在数字方面情况不好从而是不稳定的。

在度量约束下嵌入图在NLDR、自组织无线网络映射和关系数据的视觉化中是一种频繁操作。尽管在频谱嵌入法方面有一些进步，但现有技术的NLDR方法还是不实际和不可靠的。与NLDR关联的一个困难是自动产生使问题能被很好提出、很好调整和用切合实际的时间可解决的嵌入约束。很好提出的约束保证唯一解(solution)。很好调整的约束使解在数字上可与次最优解可分开。

两个问题表现为在嵌入约束的谱中特征间隙(eigengap)很小甚至为零，这表明图(即模型)实际上是非刚性(non-rigid)的，并且存在解的特征空间，在该空间中最优解难以与其他解分开。很小的特征间隙使得很难甚至不可能将一个解与它的变形模式分开。

图嵌入

在拉普拉斯算符那样的局部到整体的图嵌入中，每个图顶点的嵌入受该顶点的近邻(即，在图理论术语中，顶点的1-环)的嵌入的限制。为了降维，顶点是从在环境高维样本空间内以某种方式卷起(roll-up)的流形采样的数据点，而图嵌入约束被设计成再现该流形的局部仿射结构，同时将流形在较低维的目标空间内“打开”。

现有技术的局部到整体的图嵌入的例子包括：Tutte的方法，见W.T.Tutte的“How to draw a graph”，Proc.London MathematicalSociety，13：743-768，1963；拉普拉斯特征映射，见Belkin等人的“Laplacian elgenmaps for dimensionality reduction and datarepresentation”，volume 14 of Advances in Neural InformationProcessing Systems，2002；局部线性嵌入(LLE)，见Roweis等人的“Nonlinear dimensionality reduction by locally linear embedding”，Science，290：2323-2326，December 22 2000；Hessian LLE，见Donoho等人的“Hessian eigenmaps”，Proceedings，National Academy ofSciences)；作图，见Brand的“charting amanifold”，Advances inNeural Information Processing Systems，volume 15，2003；线性正切空间对准(LTSA)，见Zhang等人的“Nonlinear dimension reductionvia local tangent space alignment”，Proc.，Conf.on Intelligent DataEngineering and Automated Learning，number 2690 in Lecture Noteson Computer Science，pages 477-481，Springer-Verlag，2003；以及短程线零空间分析(GNA)，见Brand的“From subspaces tosubmanifolds”，Proceedings，British Machine Vision Conference，2004。

以上所列的最后这三种方法构成最大可能秩的局部仿射约束，导致基本上稳定的解。

LTSA和GNA取嵌入在环境空间R^D中的N顶点图，顶点位置为X＝[x₁，...，x_N]∈R^D×N，并将图重新嵌入较低维空间R^d，新的顶点位置为Y＝[y₁，…，y_N]∈R^d×N，保留局部仿射结构。通常，通过某种试探法从点数据(诸如k个最近邻居)构成图。

嵌入如下工作。取k个点的一个这样的邻域，用例如局部主分量分析(PCA)构成局部d维坐标系X_m[x_i，x_j，...]∈R^d×k。PCA产生一个具有与坐标系X_m的行和常数向量1正交的正交列的零空间矩阵Q_m∈R^k×(k-d-1)。这个零空间(nullspace)还与局部坐标系的任何仿射变换A(X_m)正交，使得维护局部坐标系内平行线的任何变换、旋转或延伸都满足A(X_m)Q_m＝0。于是，任何其他变换T(X_m)可以分离成一个仿射分量A(X_m)加上非线性失真N(X_m)＝T(X_m)Q_mQ_m^T。

LTSA和GNA方法将零空间投影Q_mQ_m^T，m＝1，2，...汇编成在图内所有邻域上对非线性失真求和(LTSA)或加权平均的稀疏矩阵K∈R^N×N。

嵌入基(embedding base)V∈R^d×N具有正交的并横越[K，1]的列零空间的行向量；即，VV^T＝I和V[K，1]＝0。可以得出，如果嵌入基V存在并且作为将图嵌入R^d的基础提供，则该嵌入中的每个邻域将相对它的原始局部坐标系具有零非线性失真，见以上Zhang等人的论文。

此外，如果邻域充分交叠，使得图在R^d内成为仿射刚性的，那么从原始数据X到嵌入基V的变换就以相同的方式“伸展”图的每个邻域。然后，线性变换T∈R^d×d消除该伸展，给出较低维顶点位置Y＝TV，使得从较高维数据X到较低维嵌入Y的变换只包括局部邻域的刚性变换，即嵌入Y是等距的。当在这过程中有任何类型的噪声或测量误差时，可以通过K∈R^N×N的瘦奇异值分解(SVD)或K的零空间的瘦特征值分解(EVD)(即KK^T)得到最小平方最佳近似嵌入基V。由于矩阵K是非常稀疏的，具有O(N)个非零值，迭代子空间估计器通常呈现O(N)倍缩放。在稀疏矩阵K用GNA构成时，对应的奇异值S^N-1，S_N-2，...测量按维的在点范围上的平均失真。

现有技术的图嵌入的核心问题之一是KK^T以及局部NLDR中的任何约束矩阵的特征值在λ₀＝0附近(其是提供嵌入基V的谱的末端)二次性增长，附录A是KK^T的特征值的二次增长的证明。二次增长意味着特征值曲线在谱的低端几乎是平坦的(λ_i+1-λ_i≈0)，使得将嵌入基与其他特征向量分离的特征间隙可以忽略。在简单的图拉普拉斯算符的谱内可以观察到类似的结果，它们也是S形的，在零附近二次增长。

在图嵌入中，约束矩阵起着与有限元方法中的硬度(stiffness)矩阵类似的作用，而且在两种情况下都是与零附近的特征值关联的特征向量规定了最佳参数化，即解，以及解的次最佳失真模式，也称为“振动”。面对特征解算器(eigensolver)或任何其他零空间估计器的问题是收敛速度是相对特征间隙 $>>>|>>\lambda >c>>->>\lambda >>c>+>1>>>|>>>>\lambda >max>>->>\lambda >min>>>>>s>或所需与其余主特征值之间的特征比(eigenratio)的线性函数，见Knyazev的“Toward The optimalpreconditioned eigensolver”，SIAM Journal on Scientific Computing，23(2)：517-541，2001。特征向量的数字稳定性同样取决于特征间隙。如上面所说明的那样，对于局部到整体的NLDR来说，特征间隙和特征比两个都非常小，使得难以将解(即高维数据的最佳低维模型)与解的失真模式(即振动)分开。$

直观上，低频率振动造成图内一些非常平滑的弯曲，它们在局部约束层次产生非常小的变形的不利后果。由于图的特征值将那些不利后果加了起来，与变形的低频率模式关联的特征值具有非常小的值，导致不良的数值调整和特征解算器的缓慢收敛。在精细邻域结构导致紧密间隔的特征值的情况下，这个问题在规模上增大成较大的问题，使得迭代特征解算器不能精确确定表示最优最佳解(即振动最小甚至没有振动的最佳模型)的最小特征值和向量。

因此，需要有一种从对象类的低维模型集合中选择特定的低维模型的方法，其中低维模型集合是从高维采样数据得出的。

发明内容

本发明从类的低维模型集合中选择对象类的特定模型，其中模型是图，每个图包括表示类中对象的多个顶点和连接这些顶点的边缘。测量类中对象的高维样本子集之间的第一距离。将第一距离与类的低维模型集合组合，以产生受第一距离约束的模型子集，并且从模型子集中选择具有最为分散的顶点的特定模型。

附图说明

图1为非线性降维的基本步骤的方框图；

图2为产生对象类的低维模型集合的现有技术方法的方框图；

图3为按照本发明设计的从表示对象类的模型集合中选择特定模型的方法的方框图；

图4为按照本发明设计的递归邻域扩张的方框图；

图5为表示对象类的非刚性图的框图；以及

图6为按照本发明的根据高维数据从表示对象类的低维模型的集合中选择特定模型的方法的框图。

具体实施方式

用NLDR产生输入类模型

本发明取对象的低维模型集合中的一个，即下面还要详细说明的表示对象类的局部到整体嵌入的集合，作为输入。模型集合用非线性降维(NLDR)产生。在优选实施例中，模型集合用短程线零空间分析(GNA)或可任选的线性正切空间对准(LTSA)产生，因为所有其他已知的局部到整体嵌入方法均采用LTSA和GNA的仿射约束的一个子集。

图2示出了一种用短程线零空间分析(GNA)产生模型301的集合的现有技术方法，这种方法可参见本申请的受让方拥有的2004年9月2递交的美国专利申请No.10/932,791“Method for generating aLow-Dimensional Representation of High-Dimensional Data”，该申请全部在这里列为参考予以引用。为了用GNA产生模型301的输入集合，从嵌入在环境空间中的d维流形对在高维环境空间R^D内存在的类中的对象201进行采样210，其中D＞d，从而产生样本211的集合。例如，样本211是一些面部图像。对于每个面部有至少一个图像(样本)。每个样本包括表示对象特征的多个数据值，例如图像内像素的亮度值，或许还有颜色。因此，每个样本可以包括好几百万的数据值。每个样本的数据值被组织成向量。对于图像来说，这可以用传统的扫描线变换实现。NLRD的目标是分离嵌入的非本征几何。也就是说，希望从流形的本征几何，即流形上的原有(native)d维坐标系，确定流形在环境空间R^D内的形状。

流形对于目标空间R^d的开子集是局部等距的(isometric)，并且通过未知的二次函数C²嵌入在环境欧几里得空间R^D＞d中。流形M是环境空间R^D的黎曼几何子流形。

流形在环境空间R^D内具有非本征曲率，但是零特征曲率。然而，流形在目标空间R^d内的等距浸入可以具有带凹边界的不平凡形状。

用X[x₁，…，x_N]∈R^D×N表示的样本集合211记录了在环境空间R^D内流形的N个样本的位置。

样本集合Y_iso[y₁，...，y_N]∈R^d×N的等距浸入消除了集合的非本征曲率，以便恢复等距直到目标空间R^d中的刚性运动。

将样本211组成220一些样本子集，即邻域，使得每个子集与至少一个其他子集交叠。每个样本子集具有k个样本，其中k可以不同。当且仅当第n个点在第m个子集内，成组(grouping)220由邻接矩阵M＝[m₁，...，m_M]∈R^N×M确定(M_nm＞0)。

为每个样本子集221确定230子集参数化X_m∈R^d×k231。子集参数化231可以含有在第m个子集内的k个样本的局部等距参数化。参数化内的欧几里得成对距离等于流形上的最短程线距离。

在进行最短程线零空间分析时，对等距低维参数化的零空间加以平均240，以得到具有包含对象类的低维模型301集合的零空间的矩阵。本发明的一个目的是提供一种从模型301集合中选择特定模型331的方法。可以理解，集合301内的每个模型可以用在低维目标空间Rd内的对象的图表示。本发明改善了现有技术的从集合301中选择特定模型的方法。

邻域扩展

利用施加到嵌入在环境空间R^D中的d维流形图中顶点和边缘的扩展子集上的较长范围约束，本发明有效地硬化了低维目标空间R^d内对象的图(即模型)的顶点和边缘的网状结构(mesh)。

如图3所示，按照本发明的方法300使从模型301的集合中选择的模型302的样本子集成组310。子图311包括所选择的模型302(即，表示嵌入在环境空间R^D中的d维流形的图)的顶点和边缘的交叠邻域的集合。对于从子图中选出的锚顶点312-315的集合，确定320子图参数化321。在优选实施例中，锚顶点是子图周边上的顶点，然而，锚顶点的位置并不局限于周边。将子图参数化321与模型301的输入集合组合，以识别特定模型331。

如上面对图2所作的说明那样，在对原始样本集合210施加GNA时，对等距低维参数化的零空间进行平均，以得到具有包含对象类的低维模型301集合的零空间的矩阵。回到图3，按照本发明的一个实施例的组合330对子图参数化321的零空间和输入模型301集合的零空间进行平均。由于在距离分开得比原始样本子集221大的样本之间确定子图参数化321，因此不在零空间内的特征值在组合330后具有较大的值，从而增大了特定模型331与模型集合301内其余模型之间的特征间隙。

如图4所示，通过为近似或完全覆盖401所选择的模型302的多个子图311确定参数化，本发明可以应用于整个所选择的类模型302，但是只对所有顶点中的一个小的子集例如锚顶点增添一些约束。多个子图的参数化用与图3所示的相同方式加以组合330。可以以递归方式对所选择的模型302应用尺寸增大的进一步子图参数化402。尺寸较大的子图的锚顶点只从先前递归的锚顶点中选择。

在优选实施例中，对于每个子图尺寸，选择顶点中的恒定比例的顶点作为锚顶点，例如独立于子图的尺寸，为每个递归选择1/4的顶点。

如果在每个递归将子图和锚顶点的数目减半，则可以在不多于K矩阵内非零数的数目加倍的O(N)次中执行多级硬化。

用边缘长度约束来规则化低维类模型

即使对模型(即图)进行硬化，也可能存在这个图本质上是非刚性的情况。这一般在用诸如k个最近邻居之类的试探法产生图时发生。在这样的情况下，嵌入基V∈R^c×N具有比目标空间R^d大的维c(c＞d)。例如，如图5所示，如果具有d＝2的模型510的顶点和边缘的子集501是共线的(co-linear)，它们产生轴502，允许在R^d中流形内的各种折叠(fold)，例如图内的折叠503。在这种情况下，模型的集合横跨所有可能的折叠形态504。因此，嵌入姿态不良，需要进行规则化来从模型的集合中选择最为打开的模型。

图6示出了从模型集合602中选择具有分散最开的顶点的模型631，即最打开的图。对高维样本601的子集之间的第一距离611进行测量610。可以理解，高维样本与低维模型中的顶点对应。将第一距离与模型集合组合620。组合620标识了受第一距离约束、具有在与高维样本的子集对应的顶点之间的距离的模型的子集。在优选实施例中，第一距离标识了具有受第一距离约束的边缘长度的模型的子集。从模型子集中选择630所有顶点之间的距离最大的特定模型631。在优选实施例中，在特定模型中每个顶点与每个顶点的所有4跳邻居之间的距离达到最大。因此选择作为模型的最打开的图满足在矩阵K内编码的仿射约束，使在互斥顶点子集之间的距离达到最大，并满足对特定边缘子集的精确距离约束。

任选的是，可以将高维样本601的第二子集之间的距离的第二集合612与特定模型631内对应的距离例如边缘长度相比较。如果与高维样本的第二子集对应的顶点之间的距离受第二距离约束，就存在匹配650，确认特定模型的选择630是正确的。如果没有匹配，则重复651方法，其中第二距离612与模型集合和第一距离组合620。

形式上，混合矩阵U∈R^c×d具有任意非零范数的正交列。误差向量σ＝[σ₁，...，σ_c]^T含有与其左奇异向量相关联的矩阵K的奇异值，即嵌入基V的行。混合矩阵U从由嵌入基V的行跨越的可能解的空间中选择度量正确的嵌入。

目标嵌入Y＝[y₁，…，y_N]U^TV∈R^d×N具有总失真‖U^Tσ‖和任何两个顶点之间的距离‖y_i-y_j‖＝‖U^T(v_i-v_j)‖(v_i为嵌入基V的第i列)。优化问题是使失真减到最小，同时使分散达到最大

$>>>U>*>>=>>max>U>>->>>|>|>>U>T>>\sigma >|>|>>2>>+>>\Sigma >pq>sup>>r>pq>2sup>>>>|>|>>y>p>>->>y>q>>|>|>>2>>->->->>(>1>)>>>s>$

对于加权r_pq≥0的特定选择，使距离_{ij∈EdgeSubset}‖y_i-y_j‖≤D_ij         (2)

保持在形成R^d内非零列单形体(simplex)的至少d个边缘上，否则嵌入在有些维就可能崩溃。边缘长度可以是不相等的，因为作为直线距离测量的边缘距离D_ij是在环境空间R^D内的弦而不是在流形内的最短线，因此可能与低维嵌入不一致。

这种不相等允许有些边缘稍有缩短，以有利于散得更开从而更平坦的低维嵌入。实施与图中边缘的所有或随机样本对应的距离约束。距离约束不必形成连通图。

恒等式‖Y‖_F²＝‖U^TV‖_F²＝trace(U^TVV^TU)＝trace(VV^TUU^T)应用于式1-2产生对客体的半定程序(SDP)：

$>>>max>G>>trace>>(>>(>C>->diag>>>(>\sigma >)>>2>>)>>G>)>>->->->>(>3>)>>>s>$

$>>with>>ver>>=>.>>>\Sigma >pq>>sup>>r>pq>2sup>>>(>>v>p>>->>v>q>>)>>>>(>>v>p>>->>v>q>>)>>T>>->->->>(>4>)>>>s>$

$>>>\forall >>i>,>j>\in >EdgeSubsct>>>trace>>(>>(>>v>i>>->>v>j>>)>>>(>>v>i>>->>v>j>>>)>T>>G>>)>>\le sup>>D>ij>2sup>>->->->>(>5>)>>>s>$

特别是，如果所有顶等斥(_pqr_pq＝1)，则C＝VV_T＝I，而且trace(CG)＝∑_pq‖y_p-y_q‖²＝‖Y‖_F²。由于V1，嵌入是居中的。

在c＝d的极值处，在U＝T是对等距的升级的情况下，SDP是不必要的。在c＝D-1，施加半定图嵌入，其中range(V)＝span(R^N1)代替居中约束，因此LTSA/GNA是不必要的。其间，有称为非刚性对准(NA)的调和。利用迭代特征解，LTSA/GNA取O(N)倍，但是需要整体刚性的约束集合。半定图嵌入不需要刚性约束，但是具有O(N⁶)倍的缩放。

非刚性对准

非刚性对准(NA)用LTSA/GNA构建大大缩小半定程序的嵌入基。此外，将不完全的邻域集合与不完全的边缘长度约束集合组合的选项是可行的，这进一步简化了两个问题。虽然这种方法需要初始LTSA/GNA的局部维的估计，但这种方法从半定图嵌入继承了较高维数据X的谱给出整体嵌入维的陡峭估计的特性，因为嵌入是由嵌入基V跨越的。局部维可以过估计，这降低了局部零空间维，从而降低了整体刚性，但是能因此在SDP问题上有附加的自由度。

减少SDP约束

可以以矩阵向量形式将SDP等式约束改写为A^Tsvec(G)＝b，其中svec(G)用对角线外的元素乘以，从X的上三角形成列向量。在这里，约束矩阵A的每个列含有对于特定边缘ij的向量化边缘长度约束(例如，对于等式约束的svec((v_i-v_j)(v_i-v_j)^T)；向量b的对应元素含有值D_ij²。SDP解算器的主要花费在对可能有大量线性冗余列的矩阵 $>>A>\in >>R>>>c>2>>\times >e>>>>s>的操作上。$

在问题具有精确解(式5作为等式是合理的)时，这花费可以通过投影减小：设F∈R^e×f，f＜＜e对于约束矩阵A的主行子空间是列正交基，这可以通过瘦SVD以O(ef²c²)次估计。从Mirsky-Eckart定理可以得出f等式约束，

F^TA^Tvec(G)＝F^Tb                         (6)

是原始等式约束的等效或最小平方最佳逼近。对于大的精确可解问题，通常可以将约束集合的基数(cardinality)降低97％，而没有信息损失。

在问题没有精确解，即式5只可作为不等式时，SDP问题可以用随机选取的边缘长度不等式约束的小子集来求解。结合子空间V所施加的仿射约束，这足以满足大多数其余未实施的长度约束。被违反的那些可以添加给活动集合，再解SDP，重复直到全部满足。

应用于语音数据

TIMIT语音数据库是一个可广泛获得的数据库，收集了600多个说话者说出的2000多个句子的音频波形和语音录音。本发明的一个应用是对元音中声音变化的空间建模。从标准表示开始，对于在录音中标为元音的每个10毫秒帧确定D＝13mel-cepstral特征的向量。

为了降低录音误差和共发音现象，将数据缩减到每个元音段的中间一半，得到R13内大致N＝240,000个样本。多次将PCA应用于随机数据邻域表明，数据是局部5维的。具有5维邻域和25维基的7个近似最近邻居图的NA嵌入用不到11分钟的时间确定。谱是陡峭的，在7维中方差为＞99％，在5维中＞95％，而在2维中＞75％。

原始数据的PCA旋转分别在13、9和4维与这些百分比匹配。注意到所估计的局部维度和整体嵌入维度之间的偏差，引入了具有少量不利的松弛变量来研究图没有完全打开的可能性。

在语音识别中的长期经验法则是全协方差高斯型(Gaussian)与3或4个对角协方差高斯型[LRS83]的混合体竞争。重要的经验问题是，NA表示是否提供比PCA更好的类分离。这可以通过对每个音素类应用高斯型并计算各类之间经对称化的KL发散性加以量化(与任何下游语音处理无关)。

较高的发散性意味着需要较少的比特来描述由(高斯型)二次分类器形成的分类错误。在d＝5NA表示中的类之间发散性平均为在d＝5PCA表示时类之间发散性的2.2倍，而没有NA表示变得不好的实例。对于d的其他值甚至d＝1和d＝D也可观察到类似的优点。

虽然本发明是以优选实施例为例进行说明的，但可以理解，在本发明的精神实质和专利保护范围内可以作出各种其他调整和修改。因此，所附权利要求书的目的是将所有这样的变动和修改包括在本发明的精神实质和专利保护范围之内。

附录A

可以将约束矩阵K看作对候选嵌入Z与滤波器的卷积的离散近似。如果画出K的列，这个滤波器就类似一个逆拉普拉斯算符。分析表明确实是这种情况：

命题4设Z[z₁，...，z_N]∈R^d×N，z_i＝z(y_j)是由在本征坐标y_i上的C²多值映射z：M→R^d给出的数据参数化。设

$>>K>ver>>=>·>>>(>>\Sigma >m>>>S>m>>>Q>m>sup>>Q>m>Tsup>>diag>>(>>w>m>>)>sup>>S>m>Tsup>>)>>diag>>>(>>\Sigma >m>>>S>m>>>w>m>>)>>>->1>>>->->->>(>7>)>>>>s>$

其中二元的索引矩阵S_m∈{0，1}^N×k选择形成第m个邻域的k个点，而邻域加权向量w_m∈R^k按照点离邻域中心的距离赋予点加权： $>>>(>\{>>W>m>>>\}>i>>\infty >exp>(>->|>|>\{>>X>m>>>\}>i>>-ver>>>X>m>>‾>>|>>|>2>>/>2>>\sigma >2>>/>\sigma >)>>.>>s>K的每个列是高斯型算符的离散差，参数化误差\Vert ZK\Vert$_F²近似‖z-G*z-²G*z‖²，它本身经平滑的形式a与z之差减去它与高斯-拉普拉斯算符的卷积。

证明(命题4)为简单起见，将首先考虑每隔一定间隔采样的1D流形的情况。回想一下，K是各呈现为形式 $>>>N>m>>=>>Q>m>>>>Q>m>>T>>>s>$ >>=>I>->>1>k>>1>>1>T>>->>P>m>>>>P>m>>T>>>s>的邻域零空间投影的平均，其中P$$_k∈R^k×d为居中局部坐标的正交基。由于正交化是线性运算，因此与点i和j离群集中心的距离的乘积 $>>|>|>\{>>X>m>>>\}>i>>-ver>>>X>m>>‾>>|>|>·>|>|>\{>>X>m>>>\}>j>>-ver>>>X>m>>‾>>|>|>>s>成正比。将矩阵P$_mP_m^T的元素看作表面高度，就有一个二次的鞍表面，最大的正值在左上和右下角，而最大的负值在右上和左下角。在这种经简化的情况下，P_m＝k^-1/2·[-j，1-j，...，j-1，j]^T，其中k＝2j+1为各邻域的大小，而K的各列中的元素为N_m的对角的高斯加权和。确切地说，对于第p个非边界邻域，K的一个列内的第n个非零子对角元素为

$>>>K>>p>+>n>,>p>>>=>->>1>k>over>>\Sigma >>i>=>n>>>i>=>2>j>over>>>(>1>+>>(>i>->j>)>>>(>i>->j>->n>)>>>3>>j>>(>j>+>1>)>>>>)>>>e>>->>>(>i>->j>)>>2>>>>>s>$

$>>=>->>1>k>>>3>>j>>(>j>+>1>)>>>over>>\Sigma >>i>=>n>>>i>=>2>j>over>>\{>>(>1>->>(>i>->j>>)>2>>>)>>>e>>->>(>i>->j>>)>2>>>>>>s>$

$>>->>(>1>->n>>(>i>->j>)>>)>>>e>>->>>(>i>->j>)>>2>>>>+>>>j>>(>j>+>1>)>>>3>>>e>>->>>(>i>->j>)>>2>>>>>s>$

注意，(1-i-j)²)e^-(i-j)2为高斯-拉普拉斯算符，如果保持i＝n和对n(K内一个列的各元素)迭代，就得到各有有限支持的高斯型和LoG型的差；对i的求和给出这些各有不同支持的曲线的叠加。为了推广到不规则采样，只要将增量i加大相邻点之间的差。为了推广到多维流形，注意到以上自变量适用于形成M上短程线的点的任何子集，以及由于K和拉普拉斯算符的线性，以上自变量适用于形成不同短程线的点的不同子集的任何线性组合。

命题5I-G-²G的近零特征值二次增长

证明(命题5)考虑谐波等式，其描述图如何在与它的嵌入正交的空间内振动：-(I-G-²G)Y(x，t)＝d²Y(x，t)/d²t，Y(x，t)为时间t和位置x(在流形本征坐标内)的偏移。对于周期运动，设Y(x，t)＝sin(ωt)·Y(x)，其中Y(x)是振动模式。在代入和通约后，谐波等式简化为(I-G-²G)Y(x)＝ω²·Y(x)，确认模式Y(x)为算符I-G-²G的特征函数。可以通过代入验证Y(x)＝sin(at+b)为解(特征向量)的正交基，特征值在S形曲线 $>>>\omega >2>>=>1>->>(>1>+>>a>2>>/>>2>\pi >>)>>>e>>->>a>2>>>>>s>上，其中a\in \{1，2，...，N\}，b\in R。在a＝0附近的级数展开显示出主导项为二次的。$

证明(命题1)扩展产生新的邻域，它的参数化对于其组成邻域是仿射的，因此它的零空间与K是正交的。

证明(命题2)由于减半，在任何比例上，在每个邻域扩展中顶点的数目平均起来是一个常数v＜＜n，其仅由原始局部邻域的本征维度和平均大小确定。减半也保证了邻域扩展的总数为

证明(命题3)由于F为约束的方差保留旋转，因此总是可以旋转F＝[f₁，...，f_f]的f维行空间，使得_if_i^Tb＞0。于是，任何不可行的解可以用z＞0缩放，使得 $>>>\forall >i>>>>f>i>>T>>>A>T>>svec>>(>zver>>G>~>>)>>\le >>>f>i>>T>>b>,>>s>其中任何差由非负松弛变量构成。$