RES-PCA：一种恢复低秩矩阵的线性有效的、可扩展的RPCA方法

1E∈Rǁ ǁL、S≥ ǁ· ǁ×RES-PCA：一种恢复低秩矩阵青岛大学2电子科技大学计算机科学与工程学院3肯塔基大学计算机科学系{pchong1991，cclz123}@ 163.com，zkang@uestc.edu.cn，lijianbo@188.com，qiang. uky.edu摘要鲁棒主元分析（RPCA）由于其在低秩矩阵发现方面的强大能力以及在实际问题中的成功应用而受到广泛关注。现有算法通常需要求解大型矩阵的奇异值分解，其复杂度一般至少为二次甚至三次。这一缺陷限制了RPCA在实际问题中的应用。为了克服这个缺点，在本文中，我们提出了一种新的类型的RPCA方法，RES-PCA，这是线性有效的，可扩展的数据大小和维度。为了比较的目的，AltProj，现有的RPCA的可扩展方法需要真实秩的精确知识;否则，可能无法恢复低秩矩阵。 通过对比，我们的方法在知道或不知道真实秩的情况下都有效;即使两种方法都有效，我们的方法更快。大量的实验已经进行，并证明了所提出的方法的有效性定量和视觉质量，这表明我们的方法是适合作为一个轻量级的，可扩展的组件RPCA在任何应用程序的管道。1. 介绍主成分分析（PCA）是无监督学习中应用最广泛的技术之一经典的主成分分析的目的是寻求一个低秩的近似给定的数据矩阵。在数学上，它使用了N2范数来拟合重建误差，这是已知的对噪声和异常值敏感。更难的问题是寻找一个有效的主成分分析异常破坏的数据被称为鲁棒主成分分析（RPCA）。对于术语“异常值”[ 24 ]，没有数学上的精确含义因此，已经尝试了多种方法来定义或量化该术语，例如交替最小化[14]、随机采样技术[9，17]、多变量[11][12][13][14][15][16][17][18][19在这些方法中，最近出现的一种方法将离群值视为添加剂稀疏腐败[25]，这导致将数据分解为低秩和稀疏部分。给定数据矩阵Xd×n，基于这种分解假设，相应的RPCA方法旨在数学上解决以下问题[6，25]：minrank（L）+λ S0， s.t. X=L + S，（1）L、S其中λ0是一个平衡参数，0是计算矩阵非零元素数量的0（伪）范数。求解秩函数和基于范数的优化问题通常是NP难的因此，在实践中，（1）经常被放宽到下面的凸问题[6]：最小L/L/L+ λ/S/L，s. t.X=L +S，（2）其中，α·α是输入矩阵的所有奇异值的核范数，α·α1=Ij|SIj|是矩阵的范数。 许多算法已经被开发用于求解（2）的方法，如奇异值阈值（SVT）[5]、加速近端梯度（APG）[23]和不精确的拉格朗日乘子（IALM）[16]。然而，这些算法需要在每次迭代时计算大小为d n的矩阵的SVD，已知其通常至少具有二次或甚至三次复杂度[12]。因此，由于SVD的使用，这些算法的高复杂度使得它们不太适用于大规模数 据 。 为 了 提 高 效 率 ， 基 于 增 广 拉 格 朗 日 乘 子（ALM）的算法采用PROPACK包[10]来求解部分而不是全部SVD。即使使用部分SVD，当d和n都很大时，计算成本仍然很高。（2）中的凸RPCA具有两个已知的限制：如果没有底层矩阵的不一致性保证，或者当数据严重损坏时，结果可能会大大偏离真理[6]; 2）当矩阵具有大奇异值时，其核范数可能导致远离秩的估计[13]。为了克服这些缺点，73177318×L、S∈{···}2L、Sǁ· ǁIJγ我 γ+σi（L）我已经有几种更好的秩近似方法，Σ其中，1=. ΣS2是以下项的102个范数之和：提出了 例如，L的秩是固定的，并用作一个硬约束在[15]中，和一个非凸秩逼近采用更精确地近似秩函数在[13]中。然而，这些非凸的方法也需要解决完整的SVD的d n矩阵。[15，19]中的两种方法只需要求解部分SVD，与完全SVD相比，这显著降低了复杂度;例如，AltProj的复杂度为O（r2dn）[19]，其中r是L的地面真值秩。然而，如果r不是先验已知的，[19]通常无法恢复L。随着大规模数据越来越普遍，使用更高效和可扩展的RPCA柱子。（2）和（3）之间的区别在于后者包含稀疏分量的空间连接指出核范数在逼近秩函数时可能是不精确的[22]。为了克服这一缺陷，人们用一些新的秩近似代替了（2）和（3）中的核范数，如γ-范数[13]。基于γ范数的RPCA解决了以下优化问题：最小值λLλγ+ λSλ2，1，s.t.X=L +S，（4）然而，这些方法在很大程度上仍然缺失。到面对这样的挑战和挑战，在这篇文章中，我们将...（1+γ）σi（L）其中，σ（L）是i-提出了一种新的RPCA方法，称为RES-PCA。该模型不依赖于秩近似来恢复低秩分量;相反，它有效地利用了低秩分量的潜在的组结构信息用于恢复。因此，新方法不需要像当前现有技术的方法通常那样求解任何SVD，这避免了任何二次或更高的复杂性;更具体地，所提出的方法在n和p两者中具有线性复杂性，使得其轻量、可缩放，并且因此适合于大规模数据应用。我们总结本文的贡献如下：我们提出了一种新型的RPCA模型，利用低秩分量的潜在群结构。我们开发了一个基于ALM的优化算法，它不使用矩阵分解，并在每次迭代线性有效的计算。该方法在数据维数和样本量上具有可伸缩性，适用于大规模数据。大量的实验表明，所提出的方法的有效性定量和定性。本文的其余部分组织如下。我们首先简要回顾一些相关的工作。然后介绍了新方法及其优化。接下来，我们进行实验来评估新方法。最后，对全文进行了总结最大奇异值L 在这里，不同的价值观对于λ，γ-范数在近似秩函数时可能具有不同的性能。RPCA的另一种最近的非凸方法AltProj融合了PCA的简单性和凸RPCA的优雅理论 [19]。它交替地将拟合残差投影到低秩和稀疏集合上。假定L的期望秩为r，AltProj计算每个矩阵中的秩-k投影的总r级，其中k为1，2，.，r。 在此过程中，具有大的拟合误差的矩阵元素被丢弃，使得稀疏误差被抑制。 该方法具有几个很好的性质;然而，它需要L的真实秩的精确知识，这并不总是可用的。如果没有这样的知识，AltProj可能无法恢复低秩分量。3.一种新的鲁棒PCA方法经典的RPCA及其变体通常需要求解SVD，具有较高的复杂度。为了克服这个缺点，在本文中，我们考虑了一种新的类型的RPCA模型，具有线性复杂度。受凸 RPCA 方 法 的 启 发 ， 我 们 假 设 数 据 可 以 分 解 为X=L+S。这里，L是X的低秩分量，其列在线性代数中线性相关;因此，L许多列共享高相似性且因此在欧几里德空间中几何上接近是真实的。在单个秩-1子空间的情况下，上述假设自然导致L的列向量的相互距离平方和或等效方差（按n缩放）的最小化：2. 相关工作（2）中的凸RPCA考虑了Σn最小λL、SΣnLi− LjX = L + S，（5）以元素方式的稀疏分量[5]。为了充分利用示例稀疏性，通过替换（2）[18，26]中的101范数，采用了102，1范数最小值：L=2.00+ λ=2.00，s.t.X=L + S，（3）i=1j=1其中λ ≥ 0是一个平衡参数，Li是L的第i列，2是向量的范数。应注意，尽管不是必需的，但是将最小化的（5）中的第一项导致L的低秩结构。看到···J我7319n2n···−nnn不2i=1我nj=1J 2ǁ −ǁ2因此，我们将其重新表示为2nλ<$nL1<$n L2，即从每个数据点到所有数据点平均值的残差平方和（SSR）。因此，通过最小化它，所有列都接近其平均值，并且平均值erage是SSR的最小化器，理想情况下导致rank-14. 优化在本节中，我们提出了一种有效的基于ALM的算法来求解（8）。首先，我们定义（8）的增广拉格朗日函数解决L。在一些温和的条件下，我们有下面的定理。定理3.1. 给定一个矩阵L=[l1，· · ·，ln]，其中li∈p2ΣcL=λi=1.TrLd（pi）.In−1n1T2002年ΣΣd（pi）LTR，并且ni=si，i=1，···，n，我们有秩（L）=ρ12（九）21是充分的和必要的，+S1+2X-L-S+ρθFΣL= argminTr（Q（IQ∈Rp×n111吨n）QT），（6）S.T.pi∈ {0，1}n，pi= 1n.我S.T.i=1，···，n，（7）然后，我们采用交替体面的方法进行优化，在每一步中，我们优化一个子问题，其中Q=[q1，，qn]，1是n维全1向量.值得注意的是，第一项中的双重求和（5）可以写为Tr（L（In111T）LT），通过最小化，我们可以获得期望的低秩结构。把上述想法概括起来是很自然的为此，我们将-保持一个变量不变，而其他变量不变。每个变量的详细优化策略描述如下。4.1. L极小化L-subproblem是为了解决以下问题：考虑多个秩1子空间的情况，使用以下模型，我们将其称为鲁棒、线性有效、可伸缩PCA（RES-PCA）：最小λLΣci=1.TrLd（pi）.In−12002年1n1TΣΣd（pi）LT（十）Σ c.1ΣΣn+ρX−L−S+Θ/ρ2最小λL，S，{p1，···，pc}Tri=1Ld（pi）In− 2002年1n1T d（pi）LT2F公司简介S.T. X=L + S， piΣ∈{0，1}，pi我=1n，忽略因子λ，可以看出，上面的第一项可以导出为：（八）其中In是一个n×n的单位矩阵，1n是一个包含1的n维列向量Σci=1.TrLd（pi）.In−12002年1n1TΣΣd（pi）LT从输入向量返回对角矩阵的生成器Σ c.1ΣΣ和p是一个二进制向量，1的位置表示=TrPi（L）我在这里I21吨P（L），我n个列向量中的哪一个属于第i个子空间。i=12002年i2pi2i（十一）很明显，通过自动学习pi，以获得关于低秩子空间的结构信息值得注意的是，S可以使用不同的范数，例如101和1021范数;本文在不损失一般性的情况下，采用101范数来捕获稀疏结构其中，运算符Pi（L）返回L的子矩阵，该子矩阵包含对应于Pi的非零的L的列。相应地，可以直接看到（10）的第二项可以以类似的方式分解：色葡萄 在下一节中，我们将开发一个有效的算法ρ2优化（8）。在数据具有非线性关系的情况下，即，Li和Lj在流形上而不是在2<$X−L−S+Θ/ρ<$Fρρc=<$Pi（X − S + Θ/ρ）−Pi（L）<$F。（十二）如果它们来自同一个子空间，我们的方法可以直接推广，这在4.2节中给出。由于线性模型为我们提供了本文的−173201张图片1张图片不Pi（L）我主要思想和贡献，i=1因此，对于i=1，···，c，可以通过单独求解以下子问题来求解L：实验已经证实了它的有效性在几个现实世界的应用，我们专注于线性模型在我们的pa。.最小λTr Pi（L）.1Ipi2−p不i2pi2ΣΣPi（L）per. 由于篇幅所限，我们不全面展开非线性-+ρ<$P（X−S+Θ/ρ）− P（L）<$2耳模型，并将考虑在进一步的研究和更多的2i应用.IF（十三）27321nnn22I j我 1个月1.22λ+ρI2nI2pi−1I21上面的子问题是凸的，并且根据可以看出，一阶最优性条件2λPi（L）Mi+ρPi（L）−ρPi（D）=0，（14）其中，为了便于表示，我们表示D=X-S+Θ/ρ，1Σci=1Σc.TrLd（pi）. ..In−12002年11n1TΣΣd（pi）LTΣ ΣMi=Ipi2--2002年不2002年.因此，（14）导致=TrLd（pi）−2002年d（pi）1n1Td（pi）LTP_i（L）的解：Pi（L）=ρ（2λMi+ ρI <$pi<$2）Pi（D）.（十五）i=1Σc=.Σ不L d（pi）−d（pi）1n1d（pi）可以看出，（15）需要矩阵求逆，不幸的是，一般具有O（n3）的时间复杂度。为了避免矩阵求逆，我们重写这个矩阵以简化i=1Σc=2002年Σ1 Lj−Σ Lj202，（二十）（十五）：i=1（pi）j=1pi2λ2λMi+ρI<$pi<$2=（2λ+ρ）I<$pi<$2−<$p<$不i2pi2其中（pi）j表示p i的第j个元素。因此，pi-子问题可以转化为（十六）值得注意的是，由于（16）的特殊结构，其逆-ΣcminpiΣLj−12002年ΣLJ2002通过使用谢尔曼方程，莫里森-伍德伯里公式：i=1（pi）j=1S.T.pi∈ {0，1}n，（pi）j=1Σ pi=1n，（二十一）.（2λ+ρ）Ip+（−2λ1张图片1−1iI21=2λ+ρI<$pi<$2ni22002年这就是标准的K均值问题 这是令人惊讶的，因为我们只需要对L执行K-均值，然后最优[p1 ， ···，pc]∈{0，1}n×c简单地corr-1I<$p<$（−2λ1<$p<$）1T1Ip（十七）对群体指标矩阵作出反应：-1+ 1T1Ip（−2λ1p）[p1，···，pc]←K-means（L，c）.（二十二）pi<$22λ+ρi2ni21 2λ=I+1 1应当注意，利用其当前形式，（21）被求解2λ+ρ2002年pi<$2ρ（2λ+ρ）2002年2002年[20]第20话 然而，更一般的聚类方法-因此，很明显，（15）可以写成如下：.ρODS也可以适用，如果我们考虑解决pi作为一个而不是优化问题。例如，如果我们考虑非线性聚类算法，如spec-Pi（L）=2λ+ρIpi22λ+1pi2002年不2002年ΣPi（D）（十八）在聚类分析中，恢复的L和p实际上反映了数据的非线性结构，这可以被视为我们的方法的直接非线性扩展，以说明数据的非线性关系。ρ112不不73222n=2λ+ρPi（D）2λT4.3. S极小化S-子问题是+p（2λ+p）（1 pi2（1pi2Pi（D），1 1i2分钟S1+X-L-S+Θ/ρ其通过利用矩阵-向量乘法在n和d两者中具有线性复杂度L可以根据-Sρ2F它使用软阈值算子[3，8]求解当i=1，2，···，c.4.2. pi最小化Sij =（|Bij| −1/ρ)+ 符号（Bij），（二十四）与pi-最小化相关的子问题如下：其中B = X-L + Θ/ρ。4.4. Θ，ρ更新minpiΣci=1.TrLd（pi）.In−Σ12002年1n1TΣΣd（pi）LT（十九）对于Θ和ρ的更新，我们遵循ALM框架中的标准方法：S.T.pi∈ {0，1}n，pi= 1n.我Θ= Θ+ρ（X-L-S），ρ=ρκ，（二十五）7323max{，，} ≤ 0. 001是表1. 视频序列数据集的描述数据集数据大小#背景自动扶梯机场130×160 ×3，4171霍尔机场144×176 ×3，5841Bootstrap120×160 ×2，0551购物中心256×320 ×1，2861公路240×320 ×1，7001大堂128×160 ×1，5462相机参数240×320 ×5，0012照明开关-1120×160 ×2，8002照明开关-2120×160 ×2，7152其中κ >1是控制ρ的增加速度的参数。关于上述优化过程的复杂度，应该注意的是，每个步骤需要O（nd）复杂度，并且通常ALM在有限数目的步骤中收敛[4]，因此我们的方法的总体复杂度是O（nd）。5. 实验在本节中，我们将所提出的方法与几种当前最先进的算法进行比较，包括变分贝叶斯RPCA（VBRPCA）[10]，凸RPCA的IALM [6]，AltProj [19]，NSA[28][29][29]。 特别是，我们遵循[13，21]并在三个应用中评估RES-PCA，包括从视频序列中分离前景-背景，从人脸图像中去除阴影，以及从手写数字中进行异常检测。 所有这些实验都是在Ubuntu系统下进行的，使用12个Intel（R）Xeon（R）W-2133 CPR 3.60GHz。如果达到最多500次迭代，则所有算法均终止，或者X−Lt−StLt+1−Lt表2. 前景-背景分离满意XXX5.1. 前景背景分离前景-背景分离是检测场景中的运动对象或感兴趣的活动，并从视频序列中去除背景和运动对象分别对应于低秩和稀疏对于这项任务，我们使用9个数据集，其特征总结在表1中。在这些视频数据集中，前5个包含单个背景，而其余序列具有2个背景。对于参数，我们将其设置如下。 对于IALM，我们使用理论上最优的平衡参数-我们将秩设置为贡献超过99.5%信息的奇异值的最小数量，“--” presents an“out of memory”PCA，我们使用地面真值秩作为其初始秩参数。为了公平比较，我们将c设置为地面实况埃特尔河1max（n，d）. 相同的平衡参数用于RES-PCA的等级对于所有基于ALM的方法原始文件中提到的PCP和NSA。F或F空气比较，我们使用max（n，d）用于所提出的方法。优化时，我们将参数设置为ρ = 0。0001和κ=1。五、 这些设置在整个过程中保持不变。对于AltProj，我们指定了真实值秩;对于VBR-纸张，除非另有说明。数据方法等级（L）ǁSǁ0/(dn)X−L −SX#Iter。时间启动带AltProj10.93974.22e-43668.61NSA8430.79445.87e-4121343.22VBRPCA11.00009.90e-4175186.90国际资产负债管理7820.80036.11e-4151356.04PCP11740.78593.45e-494571.75RES-PCA10.93797.81e-42316.73埃斯卡拉托机场AltProj10.89873.86e-43369.34NSA10160.63908.09e-4121793.35VBRPCA10.98399.76e-4134168.01国际资产负债管理10650.64826.95e-4151325.40PCP12320.66703.59e-493727.65RES-PCA10.88985.77e-42320.47霍尔机场AltProj10.95731.69e-53793.62NSA9480.74894.89e-4132189.99VBRPCA11.00009.90e-4152240.17国际资产负债管理9740.69177.37e-4142024.10PCP12920.70554.27e-477744.28RES-PCA10.93025.82e-42326.38高速公路AltProj10.88464.63e-427119.17NSA1660.97320.87e-4151238.95VBRPCA11.00009.87e-4126287.27国际资产负债管理3570.79806.25e-4151409.10PCP5310.84402.27e-41521013.00RES-PCA10.93407.20e-42335.32店平商城AltProj10.89078.12e-43085.92NSA1740.93721.57e-4141027.45VBRPCA11.00009.92e-4157295.00国际资产负债管理1510.84576.25e-414498.65PCP2900.88982.85e-4165790.30RES-PCA10.92087.94e-42328.44大堂AltProj20.88.973.77e-42621.58NSA1610.80736.13e-413182.50VBRPCA21.00009.92e-411169.47国际资产负债管理1040.82295.66e-415168.22PCP5020.85002.59e-492166.79RES-PCA20.89631.83e-42520.11相机参数AltProj----------NSA----------VBRPCA11.00009.95e-41711108.20国际资产负债管理11230.70207.81e-4169297.40PCP----------RES-PCA20.83052.48e-425303.57照明开关-1AltProj20.90.844.21e-44873.54NSA5410.65595.87e-413687.19VBRPCA11.00009.83e-4165151.05国际资产负债管理4150.62989.21e-414496.92PCP8480.67765.91e-485410.39RES-PCA20.97084.15e-42331.687324我们在表2中示出了结果。实验结果表明，Alt-Proj、VBRPCA和RES-PCA能够从低等级的视频中恢复背景，而IALM、NSA和PCP具有更高的然而，应注意，VBRPCA可恢复具有低于地面真值的秩的L。例如 ， 在 Light Switch-1 、 Light Switch-2 和 CameraParameter 数 据 集 上 ， 背 景 的 地 面 真 值 秩 为 2 ， 而VBRPCA恢复秩为1的低秩部分。这可能是一个潜在的问题，这将在稍后的视觉说明中清楚。虽然IALM、NSA 和 PCP 不 以 期 望 的 低 秩 恢 复 L ， 但 是 它 们 比AltProj、VBR-PCA和RES-PCA更稀疏地恢复S。此外，我们观察到，所提出的方法的速度优于其他方法。从表2中可以看出，所提出的方法比第二快的AltProj快3倍，比IALM快10倍以上（在某些数据集上甚至快60倍）。虽然所提出的方法在某些数据上的收敛时没有获得最小的误差，但注意到误差的水平与其他方法相当应该注意的是，对于诸如IALM、PCP和NSA的方法，尽管它们不能以期望的低秩恢复L，但是有可能通过调谐它们的平衡参数，它们可以工作得很好。然而，无监督学习方法的参数调整通常是耗时的。所提出的方法具有一个平衡参数，该参数已被经验验证为[6]中提供的理论参数工作良好。一个可能的解释是RES-PCA与凸RPCA有着密切的联系，因此享有相同的最优参数。更多的理论验证有待于进一步的工作中探索。此外，为了直观地比较算法和说明所提出的方法的有效性，我们在图中显示了一些分解结果。1和2.由于IALM、NSA和PCP不能以期望的低秩恢复L，因此它们不能很好地恢复背景。例如，我们可以观察到汽车在高速公路上的阴影图。1.一、VBRPCA在某些数据集上以低于地面真实值的秩重新定位L;因此，在图2中的光开关-2这样的数据上，2我们可以看到，VBRPCA不能很好地工作在不同背景的数据。AltProj和RES-PCA能很好地分离背景和前景为了进一步评估所提出的方法的性能，我们进行了以下实验来比较已经实现最佳性能的两种方法：AltProj和RES-PCA。在这个测试中，我们假设L的真实秩是未知的，并且我们将AltProj的真实秩设置为5，将所提出的方法的真实秩设置为c=5一些获得的结果在图中给出。3和4可以看出，当AltProj失效时，RES-PCA仍然可以很好地分离背景和前景RES-PCA在这类情景中的成功可以解释如下：(a) （b）AltProj（c）图3.当地面真值等级未知时，高速公路视频中的前景-背景分离，因此c被指定为错误的值。左上角是原始帧，其余部分是提取的背景（顶部）和前景（底部）。（a）原始（b）AltProj(e)提出图4. Light Switch- 2视频中的前景-背景分离。 在这两行和最下面的两行中，左上角是原始帧和其余帧分别被提取为背景（顶部）和前景（底部）。L的真值秩，大的背景组通常被分成较小的组，使得每个组内的背景仍然共享相同的结构;因此，RES-PCA仍然可以正确地恢复低秩矩阵。这一观察结果表明，RES-PCA具有优于AltProj的性能时，地面真相的精确知识是未知的先验。5.2. 人脸图像的阴影去除人脸识别是一个重要的课题，然而，它受到人脸图像上的严重噪声和阴影的困扰[2]。因此，需要处理阴影。在该测试中，使用低秩方法，因为（未知的）干净图像驻留在对应于L的低秩子空间中，而阴影对应于S。我们使用扩展耶鲁B（EYaleB）数据集进行比较研究。EYaleB数据包含来自38个人的面部图像，其中我们选择前两个人的图像，即对象1和对象2。每一个都有64张192×168的图像7325××(a) AltProj（b）NSA（c）VBPCA（d）IALM（e）PCP（f）RES-PCA图1.高速公路视频中的前景-背景分离。从上到下分别是原始帧、提取的背景和前景。(a)AltProj（b）NSA（c）VBPCA（d）IALM（e）PCP（f）RES-PCA图2.Light Switch-2视频中的前景-背景分离在第一行和最后三行中，从上到下分别是原始帧、提取的背景和前景像素遵循[6，13]中的常见方法，我们通过对图像进行矢量化来为每个人构建数据矩阵，并对该矩阵执行不同的RPCA算法。我们在图中显示了一些结果5目检。据观察，所有方法都可以成功地去除对象2上的阴影，但有些方法在对象1上失败。实验结果表明，该方法能够有效地去除受试者1和受试者2的人脸图像中的阴影5.3. 异常检测给定来自一个对象的多个图像，它们形成一个低维子空间。这些图像与鲜明的差异-多数人的推论可被视为离群值;此外，来自另一对象的一些图像也被视为异常值。异常检测就是从图像中识别出异常点。建模为L由主导图像组成，而S捕获异常值。对于这个测试，我们使用USPS数据集，其中包括9,298手写数字的大小为16 16。我们遵循[13]并对前190个1的图像和后10个7的图像进行矢量化，由于数据集包含的“1”比“7”多得多对于视觉插图，我们在图中显示了这些数字图像的示例六、它7326(a) 原始（b）AltProj(c)NSA(d)VBPCA(e)国际资产负债管理(f)PCP(g)RES-PCA图5.从人脸图像中去除阴影。每两行是不同原始面的结果。对于每个原始面部，第一行是阴影去除面部图像，而第二行是阴影图像。图6.已从USPS数据集中选择所有的7都是异常值此外，有些我们将RES-PCA应用于该数据集，并获得分离的L和S。在S中，对应于离群值的那些列具有相对较大的值。 在[13]之后，我们使用N2范数来测量S的列，并在图中显示它们的值。7，为了更清晰的可视化，我们已经消除了小于5的值。然后我们在图中显示相应的数字。8，这是检测到的异常值。值得注意的是，RES-PCA已经检测到所有的验证了RES-PCA在异常检测中的有效性。图7. 的值为1。图8.从数据集中检测离群值。5.4. 扩展性我们已经在前面的章节中分析了所提出的方法的可扩展性在本测试中，我们使用表1中的数据集，根据经验验证了我们关于n和d的线性分析结果。对于这些数据集，我们分别采用不同的样本量和数据维的抽样比率在每个子集上，我们执行RES-PCA 10次。从表2可以看出，所有实验在约23-25次迭代内终止;因此在该测试中，我们暂时忽略终止容限，并在设定为30的合理迭代次数内终止实验。 然后我们报告平均时间成本，并在图中显示结果。9.第九条。可以观察到，RES-PCA的时间成本在n和d上都线性增加，这证实了所提出的方法的可扩展性。图9.不同数据集上n和d的时间成本（最佳彩色视图）。6. 结论现有的RPCA方法通常需要求解大型矩阵的SVD，其通常具有至少二次甚至三次复杂度。为了克服这一缺点，本文提出了一种新的RPCA方法。新方法通过利用数据的几何相似性来恢复低秩分量，而不执行当前最先进的RPCA方法通常必须执行的任何SVD。我们开发了一个基于ALM的优化算法，该算法在数据维度和样本大小上都是线性有效的和可扩展的。在不同应用中的大量实验证明了所提出的方法的有效性，其中，我们观察到优越的性能，在速度和视觉质量的几个当前国家的最先进的方法。这些观察结果表明，该方法是适合于大规模的数据应用在现实世界中的问题。确认本研究得到了国家自然科学基金项目61806106、61802215 、 61806045 、 61502261 、 61572457 和61379132的资助。C. 陈and Q. Cheng为通讯作者。7327引用[1] Necdet Serhat Aybat ， Donald Goldfarb ， and GarudIyengar.稳定主成分搜索的快速一阶方法。arXiv预印本arXiv：1105.2126，2011年。5[2] Ronen Basri和David W Jacobs。朗伯反射率和线性子空间 。 Pattern Analysis and Machine Intelligence ， IEEETransactions on，25（2）：218-233，2003。6[3] Amir Beck和Marc Teboulle。线性反问题的一种快速迭代收缩阈值算法。SIAM journal on imaging sciences，2（1）：183-202，2009。4[4] Stephen Boyd，Neal Parikh，Eric Chu，Borja Peleato，Jonathan Eckstein，et al.基于乘数交替方向法的分布式优化和统计学习。基础和Tr端Ma c hinelearning，3（1）：1-122，2011。5[5] 蔡建峰，EmmanuelJCand e`s，和Zu o weiShen. 矩阵完备化的奇异值阈值算法SIAM Journal on Optimization，20（4）：1956-1982，2010. 一、二[6] EmmanuelJCan d`s，XiaodongLi，YiMa，andJohnWright.稳 健 主 成 分 分 析 Journal of the ACM （ JACM ） ， 58（3）：11，2011. 一、五、六、七[7] 克里斯托夫·克鲁和珍蒂安·海斯布鲁克。基于协方差或相关矩阵稳健估计的主成分分析：影响功能和效率。Biometrika，87（3）：603-618，2000. 1[8] Ingrid Daubechies ， Michel Defrise ， and Christine DeMol.稀疏约束下线性逆问题的一种迭代阈值算法。纯粹数学与应用数学通讯，57（11）：1413-1457，2004. 4[9] 费尔南多·德·拉·托瑞和迈克尔·J·布莱克。鲁棒子空间学习框架International Journal of Computer Vision，54（1-3）：117-142，2003。1[10] 丁兴浩，何立汉，劳伦斯·卡林。贝叶斯稳健主成分分析 。 IEEE Transactions on Image Processing ， 20（12）：3419-3430，2011。一、五[11] Ramanathan Gnanadesikan和John R Kettenring。多响应数据的稳健估计、残差和离群值检测Biometrics，第81-124页，1972年。1[12] Gene H Golub和Charles F Van Loan。矩阵计算，第三卷。JHU Press，2012. 1[13] 赵康，崇鹏，强成。基于非凸秩逼近的鲁棒主元分析。数据挖掘（ICDM），2015年IEEE国际会议，第211IEEE，2015年。一、二、五、七、八[14] 柯启发和金田武夫。用交替凸规划法求解存在离群值和缺失数据时的鲁棒l1范数分解. 计算机视觉与模式识别，2005年。CVPR 2005。 IEEE计算机学会会议，第1卷，第739-746页。IEEE，2005年。1[15] Wee Kheng Leow ， Yuan Cheng ， Li Zhang ， TerenceSim，and Lewis Foo.通过固定秩稳健PRIN-UNR成分分析进行背景恢复。图像和模式的计算机分析，第54-61页。Springer，2013. 2[16] Zhouchen Lin，Minming Chen，and Yi Ma.精确恢复低秩矩阵的增广拉格朗日乘子法。arXiv预印本arXiv：1009.5055，2010。1[17] 里卡多·马龙纳河Douglas Martin和Victor J Yohai。稳健的统计数据。John Wiley Sons Ltd Chichester，2006年。1[18] Michael McCoy，Joel A Tropp，等.基于半定规划的鲁棒主元分析的两个建议。电子统计期刊，5：1123-1160，2011年。2[19] Praneeth Netrapalli，UN Niranjan，Sujay Sanghavi，Ani-mashree Anandkumar，and Prateek Jain.非凸鲁棒主元分析。神经信息处理系统的进展，第1107-1115页，2014年二、五[20] 彭崇，赵康，蔡淑婷，程强。整合并征服：基于投影和流形重构的双边二维k-均值算法。ACMTrans. Intell.系统技术，9（5）：57：1-57：25，2018年6月。4[21] 崇鹏，赵康，强成。一种基于快速因子分解的鲁棒主元分 析 方 法 。 2016 年 IEEE第 16 届 数 据 挖 掘 国 际 会 议（ICDM），第1137-1142页。IEEE，2016. 5[22] Chong Peng，Zhao Kang，Huiqing Li，Qiang Cheng.使用 对数 行列 式 秩近 似 的子 空间 聚 类。第 21 届ACMSIGKDD知识发现和数据挖掘国际会议论文集，第925-934页。ACM，2015. 2[23] 杜金川和尹相云核范数正则化线性最小二乘问题的一种加速逼近梯度算法. Pacific Journal of Optimization，6（615-640）：15，2010. 1[24] N. Vaswani，T. Bouwmans，S. Javed和P.纳拉亚纳-穆尔蒂。鲁棒子空间学习：鲁棒主元分析、鲁棒子空间跟踪与鲁棒子空间恢复。IEEE信号处理杂志，35（4）：32- 55，2018年7月。1[25] John Wright ， Arvind Ganesh ， Shankar Rao ， YigangPeng，and Yi Ma.稳健主成分分析：通过凸优化精确重新阐述腐败的低秩矩阵。神经信息处理系统的进展，第2080-2088页，2009年。1[26] Huan Xu，Constantine Caramanis，and Sujay Sanghavi.通过离群值追踪法反作用于主成分分析。神经信息处理系统进展，第2496-2504页，2010年。2[27] Lei Xu and Alan L Yuille.基于统计物理方法的自组织规则 鲁 棒 主 成 分 神 经 网 络 ， IEEE Transactions on ， 6（1）：131- 143，1995。1[28] Zihan Zhou ， Xiaodong Li ， John Wright ， EmmanuelCandes，and Yi Ma.稳定的主成分追踪。信息理论会议录（ISIT），2010 IEEE国际研讨会，第1518-1522页。IEEE，2010。5