旗帜中位数的鲁棒性及其在Grassmannians上的应用

Nathan Mankovich, Emily J. King, Chris Peterson, and Michael KirbyColorado State University, Fort Collins, CO{nmank, emily.king, christopher2.peterson, and michael.kirby}@colostate.eduargminy∈Ap�i=1∥xi −y∥q2 .(1)103390旗帜中位数和FlagIRLS0摘要0找到数据集的原型（例如均值和中位数）对于许多常见的机器学习算法至关重要。子空间已被证明对于图像、视频等数据集提供有用的、鲁棒的表示。由于子空间对应于Grassmann流形上的点，人们不禁考虑Grassmann值数据集的子空间原型的概念。虽然已经描述了许多不同的子空间原型，但计算其中一些原型在计算上是昂贵的，而其他原型受到异常值的影响，在噪声数据上产生高度不完美的聚类。本文提出了一种新的子空间原型，即旗帜中位数，并介绍了FlagIRLS算法用于计算。我们提供了旗帜中位数对异常值的鲁棒性的证据，并且可以在Grassmannians上的算法（如Linde-Buzo-Grey（LBG））中有效使用它来产生改进的聚类。数值实验包括一个合成数据集、MNIST手写数字数据集、Mind's Eye视频数据集和UCFYouTube动作数据集。将旗帜中位数与计算Grassmannian上的原型的其他主要算法进行比较，即ℓ2-中位数和旗帜均值。我们发现使用FlagIRLS计算旗帜中位数在合成数据集上收敛于4次迭代。我们还发现，在Mind'sEye数据集上，使用旗帜中位数的GrassmannianLBG与代码本大小为20的GrassmannianLBG相比，聚类纯度至少提高了10%。01. 引言0均值和中位数是从概率分布中计算中心原型的基本方法。中位数通常比均值对异常值更具鲁棒性。将这些原型推广到欧几里德空间可以被看作是一个优化问题的解决方案。假设我们有一组点在欧几里德空间中，X = { x i } p i = 1 � R n，我们想要表示0通过求解将原型y表示为解决0对于A = R n和q =2的(1)的解被称为质心，可以看作是均值的推广。实际上，质心是向量X中向量的逐分量均值，即� p i = 1 x i / p。当q =1时，中位数的推广涉及求解(1)。当A =X时，解被称为中心点，而当A = Rn时，解被称为几何中位数。几何中位数继承了中位数对异常值的鲁棒性，而不需要成为数据集中的一个点；然而，与质心的计算不同，几何中位数的计算不仅仅是一个最小二乘问题。逼近几何中位数的迭代算法是Weiszfeld算法[21]；该算法的每次迭代都是一个加权质心问题。因此，Weiszfeld算法属于一类称为迭代重新加权最小二乘算法（IRLS）的算法。这些欧几里德原型被用作数据集的统计量，以及常见的机器学习算法，如k-means和最近质心分类。并非所有数据集都最适合使用欧几里德空间中的点来表示。特别是，图像或视频数据集有时更适合使用子空间，即作为Grassmannian上的点。例如，两个子空间之间的最小主角已被证明对于建模照明空间[3]非常有用。在欧几里德空间中，高光谱数据可能无法线性可分，但在Grassmannian上可以线性分离[5]。因此，将欧几里德空间中的原型推广到Grassmannian上的逻辑是用子空间之间的距离或不相似性替换优化问题中的欧几里德2范数。质心在[13]中使用测地距离进行推广，而在[9]中使用弦距离。据我们所知，我们还没有找到中心点的推广。然而，已经对几何中位数进行了推广。argmin[Y]∈Gr(r,n)d([Xi],[Y])(2)cosθi([X],[Y]) = maxx [X] maxy [Y] xT y = xTi yix xj = y yj = 0 for j = 1,2,...,i −1(3)̸103400使用测地距离进行广义化，称为 ℓ 2 - 中位数 [ 1 ,  11]。这些原型已被单独用作图像情感分类的方法 [ 24 ]，作为k-means 类型算法的一步 [ 18 ]，以及特征提取 [ 11]。流行的机器学习技术，如字典学习，已经适应了黎曼流形 [ 22]。Jayasumana 等人考虑使用 RBF 核在Grassmannian（以及黎曼流形）上进行学习，并提倡使用弦距（有时称为投影范数）核在 Grassmannian上，因为弦距生成一个正定的高斯核 [ 12 ]。最近，Cherian等人使用核化的 Grassmannian 池化进行活动识别 [ 6]。黎曼优化的方法，如黎曼SVRG，随着对黎曼学习的兴趣的增加而变得流行 [ 23]。在计算机视觉和机器学习中，子空间的更多用途可以在 [ 1 , 2 ,9 , 10 , 17 , 18 , 24 ]中找到。在本文中，我们提出了旗帜中位数，这是一种使用弦距在 Grassmannian 上的几何中位数的泛化。我们使用新颖的FlagIRLS 算法解决旗帜中位数优化问题。FlagIRLS 是Grassmannian 上的 IRLS算法，它在每次迭代中解决一个加权旗帜均值问题，类似于Weiszfeld算法的迭代解决加权质心问题的方式。我们在合成数据集、MNIST 手写数字数据集 [ 8 ]、DARPA Mind's Eye 数据集（在 [ 18 ]中使用）和 UCF YouTube 动作数据集 [ 16 ]上进行实验。在这些示例中，我们发现 FlagIRLS算法往往收敛迅速。我们展示了旗帜中位数似乎比旗帜均值和 ℓ 2- 中位数对异常值更具鲁棒性，并在 LBG 算法 [ 15 ]中产生最高的聚类纯度。02. 背景02.1. Grassmannian 简介0在本文中，Grassmannian流形（也称为“Grassmannian”），表示为 Gr( k , n)，是其点对应于 R n 的 k 维子空间的流形。我们将使用一个高 n×  k 的实矩阵 X 来表示 Gr( k , n )中的一个点，该矩阵的列是正交的。由 X 确定的 Gr( k , n )上的点是 X 的列空间，表示为 [ X ]。因此，如果 X 和 Y具有相同的列空间，则它们确定了 Gr( k , n ) 上的相同点 [ X ]  =[ Y]。为了在子空间上将优化问题推广得更灵活，我们使用不一定都在同一 Grassmannian 上的点进行工作。0尽管子空间是在同一环境空间中的，但它们是不同的。假设我们有一组 n 维空间的子空间，{[ X 1 ],[ X 2 ],...,[ X p ]}，其中 [ X i ]∈  Gr( k i , n )。我们希望找到一个 r 维子空间 [ Y � ]  ∈  Gr( r , n)，它在某种意义上是这些点的中心，即 [ Y � ] 是以下问题的解：0p0其中 d表示其参数之间的不相似度。子空间之间的主角度是一种常见的不相似度度量，它对正交变换是不变的 [ 4 , 9 ]。取 [ X ],[ Y ]  ∈Gr( k , n )。[ X ] 和 [ Y ] 之间的第 i 小主角度， θ i ([ X ],[ Y ])∈  [0, π /2]，被定义为解 ( 3 ) [ 4 ]。0满足  x T x  =  y T y  =  10现在让 θ ([ X ],[ Y ])  ∈  R k 成为向量，它表示 [ X ] 和 [ Y ]之间的主角度。Gr( k , n ) 上的测地距离是 ∥ θ ([ X ],[ Y ]) ∥ 2，弦距是 Gr( k , n ) 上的 ∥ sin( θ ([ X ],[ Y ])) ∥ 2  [ 7 ]。当 [ X ] ∈  Gr( k , n ) ，[ Y ]  ∈  Gr( r , n ) 且 k  �=  r时，我们可以通过将 θ ([ X ],[ Y ]) 的最后 max( k , r )  −  min( k, r ) 个条目设置为 0 来计算这些量。02.2. 测地距离原型0欧几里得平均值和几何中位数已经通过测地距离被转化为Grassmannian上的平均值。使用测地距离的Grassmannian上的平均值（解决(4)中的q=2）称为Karcher平均值，使用测地距离的几何中位数（解决(4)中的q=1）称为ℓ2-中位数。0arg min[Y]∈Gr(r,n)0i=1∥θ([Xi],[Y])∥q2. (4)0Karcher平均值和ℓ2-中位数只能在所有子空间的维度相等的情况下计算（例如，r=k1=k2∙∙∙=kp），[18]使用示例表明计算这些原型的可用算法很慢。Karcher[13]发现了找到Karcher平均值的解的最常见算法，Fletcher等人[11]表明我们可以使用Weiszfeld型算法找到ℓ2-中位数。[18]表明，Karcher平均值不仅计算速度慢，而且在他们的LBG聚类示例中产生的聚类纯度较低，因此我们选择不在我们的实验中使用Karcher平均值作为原型（第5节）。为了提供背景，Rn中的Weiszfeld算法0在算法1中给出。�−1;1.p103410算法1：Rn中的Weiszfeld算法0数据：{xi}pi=1�Rn0结果：几何中位数y∈Rn0while not conver0wi=p0�� pk=110∥xk−y∥20y ← �pi=1wi xi0end0请注意，Weiszfeld算法（算法1）的每次迭代都是加权向量wixi对最小二乘问题（1）的解（其中A=Rn，q=2）。权重wi来自于几何中位数y满足的事实（假设y�X）0y =0� p �0i=10xi0∥xi−y∥20��� p �0k=10∥xk−y∥20�0Fletcher等人通过将这种方法推广到Riemann流形来解决(4)中的q=1的问题。在第5节中，我们使用Fletcher等人的非加权Weiszfeld型算法和测地距离来计算Grassmannian上的ℓ2-中位数。设d为数据集中点之间的最大距离，δ为收敛参数。我们定义Nd,δ为我们实现的一次运行的迭代次数。我们在第5节中实现该算法的复杂度为O(npk^2Nd,δ)。02.3. 旗帜平均值原型0Draper等人[9]使用平方弦距离将旗帜平均值表示为不同维度子空间的平均值。旗帜平均值的优化问题为0arg min[Y]∈Gr(r,n)0i=1∥sin(θ([Xi],[Y]))∥22. (5)0这个标志不仅确定了Gr(r,n)上的一个点，还确定了各种旗帜流形上的一个点。旗帜流形是一个流形，其点表示子空间的旗帜[S1]�[S2]�∙∙∙�[Sr]=Rn。如果我们令si=dim([Si])，那么我们说旗帜的类型是s1,s2,...,sr。有关旗帜流形的更多细节，请参见[19]。在本文中，我们将旗帜平均值称为由旗帜确定的Gr(r,n)上的点。设[Y]为{[Xi]}ki=1的旗帜平均值。设yi为[Y]的正交矩阵表示中的第i列。那么第r个“真实”旗帜平均值是类型为{1,2,...,r,n}的旗帜流形上的点，其定义如式(6)所示。0¼ Y ¼ = span{y1} � span{y1, y2} � ∙∙∙ � span{y1, y2,..., yr} � Rn0(6)由flag确定的Gr(r, n)上的点是span{y1, y2,..., yr} �Rn。Draper等人[9]表明，我们可以通过利用矩阵[X1, X2,...,Xp]的奇异值分解（SVD）来计算flag均值。作为Gr(r,n)上的一个点，flag均值是对应于r个最大奇异值的r个左奇异向量的span。0这个算法的复杂度是O(n∑pi=1ki)2。Marks[17]在他的论文中建议计算加权flag均值。这个加权flag均值计算将被用作在第3.2节中引入的FlagIRLS算法的迭代。03. Flag中位数0将几何中位数用弦距离转化为Grassmannian，称为flag中位数。这个新型原型的优化问题在(7)中。0arg min [Y] ∈Gr(r, n)0i = 1 ∥ sinθ([Xi],[Y]) ∥2 (7)0我们将其称为flag中位数，因为使用FlagIRLS，[Y]实际上是一组子空间的flag，而不是n维空间中的单个r维子空间。这个flag中位数确实是一个中位数（类似于几何中位数），因为它最小化弦距离，而不是由flag均值解决的(5)中的平方弦距离问题。03.1. 推导0在本节中，我们展示了FlagIRLS算法可以用来近似flag中位数。本节中导出的算法围绕着{[Xi]}pi=1的加权flag均值展开。在本文的其余部分，我们将把子空间[Xi]的权重表示为wi。注意，(7)中的flag中位数优化问题涉及到向量的正弦主角的两个范数的和，而(5)中的flag均值优化问题涉及到相同向量的平方两范数。因此，换句话说，我们正在导出一种算法，类似于欧几里得设置中的Weiszfeld和IRLS，通过迭代地解决平方2-范数问题来近似解决2-范数问题。因此，FlagIRLS算法提供了一种“迭代加权最小二乘”方法来近似flag中位数。让我们从将(7)中的flag中位数问题转化为具有正交列的矩阵的优化问题开始。p�i=1pi1(9)p�i=1(11)(13)(14)103420YTXiXTiY是向量cos2(θ([Xi],[Y]))中的条目。利用迹的性质，我们可以证明tr(YTXiXTiY) = ¼ m i j = 1 cos2θj([Xi],[Y])[4]。这使得我们可以将(7)中的flag中位数问题重写为(8)中的矩阵优化问题，其中m i = min(r, ki)。0min Y ∈Rn×r0YT Y =I0¼ m i − tr(YTXiXTiY) ¼ (8)0我们使用Λ作为拉格朗日乘子的对称矩阵，其中(9)中的条目为λij，从而从这个问题中制定了一个拉格朗日函数。0L(Y, Λ) =0¼ m i − tr(YTXiXTiY) ¼0−�Λ, YTY − I�0然后我们计算(10)关于 Y 的拉格朗日函数，即 y j，并将其设为0。0yTj0¼ m i − tr(YTXiXTiY) ¼ XiXTiyj = 2λjj (10)0现在定义矩阵 X0X = ¼ w1X1, w2X2, ∙∙∙ , wpXp¼0其中 w i = ¼0m i − tr(YTXiXTiY)0¼ .0将(10)中的信息和(11)中的矩阵X结合起来，我们可以看出当[Y]是{[Xi]}pi=1的flag中位数时，Y必须是X的r个左奇异向量。现在让我们考虑一个迭代算法，其中0第j次迭代的形式为Yj+1 = Flag Mean��w(j)iXi�p0�0其中w(j)i = �0mi − tr(YTjXiXTiYj)0¼。该算法将是0在第3.2节中形式化。对于这种类型的算法，我们希望Yj+1是数据集{Xi}pi=1的旗标中位数的近似。我们将展示Yj+1的列应该选择为与r个最大奇异值相关联的X的左奇异向量，因此0使用旗标均值的更新为�w(j)iXi�p0i =0直接更新选择。设U�是由X的r个左奇异向量组成的矩阵。为了确定U�，其中0U� = argmin0p�0i = 10�q − tr(UTXiXTiU)�12。（12）0我们解决优化问题0maxU∈Rn×r0UTU = I0tr�UTXXTU�0这要求U�的列是与X的最大奇异值相关联的左奇异向量。因此，我们的更新为Yj+1 = U�。03.2. FlagIRLS算法0我们使用迭代重新加权最小二乘旗标均值算法结构来解决（7）。我们将子空间Xi的权重wi称为一个关注点。当权重的分母为零时，这些权重会引发问题。对于旗标中位数目标函数，当[Y]是[X]的子空间或反之亦然时，分母为零。为了避免奇异性，我们在分母上添加了一个小量ϵ。旗标中位数问题的wi在（14）中给出。0wi =010mi − tr(YTXiXTiY) + ϵ0¼0我们将这些权重与旗标均值一起使用，如算法2中所述的FlagIRLS算法。0算法2：FlagIRLS算法。请参见（14）以获取算法权重。我们假设U的列按照与X的最小奇异向量相关联的从左到右的顺序排序。0输入：一组正交子空间代表{Xi}pi=1，其中[Xi]∈Gr(ki,n)pi=10输出：一个正交子空间代表Y，用于旗标中位数[Y]∈Gr(r,n)，当未收敛时执行以下操作：0为每个wi分配值；X ←�w1X1|w2X2|∙∙∙|wpXp�；UΣVT = X%计算奇异值分解；Y ← U[:,1:r]%U的前r列；结束0重要的一点是FlagIRLS是一种迭代加权旗标均值算法，因此该算法的输出来自于X的左奇异向量。我们取与X的r个最大奇异值相关联的r个左奇异向量，即U的前r列。然而，U有n列，因此FlagIRLS实际上输出了一个子空间的旗标[U[:,1]]�[U[:,:2]]�∙∙∙�[U[:,:n]]。这个旗标用于在第5.2节中区分不同的原型与MNIST数字。04. 限制0计算旗标中位数的主要限制是FlagIRLS的速度。这要求我们在FlagIRLS的每次迭代中对X∈Rn×pk进行瘦奇异值分解。FlagIRLS算法的复杂度是103430即，O� nNδ��pi =1ki�2�，其中Nδ是迭代次数，δ是收敛参数。这项工作的另一个当前限制是对旗标中位数和FlagIRLS算法缺乏经过验证的数学保证。尽管对于我们所有的例子，FlagIRLS都收敛到旗标中位数问题的局部最小值，但我们还没有解决FlagIRLS收敛的条件的数学理论。我们还需要确定FlagIRLS的迭代是收缩映射的条件。在更大的尺度上，给定一个Rn子空间的数据集，我们还没有确定旗标中位数问题在哪些情况下是凸的。第3.1节表明FlagIRLS是一种寻找旗标中位数的逻辑算法，但是对数学理论的进一步发展将使我们对哪些数据集适合FlagIRLS、如何初始化FlagIRLS以及整体上为用户提供更好的收敛速度理解的直觉更加清晰。目前，FlagIRLS算法是通过多种不同的初始化来验证收敛性。05.实验0在本节中，我们使用合成数据、MNIST手写数字数据集[8]、Mind's Eye数据集[18]和UCFYouTube动作数据集[16]进行实验。目标是比较旗帜中位数与旗帜均值和ℓ2-中位数，并确定Fla-gIRLS的效率。在本节的所有实验中，我们使用FlagIRLS计算旗帜中位数，并使用[11]中的Weiszfeld类型算法计算ℓ2-中位数。我们的FlagIRLS实现的收敛准则如下。当FlagIRLS的连续迭代的目标函数值小于δ=10-11时，或者第i次迭代导致目标函数值增加时，我们终止算法。在前一种情况下，我们输出第(i-1)次迭代的结果。在所有示例中，我们使用ϵ=10-7运行FlagIRLS算法来计算权重。从[11]中计算ℓ2-中位数的Weiszfeld类型算法的收敛准则与FlagIRLS的收敛准则类似。当连续迭代的目标函数值小于δ=10-11时，我们终止算法。FlagIRLS和Weiszfeld类型算法在超过1000次迭代后终止。在我们的示例中，FlagIRLS从未超过1000次迭代。05.1.合成数据0我们首先对由来自Gr(3,20)和Gr(5,20)的10个点组成的数据集进行两个实验。从Gr(k,n)中抽样得到一个代表点的方法是在两个0步骤。第一步是从[−.5,.5)上的均匀分布U[−.5,.5)中抽样一个n×k矩阵。然后我们对该矩阵进行QR分解，得到Gr(k,n)上的一个点。我们对该数据集进行两个实验：第一个实验验证FlagIRLS的收敛性，第二个实验比较FlagIRLS与Grassmannian梯度下降的收敛速度。对于第一个实验，我们运行100次FlagIRLS的随机初始化试验。对于这些试验中的每一个，我们通过检查FlagIRLS算法输出附近的100个点来验证是否收敛。给定一个算法输出的Gr(3,20)中的点[X]，我们从U[−0.5,0.5)中抽样矩阵Y∈R20×3的条目，并检查矩阵X+0.00001Y的前3列的Q的目标函数值，其中Q来自矩阵X的QR分解。我们称这些点为算法输出的“测试点”。当所有测试点的目标函数值小于等于算法输出的目标函数值时，我们称FlagIRLS算法收敛。在这个实验中，我们发现100%的FlagIRLS试验收敛。现在我们展示一个相同数据集的例子，我们运行FlagIRLS和Grassmannian梯度下降算法，使用100个随机初始化来计算旗帜中位数。这个实验的结果如图1所示。对于这个例子，Grassmannian梯度下降的步长为0.01。我们发现FlagIRLS在旗帜中位数问题上的收敛所需的迭代次数少于Grassmannian梯度下降。0图1.在不同随机初始化的100次试验中的平均目标函数值。对于合成数据集的旗帜中位数问题，FlagIRLS收敛所需的迭代次数少于梯度下降。0对于我们的下一个例子，我们使用一个由200个Gr(6,100)上的点组成的数据集。首先确定数据集的“中心”点[X�]。我们通过取一个从U[−.5,.5)中抽样的100×6矩阵来实现这一点。然后将X�作为矩阵X的QR分解的前6列103440算法/初始化平均迭代次数0FlagIRLS/随机4.55±0.500Weiszfeld-Type/数据点795.50±227.400Weiszfeld-Type/随机968.80±94.490表1.FlagIRLS和Weiszfeld算法在一个由200个点组成的Gr(6,100)数据集上的20个随机初始化收敛的平均迭代次数。FlagIRLS的迭代次数远远少于Weiszfeld算法，并且迭代次数的标准差也要低得多。0这个随机矩阵的200个点是通过以下步骤计算得到的。对于每个点，我们通过从U[−.5,.5)中采样并将其缩放0.01的方式，生成一个随机的100×6矩阵Z。然后，我们通过从X�+Z的QR分解的前6列确定的点来计算FlagIRLS和Weiszfeld算法的20个随机初始化，分别计算旗帜中位数和ℓ2-中位数。对于随机初始化，我们将FlagIRLS和Weiszfeld算法初始化在同一点上。这个实验的结果在表1中。我们无论是否收敛，都在1000次迭代后终止Weiszfeld算法。所以，也许，即使在1000次迭代后，Weiszfeld的许多高迭代运行仍然没有收敛。现在，我们将使用一个由200个点组成的Gr(3,20)数据集。这些点由一个以子空间[X�]为中心的180个点的簇和20个异常点组成。180个点簇的点是通过以下过程采样得到的。我们通过从U[−.5,.5)中采样的方式，计算一个固定的“中心”点[X�]，并将其作为一个20×3矩阵。然后，我们通过以下步骤计算簇中的点。第一步是通过从U[−.5,.5)中采样并将其缩放0.01的方式，生成一个随机的20×3矩阵Z。第二步是将簇中的一个点作为X�+Z的QR分解的前3列确定的点。来自20个异常点集合的点是通过从U[−.5,.5)中采样的方式，计算一个随机的20×3矩阵，并将其QR分解的前3列确定的点。表2显示了计算该数据集的旗帜中位数、ℓ2-中位数和旗帜均值，然后计算[X�]与这三个不同原型之间的弦距离。请注意，旗帜中位数受异常点的影响最小，ℓ2-中位数受异常点的影响是旗帜中位数的两倍，旗帜均值受异常点的影响是ℓ2-中位数的十倍。注意：对于表2，FlagIRLS在一次迭代中收敛到旗帜中位数。0算法弦距离0旗帜中位数0.0017，ℓ2-中位数0.0022，旗帜均值0.01280表2. 算法结果与[X�]之间的弦距离。0在一次迭代中。05.2. MNIST手写数字数据集0MNIST数字数据集是一组28×28的单波段手写数字图像[8]。我们使用Gr(1,784)的一个元素来表示一个MNIST手写数字，方法是取一张图像，将其向量化，然后将得到的向量除以其范数。对于我们的第一个例子，我们看到MNIST训练的3层神经网络如何对旗帜中位数、ℓ2-中位数和旗帜均值原型进行分类。这个经过训练的神经网络分类器在MNIST测试数据集上有97%的测试准确率。我们通过从MNIST训练数据集中取20个数字1的例子和i个数字9的例子来生成这个实验的数据集。我们令i=0,1,2,3,...,19，这样就得到了20个数据集。对于每个数据集，我们计算旗帜中位数、ℓ2-中位数和旗帜均值，然后通过神经网络分类器预测每个原型的类别。在图2中，我们通过训练好的神经网络对每个数据集的每个原型的预测类别进行绘制。对于这个图，我们选择使用产生了最佳ℓ2-中位数预测的随机初始化。0图2.对于具有20个1的示例和i个9的示例的数据集，神经网络预测的原型类别，其中i = 0,1,2,...,19。0当添加了9个9的示例时，ℓ2-中位数和标志均值被错误分类，而标志中位数仍然被正确分类。103450对于i = 10和i =11添加的9个示例，正确分类为9。因此，在这个实验中，标志中位数是对异常值最稳健的原型。常见的误分类为8可能是因为1倾向于呈角度，因此当平均时，它们倾向于看起来像模糊的8，特别是当一些9被引入到数据集中时。此外，具有15到19个9位数字的20个1的ℓ2-中位数被错误分类为7。这很可能是由于不同角度的1和引入9的示例添加到数字7的顶部。现在我们使用多维缩放（MDS）[14]来可视化被异常值污染的MNIST数据集的原型的移动。对于这个实验，我们使用20个7的示例和i =0,2,4,6,8个6的示例。这导致从MNIST训练数据集中的示例形成的5个不同子空间数据集。然后我们计算标志中位数、ℓ2-中位数和标志均值。我们为所有6和7的示例以及每个数据集的样本生成一个距离矩阵，使用测地距离并通过MDS算法将距离矩阵传递以在二维中可视化这些子空间之间的关系。这个例子在图3中。请注意，随着我们添加6的示例，标志均值移动最多，ℓ2-中位数的移动方式与标志均值类似。标志中位数的移动要比其他原型小得多，因此它是最不受添加的6示例影响的原型。现在我们计算具有20个7和i = 8个6的数据集的r =5维标志中位数和标志均值。我们在图4中绘制了代表这些原型的矩阵的每个重塑的列。请注意，标志均值受6的示例影响比标志中位数更多。这在最后一列（维度5）中特别明显，在标志均值的图像中有一个清晰的6，而在标志中位数中6不清晰。05.3. Mind's Eye数据集0Mind'sEye数据集是一组灰度室外视频剪辑，其焦点是移动物体（主要是人）并且有一个减去的背景。每个视频剪辑由48帧组成，每个帧重新缩放为32×32像素的大小。我们使用Marrinan等人的k-means实验中的预处理数据[18]。这些数据和预处理的脚本可以在https://www.cs.colostate.edu/~vision/summet上访问。视频剪辑的77个标签表示视频中焦点对象的动作。通过将每个帧向量化并水平堆叠形成的1024×48矩阵的张量，将视频剪辑表示为Gr（48,1024）上的子空间。对于这个例子，我们使用表示具有弯曲、跟随、拾起、骑自行车和奔跑动作标签的剪辑的子空间（Gr（48,1024）中的点）。有27个示例。0图3.标志中位数、ℓ2-中位数和标志均值的MDS嵌入，点表示一维子空间。我们有20个7的示例和i个6的示例。每个三角形代表i =0,4,8的原型。最左边的三角形是没有6个示例的数据集的原型，最右边的三角形是具有8个6个示例的数据集的原型。下方的图像是上方图像中红色框内部的放大版本，以阐明示例之间的差异。0图4.矩阵的每一列代表具有20个7的示例和8个6的示例的数据集上的标志中位数和标志均值。0弯曲的32个，跟随的32个，拾起的27个，骑自行车的17个和奔跑的24个。我们使用Linde-Buzo-Grey（LBG）算法[15,20]对这些数据进行聚类，使用不同大小的码书（中心数）和使用标志中位数、ℓ2-中位数和标志均值进行原型计算。在LBG算法中，我们使用弦距离计算距离。对于每个103460中心数量，我们进行了10次不同的LBG初始化试验。结果如图5所示。我们注意到，对于8、12、16和20个聚类，旗帜中位数产生了最高的聚类纯度。在之前的所有实验中，我们发现旗帜中位数对异常值更具鲁棒性，这可能是旗帜中位数原型LBG实现成功的关键因素。我们还注意到，ℓ2-中位数和旗帜平均LBG实现对于每个码书大小具有类似的聚类纯度。同样，这与ℓ2-中位数和旗帜平均MNIST实验的类似行为一致（参见图2和图3）。0图5. Mind'sEye数据集上的LBG实现。对于码书大小为4、8、12、16和20，3种不同的LBG实现的结果。旗帜中位数在大小为4的码书上与ℓ2-中位数和旗帜平均相竞争，并在码书大小为8、12、16、20时优于ℓ2-中位数和旗帜平均。05.4. UCF YouTube数据集0我们的最终数据集是UCF YouTubeAction数据集的子集[16]。该数据集包含11个动作类别。对于每个类别，视频被分组为具有共同特征的组。对于这个实验，我们从每个动作类别中取一个示例。具体而言，我们的数据集包括23个篮球投篮示例，22个骑自行车示例，25个潜水示例，24个高尔夫挥杆示例，24个骑马示例，24个足球控球示例，23个荡秋千示例，24个网球挥拍示例，24个蹦床跳跃示例，22个排球扣球示例和24个遛狗示例。由于这些RGB视频非常大，我们将它们转换为灰度。然后，我们为每个视频生成一个矩阵，其列是每个帧的向量化。最后，我们对每个视频执行QR分解，并取Q的前10列作为其在Grassmannian上的代表。然后，我们使用48维旗帜平均和旗帜中位数运行子空间LBG。结果如图6所示。我们选择省略ℓ2-中位数LBG实现，因为Weiszfeld类型的算法只能计算一个010维原型。我们对以下码书大小的每个试验运行了10次LBG实现：4、8、12、16和20。我们发现，所有试验中，旗帜中位数LBG实现优于旗帜平均LBG实现。0图6.YouTube数据集上的LBG实现。对于码书大小为4、8、12、16和20，2种不同的LBG实现的结果。旗帜中位数在所有码书大小上优于旗帜平均。06. 结论0在本文中，我们提出了一种新的原型，即旗帜中位数，用于Grassmannian上的点簇。我们提出了FlagIRLS算法来近似解决旗帜中位数优化问题。我们进行了旗帜中位数、旗帜平均和ℓ2-中位数的实验比较。在我们的实验中，我们发现FlagIRLS通常比梯度下降更快地收敛。此外，我们发现旗帜中位数对异常值更具鲁棒性，并产生比旗帜平均和ℓ2-中位数算法更高的聚类纯度。旗帜中位数和FlagIRLS的未来工作可能涉及机器学习或向数学理论添加细节。对于机器学习，旗帜中位数可以用作子空间k-means算法、Grassmanniann-shot学习或任何其他计算“平均值”是一步的机器学习算法的步骤。这些类型的算法很可能对于图像和视频的分类非常有用。在数学方面，我们希望找到旗帜中位数问题是凸的定义域，并证明FlagIRLS的收敛速度是一个开放问题。这种优化问题与框架理论之间存在潜在的联系，因此在这个方向上的进一步研究可能会证明有用。最后，旗帜中位数可以推广到其他空间，如Stiefel流形。0致谢: 本工作部分得到国家科学基金会奖励NSF-ATD1830676的支持.103470参考文献0[1] Khurrum Aftab, Richard Hartley, 和 Jochen Trumpf.Lq优化的广义Weiszfeld算法.  IEEE模式分析与机器智能交易,37(4):728–745, 2014.  20[2] Daniel J Bates, Brent R Davis, Michael Kirby, Justin Marks, 和Chris Peterson.一组向量子空间的最长向量最佳拟合线及一组超椭球上的优化问题.数值线性代数与应用, 22(3):453–464, 2015.  20[3] J Ross Beveridge, Bruce A Draper, Jen-Mei Chang, MichaelKirby, Holger Kley, 和 Chris Peterson.主要角度将YDB和CMU-PIE中的主题照明空间分开.IEEE模式分析与机器智能交易, 31(2):351–363, 2008.  10[4] Ake Bjorck 和 Gene H Golub. 计算线性子空间之间角度的数值方法. 计算数学, 27(123):579–594, 1973.  2 ,  40[5] Sofya Chepushtanova 和 Michael Kirby.用于高光谱数据表示和分类的稀疏Grassmannian嵌入.IEEE地球科学和遥感快报, 14(3):434–438, 2017.  10[6] Anoop Cherian, Suvrit Sra, Stephen Gould, 和 Richard Hartley.用于活动识别的非线性时间子空间表示. 在IEEE CVPR会议论文集中,页2197–2206, 2018.  20[7] John H Conway, Ronald H Hardin, 和 Neil JA Sloane.线、平面等的装箱: Grassmannian空间中的装箱.  实验数学,5(2):139–159, 1996.  20[8] Li Deng. 用于机器学习研究的手写数字图像MNIST数据库.IEEE信号处理杂志, 29(6):141–142, 2012.  2 ,  5 ,  60[9] Bruce Draper, Michael Kirby, Justin Marks, Tim Marrinan, 和Chris Peterson. 有限维度子空间的标志表示.  线性代数及其应用,451:15–32, 2014.  1 ,  2 ,  30[10] Alan Edelman, Tomás A Arias, 和 Steven T Smith.具有正交性约束的算法的几何.  SIAM矩阵分析与应用杂志, 20(2):303–353, 1998.  20[11] P Thomas Fletcher, Suresh Venkatasubramanian, 和 SarangJoshi.在Riemannian流形上的几何中位数及其在鲁棒性图谱估计中的应用.神经影像, 45(1):S143–S152, 2009.  2 ,  50[12] Sadeep Jayasumana, Richard Hartley, Mathieu Salzmann,Hongdong Li, 和 Mehrtash Harandi.在高斯RBF核上的Riemannian流形上的核方法.  IEEE PAMI,37(12):2464–2477, 2015.  20[13] Hermann Karcher. Riemannian质心和平滑器平滑.纯粹与应用数学通讯, 30(5):509–541, 1977.  1 ,  20[14] Joseph B Kruskal. 多维缩放. 编号11. Sage, 1978.  70[15] Yoseph Linde, Andres Buzo, 和 Robert Gray.一种向量量化器设计算法.  通信学报, 28(1):84–95, 1980.  2 ,  70[16] Jingen Liu, Jiebo Luo, 和 Mubarak Shah.从“野外”视频中识别真实动作.在2009年IEEE计算机视觉与模式识别会议中, 页1996–2003. IEEE, 2009.2 ,  5 ,  80[17] Justin D Marks. 矩阵流形上的均值变体. 博士论文,科罗拉多州立大学, 2012.  2 ,  30[18] Tim Marrinan, J Ross Beveridge, Bruce Draper, Michael Kirby, 和Chris Peterson. 找到适合需求的子空间均值或中位