没有合适的资源?快使用搜索试试~ 我知道了~
9915F仿射子空间聚类是否需要仿射约束?1李春光2丹尼尔P。Robinson3Rene 'Vidal41EECS,加州大学伯克利分校,美国2北京邮电大学应用数学与统计学院,中国北京3美国约翰·霍普金斯大学应用数学与统计学院,美国4美国约翰·霍普金斯大学数据科学数学研究所,美国摘要子空间聚类方法基于将每个数据点表示为其他数据点的线性组合,在计算机视觉应用中取得了很大的成功,如运动分割,人脸和数字聚类。在人脸聚类中,子空间是线性的,可以直接使用子空间聚类方法。在运动分割中,子空间是仿射的,并且经常对系数执行附加的仿射约束。然而,由于仿射子空间总是可以嵌入到一个额外维度的线性子空间中,因此不清楚仿射约束是否真的必要。本文从理论上和经验上证明了当周围空间的维数相对于仿射子空间的维数之和很高时,仿射约束有一个严格的约束条件,即当周围空间的维数相对于仿射子空间的维数之和很高时,仿射约束有一个严格的约束条件。线性子空间的并集从未标记数据中学习线性子空间的这种并集的问题被称为子空间聚类[33],并且在计算机视觉[3,34,22],系统识别[1,30]和生物信息学[19]等近年来,基于数据的自我表达特性的子空间聚类方法[4]取得了巨大的成功。自我表达属性表明每个数据点都可以表示为数据集中其他一些点的线性组合。也就是说,对于每个j,xj=Xcj,或者等价地,X=XC,(1)其中X=[x1,···,xN]∈IRD×N是数据矩阵,C=[c1,···,cN]∈IRN×N是系数矩阵.满足(1)中的等式的矩阵C是通常不是唯一的,但总是存在解决方案,对集群性能的影响具体来说,我们的肛门-条目满足cij0,仅当xi和xj来自ysis提供了保证有和没有仿射约束的仿射子空间聚类方法的正确性的条件,并表明这些条件是相同的子空间这种表示被称为子空间保持[23,44,33]。子空间保持C产生亲和矩阵W=|C|+的|C|正确的连接,满足高维数据。 在我们的分析基础上-选项,即,wij0仅当xi和xj来自相同SIS是仿射独立子空间的概念,它不仅提供了几何上可解释的正确性条件,而且阐明了仿射子空间聚类的实验结果之间的关系。1. 介绍计算机视觉中现代数据的一个重要特征是高维性。例如,用百万像素相机拍摄的图像可以被视为数百万维空间中的数据点。尽管它们是高维的,但对应于同一组的数据,如受试者的面部图像,通常可以用几个生成因子来描述。这样的数据被认为具有比周围空间小得多的固有维度。当数据中存在几个这样的组时,每个组都位于近似线性的低维结构中,数据可以被建模为从亚空间谱聚类[35]然后可以应用于W对数据X进行聚类。为了寻找子空间保持解,许多文献提出了求解最优化问题最小f(C)S. t. X=XC,C∈N,(2)C其中f(·)是正则化子,且f∈RN×N. 现有的方法对均衡器f(·)有不同的选择。例如,稀疏子空间聚类(SSC)方法[4,5]使用f(C)=C1:=i、j|cij|寻求一个稀疏的,解C;低秩表示(LRR)[15,14]和低秩子空间聚类(LRSC)[6,31]方法使用f(C)=C来鼓励C为低秩;最小二乘回归(LSR)[18]和有效的稠密子空间聚类(EDSC)[8]方法使用f(C)= f(C)2,因为具有这种正则化的优化问题(2)具有封闭形式的解决方案。这些方法在许多实际应用中取得了优异的性能[5,42,991611,9,41,46,13,45],并有相应的理论,cal支持以证明其在子空间检测中的正确性[23,18,38,14,24,36,37,40,43,42,28,16,29,47]。特别地,已经证明了当子空间是独立的(定义1)并且f(·)满足关于k的强制块对角(EBD)条件(定义2)时,所有这些方法都产生子空间保持C[18]。仿射子空间聚类。尽管基于(2)的子空间聚类方法取得了巨大的成功,但是子空间是线性的假设通常过于限制,因为在许多应用中,子空间不通过原点,即,它们是仿射的。例如,在运动分割中,对应于相同刚性移动对象的特征点轨迹近似位于三维仿射子空间中[25]。适当地利用这种仿射结构有望提高聚类性能。实际上,[4,5,8]通过解决以下优化问题来代替(2)来解决运动分割问题:最小f(C)S. t. X=XC,1<$C=1<$,C ∈<$。(三)C这里,1是长度为N的向量,其条目都是1。附加的约束1C=1强加了自表达使用仿射组合而不是线性组合,这是从观察到仿射子空间中的每个点可以被表达为该仿射子空间中的其他点的仿射组合而激发的[4,5,8]中证明的基于(3)的方法的有效性需要解决以下理论问题:在仿射子空间上的什么条件保证(3)的解是子空间保持的?虽然这个问题在线性子空间的情况下得到了很多关注,其中人们分析了(2)的解,但仿射子空间的结果令人惊讶地稀少。例如,[27]提供了仿射子空间的代数子空间聚类(ASC)[32]的代数几何分析,但该分析没有扩展到基于(3)的方法然后,虽然[4]根据仿射子空间的齐次嵌入提供了SSC的条件,但该条件并没有提供关于原始子空间的几何的清晰见解。最后,虽然[12]提出了一个具有明确几何解释的SSC分析,但该分析仅限于SSC,并且不清楚它对于(3)中更一般的正则化子f(·)也是适用的是否需要仿射约束?很容易得出这样的结论,即人们应该总是使用(3)中的公式,而不是(2) 在处理仿射子空间方面。令人惊讶的是,现有文献[18,14,17,24,42]中的大多数论文这就需要解释为什么(2)中的公式可以很好地用于仿射子空间,以及(3)中的仿射约束是否真的需要。的前一个问题可以通过论证任何d维仿射子空间都可以被看作是包含该仿射子空间的d+ 1维线性子空间的子集来回答,这证明了线性子空间聚类方法应用然而,以下理论问题尚未得到回答:在仿射子空间上的什么条件保证(2)的解是子空间保持的?这个问题的答案可能有助于揭开(3)中仿射约束的神秘作用,并回答何时以及是否需要仿射子空间聚类的问题捐款. 在本文中,我们证明了,如果周围空间的维数足够高,则(2)和(3)都是有效的。(3) 保证在数据点从仿射子空间的并集中提取的模型下产生子空间保持解,仿射子空间是从周围空间随机生成的。这个结果证明了(2)和(3)的使用是正确的。(3)用于仿射子空间聚类。它还表明,在处理高维数据时,可能不需要(3)中的仿射约束,从而解释了(2)在现有文献中的流行为了验证高维性在得出这一结论中起着关键作用,我们对低维和高维环境空间的应用进行了实验,并表明(2)和(3)之间的性能差距在前一种情况下通常是突出的,而在后一种情况下通常可以忽略不计。我们的发现对于寻求为他们的问题选择合适的公式的从业者很重要。求解(3)中具有仿射约束的公式有时不如求解不具有仿射约束的公式容易。例如,虽然在[42]中已经开发了一种可以在没有仿射约束的情况下处理SSC的一百万个数据点的算法,但是它不能容易地适应于处理仿射约束。现有解算器只能处理10,000数据点[5,21]。此外,一些方法,如如SSC-OMP [43]和SSC0-SSC [40],根本不能显式处理仿射约束。对于这样的方法,我们的结果表明,可能根本不需要仿射约束,并且(2)中的更简单的模型可能同样好。我们的理论分析是基于一种新的方法来分析仿射子空间聚类问题,该方法利用了[12]中提出的仿射独立子空间的概念这一概念刻画了仿射子空间集合的排列,并具有明确的几何解释.我们的研究结果基于这一概念提供几何学的见解制度,仿射子空间聚类,ING是很容易的自我表达为基础的方法。此外,我们的分析建立了几个性质的仿射独立的子空间(例如,引理3和5),这使得有可能比较几个现有的条件[4,27,12]的仿射子空间聚类的正确性。9917j=1=1C=1=1=1=1=1=1CMΣj=12. 背景本节提供了我们对仿射子空间聚类的公式(2)和(3)的理论分析的背景,包括对线性子空间聚类的现有理论结果的回顾(第2.1节)以及仿射几何的基础知识(第2.2节)。• 仿射外壳(仿射跨度)。集合X ∈IRD的仿射壳/展,记为aff(X),是所有包含X的仿射子空间的交集。等价地,aff(X)是X中所有点的仿射组合的集合。• 仿射独立性一个点集{xj∈IRD}m是仿射独立的当且仅当j=1cjxj=0且2.1. 独立子空间聚类Σmj=1cj = 0表示cj=0对于所有j ∈ {1,···,m}。子空间模型• 仿射基 一组点{xj∈ IRD}m是仿射线性子空间聚类的一个众所周知的结果是,当子空间是独立的并且f(·)满足强制块对角(EBD)条件,如下定义。A的基当且仅当它是仿射独立的,仿射壳是A。•仿射维数。仿射子空间的维数A,表示为dim(A),被定义为其方向子空间,即,暗(A.)=dim(T(A))。3定义1(独立线性子空间[33])。 一个同事-称线性子空间{S<$N}n的独立性现在我们引入两个仿射子空间的仿射不交性的概念。如果变暗(跨度(范围)nS))=n=101 - 02-03-02S)。定义3(Affordable disjoint subspaces [12]). 两仿射定义2(EBD条件[18])。设N×N为零。一个函数f:R→ IR被称为满足EBD条件,如果• f在置换下是封闭的,f是置换不变的,即,对任意C∈P , 我 们 有 P<$CP∈P , 且 f ( C ) =f(P<$CP),对任意置换矩阵P,子空间A和A′称为仿射不相交当且仅当A <$A′={0}且T(A)<$T(A′)={0}。等价地,两个仿射子空间A和A′仿射不相交当且仅当dim( aff(A <$A′))= dim(A)+Σ• 对于任何分区C=14Σ3的任意矩阵C∈2dim(A′)+1 [12]. 例如,两个一维仿射IR3中的子空间是仿射不交的,当且仅当它们是偏斜(即,既不平行也不相交)。C1和C2是方阵C01∈F,f.ΣC好的ΣC1 3≥f10ΣΣ定义4(Affirmative独立子空间[12])。 一个山口-仿射子空间{A}n的选择称为仿射于-0 C2C4C20 C2ℓℓ=1Σn等式成立当且仅当C3=C4=0。dependent if dim(aff(nA))+ 1==1 dim(A)+n.更正式地说,子空间聚类对于仿射子空间{A }n的任意集合,在独立子空间模型下,1定理1([18]). 设X是数据矩阵,其列是从独立线性子空间的并集中抽取的联系我们.如果f满足EBD条件,则任何解在[12]中已经表明,Σndim( aff(nA))+ 1≤=1ℓℓ=1dim(A)+n.(四)(2)是子空间保持的。2.2. 仿射几何与仿射独立子空间在这里,我们回顾了仿射几何中的一些基本概念• 仿射子空间。一个非空集A ∈IRD是一个仿射子空间当且仅当每个点的仿射组合因此,集合{A<$}n是仿射独立的当且仅当仿射子空间处于某种排列中使得它们的并集的仿射包的维数最大化。亲和力不相交和亲和力独立的概念是密切相关的。具体来说,仿射子集合从A到A的谎言。等价地,仿射子空间是空格{A}n是独立的,当且仅当非空子集A=x0+S:={x0+x:x∈ S},其中S ∈IRD是线性子空间,x0∈IRD是点. 关联的子空间Sa n ysubse t sI′,I′′∈{1,···,n},其中I′∈I′′=A,证明了a f精细子空间a f f(Aκ∈I′Aκ)与a ff(Aκ∈I′ ′Aκ)是仿射不相交的.根据这个结果,如果集合其中A由T(A)表示,并称为子方向。{A}n是亲和力独立的,那么它们是成对的空间2[1]最近的一些工作[16,39]表明,该定理适用于更广泛的f范围。我们所有的结果也适用于所有这样的f2注意任何线性子空间也是仿射子空间。特别地,给定仿射子空间A,以下三个陈述是等价的:CC9918(i) A是线性子空间;(ii)0∈ A;(iii)T(A)=A.不相交的这种说法的反面是不正确的。3注意,如果dim(A)=m,则A的任何基都有m+1个元素。还要注意,仿射子空间的维数定义推广了线性子空间的维数定义。具体而言,任何线性子空间也可以被认为是仿射子空间,并且其作为仿射子空间的维数等于其作为线性子空间的维数。9919=1=1=1=1=1=1=1=1=1=1=1=13. 仿射独立子空间模型在本节中,我们建立几何条件,在此条件下,(2)和(3)中的最优化问题的解是子空间保持的。仿射子空间聚类问题的形式定义如下.定 义 5 ( 仿 射 子 空 间 聚 类 ) 。 给 定 一 个 数 据 集X=[x1,···,xN]∈IRD×N,其列位于维数为{d<$d ,则A 是概率为1的仿射(非线性) 子空间 ,这可 以从w0 ,独立 于子空间跨 度{w1,,···,wd,}的事实中看出。从命题1和命题2中可以看出,为了满足定理2和定理3中的几何条件,周围空间的压强需要足够大。下面的两个结果表明,在随机仿射子空间模型下,这样的条件不仅是必要的,而且是充分的。引理6. 如果D≥nd+n−1,则集合环境空间的维度是必要的,(3)和(2)的解一般是子空间保持的。对于真实数据,仿射子空间通常不满足随机仿射子空间模型,因此即使周围维数足够高,解也不一定是子空间保持的尽管如此,我们仍然观察到,对于高维数据,(3)和(2)之间的性能差异我们在下一节中提出这样的调查。5. 实验我们在人工数据集上进行实验,以验证我们的理论结果,并进一步理解仿射子空间聚类公式(3)和(2)的优越性。我们还在真实数据集上进行了实验,这些数据集包括低维和高维设置,以更好地理解它们的性能差异。公式(3)和(2)包括在现有文献中已经研究的广泛的方法。为了这项研究的目的,我们将注意力限制在SSC方法(即,f(·)=π·π1且π={C∈IRN×N:的仿射子空间{A∈RD}n,根据1 2=1定义6中随机仿射子空间模型是仿射的独立概率为1。引理7. 如果D≥nd+n,则根据定义6中的随机仿射子空间模型所画的仿射子空间的集合{AffIRD}n是仿射无关的,0∈/af f(na)概率为1。diag ( C ) =0} ) 和 LSR 方 法 ( 即 , f ( · )=2<$·<$F,N=IRN×N)。 F或两者同时存在时,函数f(·)满足EBD条件。为了区分(3)和(2),我们将对应于(3)的方法称为A-SSC,A-LSR,以及对应于(2)的方法为SSC和LSR。在我们对合成数据的实验中,我们使用CVX[7] 来解决与A相关的优化问题SSC和SSC,并使用由下式给出的封闭形式解:通过将引理6和引理7与定理2和定理3相结合,我们得到以下结果。X1⊤1 ⊤和XtX,分别用于A-LSR和LSR,定理4. 设{A}n是n个仿射子的集合,其中Xt表示X的伪逆。ℓℓ=1根据定义6中的随机仿射子空间模型绘制的维度为{d<$0,而不是(3),我们使用(i) 如果D≥n=1dn+n−1,则(3)的任何解都是minf(C)+λ<$X−XC <$2S. t. 1<$C=1<$,C∈<$,(8)概率为1的子空间保持。C2F}∪9924NN而不是(2)我们使用minf(C)+λ<$X−XC <$2S. t. C∈ C。(九)SSC A-SSC LSRA-LSR 100100C2F75 75对于A-SSC和SSC,我们遵循[5]并设置λ=α/μz,其中α是参数,μz在[5]中定义,并通过交替方向乘法器(ADMM)算法求解相关的优化问题。对于A-LSR和LSR,优化问题具有封闭形式502505 10 15 20 25(a) SPR与D502505 10 15 20 25(b) ACC与D可以在[18]中找到LSR的解决方案,并给出对于A-LSR,通过C=λWX<$X+(1<$v)−1vv<$,其中W=(λX<$X+I)−1,v=W·1。5.1. 合成数据我们通过根据定义6中的随机模型生成仿射子空间并在仿射子空间上随机采样数据点来验证定理4具体地说,我们首先从IRD中随机抽取n个维数为d的线性子空间。然后,从每个子空间的单位球面上独立均匀地随机抽取N/n个数据点。最后,我们在周围空间的单位球面上生成n个向量,并将它们中的每一个添加到相应子空间中的所有数据点这给出了N个点位于随机生成的仿射子空间的并集中。在实验中,我们固定d= 4、n= 5和N= 100,并在{5,6,···,30}中改变环境维度D。为了评估子空间保持的程度,性质,我们使用子空间保持率图2.合成数据性能评价。根据随机子空间模型生成5个4维仿射子空间,在每个仿射子空间上随机采样20环境尺寸D在x轴上变化。结果是20次独立试验的平均值。当周围空间的尺寸相对较低时,在提高性能方面起着重要作用另一方面,通过A-SSC和SSC实现子空间保持的D的范围扩展到比分别由定理4(i)和定理4(ii)预测的那些值小得多的值,这表明通过利用E1正则化子的特殊性质来导出这些方法的更紧的界限的可能性。4尽管如此,我们仍然观察到一种模式,A-SSC中的仿射约束在环境空间为低维时改善了SPR和ACC的性能5.2. 真实数据(SPR)定义为11= 0(Ni=1(wij·|cij|)/cj1),其中关于子空间聚类的文献通常报告wij∈{0,1}是取值为1的基础真值当xi和xj来自相同的子空间并且0个其他的子空间时,睿的 SPR取值范围为[0,1],SPR= 1当且仅当C是子空间保持的。另外我们也报告子空间聚类的聚类精度(A_CC)具有仿射约束的方法的聚类性能(例如,[5,8])或没有仿射约束(例如,[14,18,42,17,9]),从而使得不清楚仿射约束是否为了补充现有的研究,目的是了解仿射约束的影响ing,定义为max11{π(p)=p},其中我们在三个常用的数据集上进行实验。πNj=1jjp,p∈{1,···,n}N是地面真值,估计为-将X中的列分配给n个子空间,π是n个组的所有排列的集合。我们的实验结果报告在图2中。由图2(a)可知,当D满足定理4(i)和定理4(ii)的条件时,A-LSR和LSR产生子空间保持解,从而验证了这两个结果的正确性。此外,一旦违反定理4中的条件,解就不是子空间保持的。 的A-LSR和LSR迭代不能给出子空间保持解。霍普金斯155 [26]是一个运动分割数据库其由155个视频序列组成,每个视频序列具有2或3个刚体运动。我们报告的平均聚类精度超过35个序列,有3个运动。对于不同的序列,数据的环境维度范围从30到122,平均为57。MNIST [10]数据集包含70,000张手写数字图像。每个图像的大小为32×32。在[43]之后,我们使用散射变换网络[2]从每个图像中提取3,472维的特征,然后投影到500维通过PCA。我们在每次试验中随机选择1000张图片当你看到D时,
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功