离群鲁棒張量主成分分析的方法与性能保證

2263离群鲁棒张量PCA潘洲冯佳石新加坡国立大学新加坡pzhou@u.nus.eduelefjia@nus.edu.sg摘要低秩张量分析对于计算机视觉中的各种实际应用是重要的。然而，现有的方法集中于恢复被高斯或总稀疏噪声污染的低秩张量，因此不能有效地恢复低秩张量。离群破坏张量内低秩张量离群张量有效地处理实际张量数据中常见的离群值。为了解决这个问题，我们提出了一种同时进行低秩张量恢复和异常检测的异常鲁棒的十元主元分析（OR-TPCA）方法。对于具有任意离群点破坏的低秩张量观测，OR-TPCA是第一种在温和条件下具有可证明的性能保证的方法，能够准确地由于张量数据本身是高维和多向的，我们进一步开发了一种快速随机化算法，该算法需要较小的采样大小，但可以在不降低性能的情况下大大加速OR-TPCA。四项任务的实验结果：离群点检测、聚类、半监督和监督学习，清楚地证明了我们方法的优点。1. 介绍在这项工作中，我们考虑离群鲁棒张量主成分分析（OR-TPCA）如图1、假设我们有一个3-路张量数据X∈Rn1×n2×n3，它是干净的低秩张量L0和稀疏离群噪声E0的混合：X= L0+ E0。OR-TPCA旨在解决这样一个问题，即如何在存在离群值的情况下快速恢复低秩张量L0这个问题在许多实际应用中都很重要，例如图像/视频去噪和内绘[1，2]，数据挖掘[3]，协作滤波[4]，文本分析[5]等。一方面，最近的研究[6]表明，感兴趣的高维张量数据，如视频和图像集，通常本质上是低秩的或近似如此。因此，低秩张量数据分析的应用越来越广泛。另一方面，由于传感器故障、恶意篡改或其他原因，图1：这项工作解决的问题：隔离干净的低秩分量来自离群值的离群值损坏的张量。其他系统错误[7，8]。在这些情况下，大的误差仅集中在一些样本或数据的几个部分上。这两个因素共同导致了从离群值损坏中重新覆盖低秩张量数据但是，到目前为止，大多数低秩张量分析方法[2，9-OR-TPCA通过不仅考虑2路数据（矩阵）并提供更广泛的应用，大大推广了离群鲁棒矩阵PCA（OR-PCA）问题[7，14，15在这项工作中，我们在理论上和实践中开发了这个问题的第一个算法解决方案。我们直接对原始张量数据进行鲁棒低秩分析，提出了一种离群鲁棒张量主成分分析（OR-TPCA）方法（与问题同名），通过多项式时间凸优化恢复张量子空间并检测离群点。我们还为OR-TPCA提供了理论性能保证：在较温和的条件下，OR-TPCA可以恢复L0的列空间，并能准确地检测出离群点。此外，由于张量数据自然是多路和高维的，例如长视频序列和数百万图像集合，因此算法效率在实际应用中至关重要。因此，我们开发了一种快速的OR-TPCA算法。它首先对一小部分样本进行随机采样，并从采样数据中精确恢复底层子空间，该子空间也被整个数据共享。因此，恢复的低秩子空间是期望的，并且通过利用它，还可以有效地检测剩余数据中的离群值我们进一步证明了当随机采样数据的大小由一个远小于总数据数的正常数下界时，快速OR-TPCA2264n33精确地恢复张量列空间并检测异常值。事实上，这是第一个可以在线性时间内精确解决张量低秩恢复问题的算法（w.r.t. 数据大小）与理论保证。最近，基于t-SVD [16，17]和张量管秩[18]，Lu等人。 [2]将R-PCA [11]从2路矩阵扩展到3路张量数据，并考虑鲁棒张量PCA（R-TPCA）问题：最小值λ L =1+λE =1，s.t.X=L+E∈Rn1×n2×n3，L、 E其中，L和E1是张量核和1范数。然而，R-TPCA仍然假设噪声是表1：本文主要注释摘要。一一张量。矩阵。一一一个载体。标量。我AijkA（i，：，：）A（：，i，：）恒等张量。A的第（i，j，k）项。A的第i个水平切片A的第i个侧片。A*AǁAǁ1ǁAǁ∞A的共轭转置。A.A|阿i jk|.A|阿i jk|. A（：，j，：）|阿i jk|二、<$A2，1 =<$j<$A（：，j，：）<$F.A=.吉吉|阿i jk|二、A（：，：，i）A（i）第i个额叶切片为A.A（i）=A（：，：，i）.A（：，i，：）2004年2月，1A（i，j，：）A的第（i，j）个管.ǁAǁF等级（A）A矩阵A的秩。A=.2.IJǁAǁ∗A的奇异值之和。ΘPθPU（ A）E.在Θθ上的投影。PU（A）=U<$U<$A。PΘ在Θ上的投影。B（E） {E：E（：，i，：）=E（：，i，：） （iE（：，i，：）∈Θ）;E∈（：，i，：）=0（i/∈θ）}。稀疏且均匀分布在E0上。它不能有效地处理异常损坏。此外，我们专注于一个逆DFT以获得A=ifft（A<$，[]，3）. 我们的定义不同的问题，因而在理论分析和保障上存在重大差异OR-TPCA解决了一个问题，A<$∈Cn1n3×n2n3，（1）A¯（2）这就更难得到理论上的保证。事实上，在马里的存在下，确切的恢复是不可能的A<$=bdiag（A<$）=. ..A¯（n3）但是，腐败。 最好的办法就是-准确或近似地实现问题的某些结构[14，15]。此外，我们的方法在关键分析技术上有所不同，我们相信这将证明更广泛的适用性，从而引起普遍的兴趣。其中bdiag（·）将张量A<$展开为块对角矩阵A<$。进一步定义A的分块循环矩阵bcirc（A）∈Rn1n3×n2n3A（1）A（n3） ···A（2）A（2）A（1）···A（3）本文的贡献如下：bcirc（A）=0。.. . .. 。（一）1) 我们提出了一个新的离群鲁棒张量原理.A（n3）.A（n3−1）···.A（1）成分分析（OR-TPCA）方法秩张量分析OR-TPCA处理离群值和样本特定的损坏，这些损坏无法通过其他低秩张量分析方法。2) 我们证明了OR-TPCA成功的高概率，需要温和的条件，即使在具有挑战性的情况下，其中的秩L0和离群点的数量E0分别高达O（n/log（n））和O（n）。这里，n是异常值分布的维度。3) 所提出的快速OR-TPCA算法复杂度低，与时间成线性关系。数据大小，并已证明A<$和bcirc（A）的定义是张量秩和核范数的基础，这将在后面介绍。2.2. 预赛为了恢复低秩张量分量，我们首先介绍了两个广泛使用的张量秩定义，即张量平均值和管秩。定义2.1.（张量平均和管秩）[2，19]对于任意张量A∈Rn1×n2×n3，假设r=（rank（A<$（1））;· · ·;rank（A<$（n3）∈Rn3。A的张量a的平均秩秩a（A）定义为：rank （ A ） =1rank （ A<$ ） =1rank （ bcirc（A））。回收保证。an3我 不不i=12. 注释和预备2.1. 符号为了简洁起见，我们在表1中总结了主要的符号.张量A ∈ Cn1 × n2 × n3的共轭转置A∈Cn2×n1×n3是通过共轭转置每个正面切片，然后颠倒转置的正面切片322652到n3 的 顺 序 得 到 的. I∈Rn×n×n3表示第一个前切片为n×n单位矩阵，其它前切片均为零的单位张量.现在我们考虑张量上的离散傅立叶变换（DFT），它是张量相关定义的核心在SEC中。 2.2 设A<$∈Cn1×n2×n3表示A ∈ Rn1×n2×n3沿第3维的DFT. 我们可以通过Matlab命令A<$=ff t（A，[]，3）计算A <$，并使用张量管秩秩t（A）被定义为S的非零奇异管的数量，即，秩 t （ A ） =#{i ： S （ i ， i ， ： ） /= 0}=max（r1，···，rn3），其中S来自A = U <$S <$V <$的t-SVD（见下文）。由于最小化张量平均或管秩是NP-困难的，我们使用张量核范数来放松张量平均秩，如[2]所示。在此之前，我们首先介绍t-乘积定义，根据它我们可以计算3路张量之间的乘积。定义2.2.定义A ∈ Rn1×n2×n3与B ∈ Rn2×n4×n3之间的t-积为A ∈ B=fold（bcirc（A） ·unfold（B））∈Rn1×n4×n3 ， 其 中 unfold （ A ） =[A （ 1 ） ;A（2）;· · ·;A（n3）]∈Rn1 ×n3×n2，其逆算子fold定义为fold（unfold（A））=A.2266（二）n3k+1基于t积的定义，我们可以发展出以下必要的概念。一个张量P∈Rn×n×n3是orth o π，如果P ππP=PπPπ=I. 一个张量是f-dia矩阵，如果它的每个正面切片是一个对角矩阵。定义2.3.（T-SVD）[17]对于任意张量A ∈Rn1×n2×n3，它 可 以 被 T-SVD 分 解 为 A=U <$S <$V<$ ， 其 中U∈Rn1×n1×n3和V∈Rn2×n2×n3是正交的，S∈Rn1×n2×n3是f-对角的。现在我们可以给出张量核范数的定义，它是张量平均秩的凸包络。利用这个性质，我们用张量核范数来刻画张量的低秩结构。定义2.4. （张量核范数）[2]张量A∈ Rn1×n2×n3的张量核范数定义为A <$的所有f个切片的奇异值之和，即，A其中，·表示张量核范数。通过定义2.4，我们知道L的张量核范数等价于等式n中 块循 环 矩 阵 bcirc（ L ）的 核范 数 （ 因子 为 1/n3（一）.如[2]所指出的，与其他沿某维的矩阵化（如Tucker秩[20]）相比，循环矩阵化可以保留条目之间更多的空间关系，从而更好地描绘张量的低秩结构。我们还注意到，张量核范数也等价于L<$的所有正面切片的核范数之和，这是L沿3维的DFT因此，最小化L的张量核范数等价于恢复底层的低秩每个正面切片L<$（i）（i=1，· · ·，n3）的结构。这这意味着它恢复了傅立叶域中的数据子空间，即。e. ，所有正面切片L<$（i）的子空间，而噪声分布在原始空间中。 如果n3=1，第3章i=1第3章第3章然后，三向张量的t-乘积降为标准它是张量平均秩的凸包络在单位球中。其次，我们引入了与我们的理论结果相关的张量列空间。定义2.5. （张量列空间）对任意张量A∈Rn1×n2×n3，假设r=（rank（A<$（1））;· · ·;rank（A<$（n3）∈Rn3，r=maxr，且矩阵-矩阵乘积和张量核范数degen-生成矩阵核范数。OR-TPCA将减少到OR-PCA [7，14，15]。所以OR-PCA是我们的一个特例3.2. 优化我们使用ADMM [21]来解决问题（2），因为它在解决这个问题时的效率和收敛保证我的问题。算法1中总结了优化。A的t-SVD为A = U <$S<$V。那么它的列空间值域（A）由UA∈Rn1×r×n3所张成，其中第一扣除情况详见补充资料在每次迭代中，L和E每个ch切片U的r列（：，：，i）由第一个r组成k+1k+1有封闭形式解，我爱及其每次迭代的计算复杂度列U（：，：，i），其余列为0s。因为对于张量A，它的张量核范数等于A<$，最 小化A<$ ，意味着 重新覆盖每个正面切片A<$（ i）（i=1， · · ·，n3）的低秩子空间。因此，A的列空间是所有正面切片A<$（i） 的 列 空 间 的并集。3. 离群鲁棒张量PCA首 先 详 细 介 绍 了 异 常 鲁 棒 张 量 PCA （ OR-TPCA），然后对其进行了优化，最后从理论上分析了其设n=max（n，n）且n=是O.n（1）n2n3+n1n2n3log（n3）n. 请注意，COM-OR-TPCA 的 计 算 和 存 储 开 销 远 低 于 OR-PCA 和 R-PCA。这是因为这些方法的主要计算和内存开销都在SVD上，而OR-TPCA只需要 n1×n2矩阵的n3个SVD（横向切片L（i）），而OR-PCA和R-PCA需要计算整体的SVD数据矩阵更大，因此需要更多的计算资源和内存。注意，我们的优化方法可以并行实现，因为在每次迭代中，所有横向切片L<$（i）（i=1，· · ·，n3）（一）12（2）条k+1min（n1，n2），它将用于第二节。3.2、3.3和4.2。3.1. OR-TPCA的配方不失一般性，本文假设异常值沿张量X的第2维分布，即，E（：，i，：）表示可能的离群值。请注意，离群值也可以沿着其他维度分布，并且可以直接应用所开发的方法和分析在大多数情况下，与数据大小相比，离群值非常稀疏。因此，我们可以使用张量n2，1范数来刻画这种稀疏性。然后，OR-TPCA恢复低秩张量分量，通过最小值λL_（max）+λE_（max）2，1，s.t.X=L+E，（2）L、 EL可以被快速更新，这是主要的计算-当更新Lk +1时，也可以计算它的前切片Ek+1（：，i，：）（i=1，· · ·，n2） 但对于为了公平起见，我们在我们的实现中采用了串行更新方案，这也是非常快的（参见第2节。5.2.2）。3.3.精确的子空间恢复保证类似于低秩矩阵恢复[7，14，15]，在以下两种情况，将X精确分离为低秩项L0(1)真实的低秩项L0是稀疏的;（2）真实的稀疏离群值E0是低秩的。为了避免这些情况，我们需要两个2267√Θ（一）的t0√温和的条件（假设）。干净低秩数据上的张量列不相干条件：这个条件被广泛用于评估矩阵的稀疏性，我们在这里将其推广到张量。对于张量L ∈ Rn1×n2×n3，设秩t（L）=r，其skinny t-SVD为U <$S <$V<$. 对于U ∈Rn1×r×n3，V∈ Rn2×r×n3，则有UU = I和VV = I。算法1离群鲁棒张量PCA（OR-TPCA）输入：张量数据X ∈ Rn1×n2×n3。初始化：L0=E0=J0= 0，λ = 1/ log（n2），γ= 1. 1，β0=1e−5，βmax=1e+8，λ=1e−8，k=0。虽然不收敛，1. 修复Ek。更新Lk+1，L= argmin <$L+ βk<$X− L − E + Jk<$2。然后，具有参数μ1的张量列不相干条件被定义为：k+1L2. 固定Lk+1。更新E k+1，kβkFn2n32E= argminλ<$E+βk<$X−L−E+ Jk2。μ1≥Max（3）第一次见面。k+1E二，十二k+1βkFri=1，···，n23. J k+1 =Jk +βk（X-L k+1 -E k+1）。其中，具有第（i，1，1）个条目的大小为n2×1×n3等于1，其余的等于0。μ1度量张量距离列稀疏张量的距离，如果μ1很小，则张量L不是列稀疏的，因此避免了第一种情况。离群值的不明确性条件：为了区分低秩项与离群值，我们还要求离群值不在低秩干净数据的子空间中并且不是低秩[14，15]。为了避免这种情况，类似于矩阵OR-PCA [15]，我们在out上引入了一个无二义性条件，4. βk+1=min（γβk，βmax）。5. 检查收敛条件：<$E k+1−E k<$∞≤ε， <$Lk+1−Lk <$∞ ≤ε，<$X−Lk+1−E k+1<$∞≤ε。6. k=k+1。end while输出：Lk+1和E k+1。4. 快速OR-TPCA算法线E：B（E）≤对数（n2）/4。（四）如前所述，张量数据通常是大规模的，例如长视频序列和数百万图像集合，注意，许多噪声模型满足上述条件，包括i.i.d. 高斯噪声事实上，只要B（E）的非零侧切片的方向足够随机地散射，（4）就成立。无论存在多少离群点，（4）都可以保证离群点不是低秩的。主要结果：令Range（L0）表示L0. 现在我们给出定理1中的主要结果。定理1. 假设Range（L0）= Range（P（L0）），0E0/∈ Range （ L0 ）.则问题（2）的任何最优解（L0+ H，E0−H）（λ=1/log（n2））精确地恢复了L0的张量积列空间U0和E0的支撑集Θ0，其概率至少为1−c1n−10，其中c1是正常数，如果支撑集Θ0在所有的中心集之间均匀分布|Θ0|和因此，我们提出了一种快速OR-TPCA算法。它有下面给出两个步骤4.1. 快速OR-TPCA(1) 种子张量恢复：由于当数据规模非常大时，直接用整个数据求解OR-TPCA问题非常耗时，因此我们将整个感兴趣的张量分成两个较小尺寸的张量。一种称为“种子张量”，用于恢复整个张量的子空间。更具体地说，我们首先从X中随机采样一个子张量Xl∈Rn1×k×n3，其中k比n2小得多。 因此，X、L和E是分别划分为X=[X1，Xr]，L0=[L1，Lr]，E0=[E1，Er]。然后快速OR-TPCA首先通过求解rank（L）≤ρrn2μ1log（n（1））和|Θ0| ≤ρsn2，小规模OR-TPCA问题（2）.与n2相比，k非常小（见第二节）。 4.2）、恢复的计算其中ρr和ρs是两个常数，L0+Pθ0P U0（H）满足列不相干条件（3），E0−Pθ0 P U0（H）满足无歧义条件（4）。上述结果表明，在高概率的情况下，L1比回收整个L0要便宜得多。(2) 张量2，1过滤：由于X1是随机选择的，L1以高概率跨越与L0事实上，这是有保证的（见定理2）。因此，必须OR-TPCA能准确地恢复PL（0），即清洁0存在一个张量Q，使得L r= L lQ。X中的数据，以及E0的支持集Θ0。 但它确实这并不意味着OR-TPCA永远无法恢复损坏的样品 实际上，如果样本没有严重损坏，就有可能去除噪声，这在[15，22，23]和我们的实验中得到了证明（见图11）。4）.此外，定理1在第3维为1时也适用。因此[15]中OR-PCA的理论保证也是我们定理的一个特例。Θ22268i=1Σ由于异常值E是稀疏的，因此Er也是稀疏的，因此可以用范数E2，1来描述。所以我们可以通过求解最小吸收率2.1， s.t. X r= Ll Q + Er。（五）Er， Q由于DFT是沿着第三维进行的，因此横向切片彼此独立然后，通过定义<$Er<$2 ， 1=n2 <$Er（：，i，：）<$F，我们可以进一步22690√RRR˜˜˜rnoulli分布Ber（s/n2）构造X˜˜L000√′⊥r rLrs≥最大值cμrlog g（n˜˜算法2快速OR-TPCA表2：不同的随机问题的精确恢复输入：张量数据X∈Rn1×n2×n3和参数s/n2。1. 通过i.i.d.随机抽取X的每个侧面切片。是-尺寸.r= rankt（L0）= 0。15n，k = 0。4n，λ=1/log（n），Θ=Θ0。主要的侧切片用于构造Xr。2. 计算干净的数据Ll和异常值E1通过求解（L1，E1）= argmin<$L′<$L+λ<$E′<$2，1，s.t. Xl = L′+E′。L′， E′3. 利用问题（6）的封闭形式解计算Xr中的Lr和Er输出：L=[L1，Lr]和E=[E1，Er]。将问题（5）沿第二维划分为（n2-k）个子问题，第i个子问题写为表3：不同噪声幅度和不同类型噪声的随机问题的精确恢复。n= 80，r = rankt（L0）= 0. 15n，k = 0。4n，λ = 1/log（n），Θ′ = Θε。PU0−PU最小值Ei=F， s. t.Xi=L1<$Qi+Ei，（6）k∈ [0. 5s，2s]，概率至少为1-n-10，Ei，Qir rR2用Ber（s/n2）对X的每个侧切片进行采样。这么快其中Xi、Ei和Qi表示Xr（：，i，：）、Er（：，i，：）和Q（：r r 算法只需要一小部分样本和uti-，i，：）。 由于问题（6）是一个最小二乘问题，它允许封闭形式的解Ei=X i− P U（X i），L其中U L1是L1的张量列空间。我们可以进一步先对它们进行排序，准确地恢复出整个数据的低秩结构，然后对剩余的样本逐一进行恢复。这种机制使其能够应用于许多得到Li=PUL在算法2中。（X i）. 我们总结了快速算法任务，例如监督学习、视频摘要等。4.2. 快速OR-TPCA在这里，我们分析的准确恢复能力的算法2。对于随机选择的Xl∈Rn1×k×n3，当k的值有一个正的常数下界算法2中的步骤1保证Pθ（X1）恰好5. 实验5.1. 综合数据评价我们首先测试了OR-TPCA从合成数据中恢复低秩张量的性能，并验证了其性能与Theo-0以高概率跨越所需的列间距范围（L0）rem1 我们生成一个张量X = L0+E0 ∈Rn1×n2×n3，能力通过定理1，步骤2可以准确地恢复L1的真实低秩结构，并且以高概率检测离群点E1因此，剩余的正常样本可以由L1表示，而异常值不能表示。我们的主要结果在定理2中陈述。定理2. 假设X的每个横向切片由i.i.d. Bernoulli分布Ber（s/n2）构造X1，定理1中的所有假设对（L1，E1）都成立。 然后算法2以至少1-δ的概率精确地恢复L0的张量列空间和E 0的支撑集Θ0，条件是R2 1（1）1 δ其中c2是常数，r = rank t（L0），μ1表示方程n中的张量列不相干参数。 （三）、注意，如果（L0，E0）服从定理1中的假设，则对（L1，E1）也满足它们.因此，实际上这种快速算法并不需要比解决原始问题更严格的条件这种快速算法在处理大规模张量数据时也是非常有用的这是因为大规模数据的秩通常比大小小得多 因此，我们可以只设置s/n2非常小（例如， 6%），并且随机选择的Xl服从Eqn. （7）具有高概率，这在SEC中得到验证第5.2.3节。实际上，根据[23]中的伯努利试验性质，采样数k服从其中L0是低秩，E0包含稀疏离群值，如下所示。 我们 构 造 了一 个 秩 为 t-r 的 张 量 L0= A <$B ， 其 中A∈Rn1×r×n3和B∈ Rn2×n3的元素来自i.i.d. N（0，1）。 我们一致地选择E0的k个横向切片作为异常值，其条目服从i.i.d.。 N（0，1），E0的支撑集用Θ0表示。E 0中的其余条目为0s。为了简单起见，我们设置n1=n2=n3=n。为了验证OR-TPCA对各种张量大小、噪声大小和不同类型的噪声都能很好地执行，我们进行了两个不同的实验。(1)我们考虑维数随n=60，100，200，并以Ta为单位报告OR-TPCA的恢复误差。表2. (2)我们测试了E0的条目遵循i.i.d. N（0，0. 01），N（0，1），N（0，100），以及分布Bin（1，-1），其中i.i.d. 以概率0.5产生1或-1，并在表3中报告性能。 我们运行ev-每个实验20次，并报告平均结果。注意，L表示恢复的张量，并且非零E（：，i，：）的支持集Θ是恢复的离群值支持集。 根据表2，恢复的输卵管秩正好等于r，并且相对误差<$P U0−P U <$F/<$PU0<$F和<$PΘ<$（L0）−PΘ<$（L）<$F/<$PΘ <$（L0）<$F非常小，甚至小于10−10，其中P U= U <$U<$。Θ 0和Θ之间的汉明距离dist（Θ0，Θ）总是0。以上结果证明OR-TPCA能准确地恢复输卵管还有Ln R Krankt（L）PU0−PUPU0<$PΘ′（L0）−PΘ′（L<$）<$FPΘ′（L0）dist（Θ0，θ）609 2494.634e-155.518e-150100 15 40152.754e-153.322e-150200 30 80302.858e-152.870e-150异常值rankt（L）<$PΘ′（L0）−PΘ′（L<$）<$Fdist（Θ0，θ）中国共产党F0PΘ′（L0）N（0，0.01）125.007e-146.559e-140N（0，1）123.521e-153.753e-150N（0，100）122.306e-152.913e-1502270√ΘΘΘFF√ √√FF1 2210080(a) Mnist（b）FRDUE（c）Extended YaleB604020(d)AR（e）PIE（f）MIRFLICKR-25k数据库#类数量的每个 类总数大小差异MNIST10100100028× 28def.FRDUE153≈203059100× 90定义和位置YaleB38≈68241496× 84伊利诺伊州AR100262600165× 120III.，exp.和occ。馅饼68≈1701155496× 96III.，exp.和pos.(g)测试数据集的描述（“def."， 和分别是“变形”、“姿势”、“照明”、“表情”和“遮挡”的缩写图2：五个测试数据集和MIRFLICKR-25 k的示例和描述。表4：FRDUE上离群值检测和聚类结果（ACC、NMI和PUR）的AUC（20次随机运行的平均值）。00 50 100 150 200 250 300 350 400指数图3：OR-TPCA对FRDUE中前400个样本的离群值检测结果，其中有100个离群值。最好在彩色pdf文件查看。表5：Mnist上的聚类结果（ACC、NMI和PUR）和分段误差（ERR，%）（20次随机运行的平均值）。度量k-meansR-PCAOR-PCALRRSNNR-TPCAOR-TPCAACC0.4900.5120.5200.5380.5590.7810.826NMI0.4680.5000.4950.5130.5350.8030.880PUR0.5320.5630.5740.5680.5860.8230.865ERR0.5750.4910.4790.4610.4520.2580.1101/log（n2），其中数据矩阵大小为pro-R-PCA和OR-PCA的估计值为n′×n′，离群值为1 2列分布，而在R-TPCA和我们的OR-TPCA，数据大小为n1 ×n2×n3 和离群值是不一样的rank、列空间U0、干净数据P（L0）和上0异常值的端口集合Θ0。表3证明OR-TPCA是对各种噪声和相应的幅度非常鲁棒这些结果充分验证了定理1中的结论。5.2. 实际应用评价在这里，我们将我们的方法与其他最先进的低秩因子分解方法进行比较，包括R-PCA [11]，在第二维空间中的贡献。这些参数设置作者是作者[2，11，15]。我们手动调整LRR和SNN的参数。5.2.1离群点检测定理1意味着最优解E可以帮助检测数据中的潜在离群值：当数据P（X）是干净的时0非零E（：，i，：）的支持集Θ揭示了如在Sec.第5.1条但实际数据P（X）通常0噪声，导致更多的非零E（：，i，：）。AsE（：，i，：）2对应于异常值的比正常值大得多OR-PCA [15]，LRR（与二、一[12]第24话：我的世界我们可以使用k-means来聚类所有的koE（：，i，：）成两和R-TPCA [2]的四个张量分析任务，即离群点检测，聚类，半监督和监督分类。图2给出了五个测试数据库的简要介绍，包括一个手写数据集Mnist和四个人脸数据库，即埃塞克斯大学人脸识别数据1（FRDUE），扩展YaleB [25]，AR [26]和PIE [27]。在本文中，所有分类性能都是通过岭回归（RR）来评估的，其定义为：minY−WB2+νW2，（8）W其中B是通过这些比较方法恢复的数据。ods，Y是标签矩阵。 对于基于张量的方法（即，SNN，R-TPCA和OR-TPCA），我们对样本矩阵进行向量化以进行分类或聚类。对于我们的方法，我们不调整RR的参数，并设置ν=1节中第5.2.1和5.2.2节中，v=305.2.3虽然在其他比较方法中，它们的参数ν被调整为对于不同数据集上的不同任务是最佳的。为了公平起见，我们将R-PCA[11]、OR-PCA [15]、RT-PCA[2]和我们的OR-TPC A的正则化参数设置为1/max（n′，n′），1/log（n′），1/max（n1，n2）n3和1http://cswww.essex.ac.uk/mv/allfaces/类（离群值与非异常值）用于异常值检测。为了研究OR-TPCA在存在离群值的情况下的有效性，我们通过 将FRDUE与MIRFLICKR-25 k数据集（包含25，000张用于检索评价的图像）组合来构建数据集[28]。对于FRDUE，我们只使用前40个受试者，从而从低秩子空间中获得800个真实样本。然后，我们从MIRFLICKR-25 k中随机提取100和200张图像作为离群值。图2(f)显示了MIRFLICKR-25 k的一些示例。我们使用AUC来评估离群点检测的性能，离群点检测是基于E上的k-means检测结果计算的。我们采用以下 聚 类 度 量 来 衡 量 恢 复 子 空 间 的 质 量 ： 准 确 度（ACC）、归一化互信息（NMI）和纯度（PUR）。在实验中，我们首先移除由k-means检测到的异常值（也可能移除一些正常样本），并使用剩余的恢复数据（可能包括未检测到的异常值）进行聚类。然后，我们报告正常样本的聚类结果（被k-means检测为离群值的正常样本被赋予错误的标签）。表4总结了实验结果。我们的OR-TPCA实现了最好的离群点检测和聚类Ture离群值检出离群值检测到的正常噪声值纠正检测到的离群值错误检出离群值离群值数量度量k-means R-PCA OR-PCA LRRSNN R-TPCA OR-TPCAAUC-0.8650.9430.914 0.8690.8750.951100ACCNMI0.4070.6930.4360.7200.5200.7850.4920.7690.4910.7260.4990.7660.5640.818PUR0.4270.4820.5520.499 0.5220.5270.640AUC-0.8230.8860.892 0.8270.8350.934200ACCNMI0.3740.6500.4300.6940.4810.7500.4740.7160.4560.7240.4610.7280.5310.779PUR0.4050.4790.5180.523 0.4860.4920.5662271(a)原件（b）R-TPCA（c）OR-TPCA（d）原件（e）R-TPCA（f）OR-TPCA（g）原件（h）R-TPCA（i）OR-TPCA图4：扩展YaleB上的人脸图像去噪结果示例最好在彩色pdf文件查看。表6：在三个人脸测试数据库上半监督学习设置下的分类准确率（%）和平均运行时间（秒）。数字，例如1、2、3，表示每个人的训练次数。方法FRDUE扩展YaleBAR一二三时间3 6 9 12 15时间1 2 3 4 5时间RR87.4±1.0 92.2±0.7 93.9±0.556.6±1.8 74.2±1.4 81.5±1.4 86.0±0.9 88.3±1.0-39.6±1.9 64.8±1.377.5±1.284.9±0.887.8±0.5-R-PCA90.5±0.5 94.5±0.5 95.4±0.361.5±1.1 79.9±1.0 87.7±1.0 92.1±0.9 92.9±0.71.9943.8±1.2 73.0±1.084.5±0.889.8±0.692.4±0.56.23OR-PCA90.6±0.7 95.0±0.5 96.0±0.461.8±1.3 80.5±1.1 88.3±0.8 92.9±0.7 93.4±0.51.2643.1±1.1 74.1±0.984.9±0.889.3±0.693.2±0.64.61LRR90.3±0.6 95.1±0.4 96.6±0.458.9±1.5 72.9±1.3 79.3±1.0 86.0±0.8 88.3±0.72.0445.1±1.6 68.1±0.9 77.6±0.7 86.0± 0.6 89.4± 0.6 6.41SNN92.2±0.7 95.9±0.5 96.9±0.463.1±1.2 81.7±0.9 89.8±0.5 93.6±0.3 94.1±0.32.6745.7±1.2 75.3±1.086.6±0.791.1±0.594.1±0.46.89R-TPCA95.6±0.5 97.9±0.4 98.7±0.40.7665.1±1.1 84.5±0.8 92.0±0.7 95.7±0.5 97.3±0.50.3849.3±1.2 78.9±0.889.7±0.793.6±0.696.0±0.61.43OR-TPCA97.3±0.698.6± 0.499.2± 0.20.6971.4±1.190.3± 0.995.9± 0.698.2± 0.498.6± 0.30.2456.8±0.887.2± 0.795.0± 0.698.1± 0.499.0±0.21.03性能，因为（1）它利用了张量多维结构;（2）它使用了比1，2，1范数更好地描述离群值的1，2，1范数。图3显示了OR-TPCA检测到的一些离群值我们还观察到离群点检测可以提高聚类结果。这些方法首先从检测离群值中受益，并实现比vanilla k-means更好的聚类结果。5.2.2无监督和半监督学习如前所述，低秩子空间方法已被应用于图像去噪和对齐。在这个实验中，我们还应用OR-TPCA通过恢复它们的子空间来去除人脸和手写数字上的噪声和破坏，考虑到真实的手写和人脸图像近似地位于低秩子空间的并集上[2，11，24，29- 35 ]。同时，对图1所示人脸图像中的阴影、表情和遮挡进行了分析 2更像是连续的噪声，因此与传统的1，2，1范数相比，1，2，1范数可以更好地表征它们。由于张量核范数是依赖于方向的，我们发现沿着第三方向组织图像方向形成w×h×n张量提供了稍微好一点的结果。R-TPCA在处理时也表现得更好，张量就是这样构造的。此外，这种构造方式导致更高的计算效率，因为样本数n通常远大于其维数w和h。否则，我们必须计算大小为n×h或w×n的w或h矩阵的分解。我们在一个手写数字数据库Mnist和三个人脸数据集FRDUE，ExtendedYaleB和AR上评估了OR-TPCA。我们使用ACC、NMI、PUR和分割误差（ERR）来评价Mnist上的聚类结果;采用分类准确度作为三个人脸数据集的性能指标。我们还报告了平均算法运行时间（总去噪时间除以样本数）。我们运行每个分类实验表7：快速OR-TPCA关于PIE（TSP数量6101418222630PUi−PU5.1e-01 2.7e-15 2.7e-15 2.7e-15 2.7e-15 2.8e-15 2.7e-15使用特定的训练大小超过10个恢复数据的随机训练/测试分割，并报告平均结果。表5总结了Mnist上的聚类结果或者- TPCA在所有四个指标上的表现都优于基线提高了13。8%，比第二好的R-TPCA的错误率。表6显示了三个人脸数据集的分类精度。所有方法都在FRDUE上取得了令人印象深刻的良好分类结果，部分原因是它比扩展的YaleB和AR更容易（见图1）。2）的情况。虽然扩展的YaleB和AR更具挑战性，但OR-TPCA在所有领域的表现仍然优于其他方法设置，特别是对于训练样本不足的情况（例如，扩展YaleB和AR上每人分别≤6和3个训练样本）。这清楚地证明了OR-TPCA的优越鲁棒性。此外，结果表明基于张量的方法，即。SNN、R-TPCA和OR-TPCA，实现更高的分类精度，因为它们利用了张量的多维结构，而不是像基于基线的矩阵那样直接矢量化样本我们还观察到，基于OR2，1的方法，即OR-TPCA和OR-PCA，通常优于它们的OR 2，1对应部分，即。R-TPCA和R-PCA。这是因为N2，1范数可以更好地检测相邻噪声。这一点得到了图1所示结果的证实4，其中OR-TPCA去阴影和恢复面部比R-TPCA好得多我们还观察到OR-TPCA比其他算法快得多：R-PCA，OR-PCA和LRR需要在非常大的数据矩阵上执行SVD，SNN分解三个大矩阵（沿三个模式展开张量相反，OR-TPCA需要对n个矩阵进行SVD，但每个矩阵都比基线中涉及的矩阵小得多2272总运行时间（秒）˜˜˜˜表8：PIE上半监督学习设置下的分类准确率（%）和总运行时间（小时）。（快速OR−TPCA快速R−TPCA快速OR−PCA快速R−PCARR95 5000904000858030007520007010006560 05 10 15 20 2530每个人的训练样本5 10 15 20 25 30每个人的训练样本5.2.3快速OR-TPCA的实验研究在这里，我们评估了我们的快速OR-TPCA在PIE上的性能，PIE是一个大规模的人脸数据集，每个实验运行10次，以获得平均性能。我们首先检查给定一小部分数据，快速OR-