基于投影的鲁棒主成分分析：实时处理大数据的在线算法

==∥ ∥∥ ∥∗⃝可在www.sciencedirect.com上在线ScienceDirectICT Express 1（2015）59www.elsevier.com/locate/icte基于投影的鲁棒主成分分析HyeungIl Lee，JungWoo Lee韩国首尔国立大学电子与计算机工程系接收日期：2015年6月8日;接受日期：2015年2015年9月25日在线发布摘要鲁棒PCA是PCA的一种改进，它可以很好地处理损坏的观测值。现有的鲁棒PCA算法通常基于批优化，并且必须将所有样本加载到内存中。因此，这些算法随着数据量的增加而具有较大的计算复杂度在本文中，我们提出了一种基于投影的鲁棒主成分分析（RPCA），以使用RPCA作为实时处理的在线算法。本文提出的在线算法大大降低了计算复杂度，尽管与传统方案相比，该算法的性能下降可以忽略不计该方法适用于各种需要RPCA实时处理的应用场合。2015年，韩国通信信息科学研究所。制作和托管由Elsevier B.V.这是一个开放获取的文章根据CC BY-NC-ND许可证（http：//creativecommons. org/licenses/by-nc-nd/4. 0/）。关键词：鲁棒PCA;在线算法;投影技术1. 介绍鲁棒PCA（Robust Principal Component Analysis）是一种将给定矩阵分解为低秩矩阵和稀疏矩阵的技术。它被认为是一个有效的替代传统的PCA方法在多个离群点的环境中。RPCA有几个应用，例如，当数据大小增加时，计算机视觉中的前景-背景分离，人脸识别，推荐系统等（即，大数据），然而，对于基于批处理的传统RPCA，计算复杂度变得太大。因此，我们需要一种不同的方法来实时处理大数据。本文提出了一种基于投影的RPCA技术，将传统的RPCA改进为在线算法。该方法通过将附加数据投影到低秩矩阵的列空间而不是在附加数据进入时再次对累积数据应用RPCA来显著降低计算复杂度我们预计，我们提出的算法是有用的，在各个领域需要实时处理的鲁棒PCA。*通讯作者。电子邮件地址：junglee@snu.ac.kr（J. Lee）。假设给定矩阵M是低秩矩阵L0和稀疏矩阵S0之和。M=L0+ S0。稀疏矩阵是指大多数元素为零的矩阵鲁棒主成分分析（RobustPCA）是利用给定的矩阵M重构低秩矩阵L0和稀疏矩阵S0的方法。让我们考虑一个优化问题。最小化λL+λλS1满足L+S= X。这个问题被称为主成分追踪（PCP）。λ是一个常数，M是矩阵M的奇异值之和的核范数。M1是一个l1范数，它是M的所有元素的绝对值。我们可以提出以下两个主要问题。(1) 是否有可能解决上述优化问题的解决方案？(2) 如果可能，解S和L是否唯一，并且S S0，L L0？证明了在一定条件下，随着矩阵的增大，上述优化问题的解等于L0且S0收敛于http://dx.doi.org/10.1016/j.icte.2015.09.0032405-9595/c2015韩国通信信息科学研究所。制作和托管由爱思唯尔B. V.这是一个开放获取的文章下，CC BY-NC-ND许可证（http：//creativecommons。org/licenses/by-nc-nd/4. 0/）。∈∈∈=-= − −µµk+1 k k+F=+ −− ++= −−60H. Lee，J.Lee/ICT Express 1（2015）59一个[1]。换句话说，如果数据矩阵L0的秩足够低，而误差矩阵S0足够稀疏，那么我们可以仅用矩阵L0和S0的和来完全重构矩阵L0和S0。我们称这种技术为鲁棒PCA。有几种实现鲁棒PCA的算法，如内点方法[2]，增广拉格朗日乘数（ALM）方法[3]。我们介绍这些算法，并解释为什么这些算法不能应用于实时处理。首先，由于PCP是一类半定规划（SDP），我们可以用凸解或SDP解来求解，这与内点法是相同的。内点法虽然迭代次数少，收敛速度快，但由于每次迭代的计算复杂度为O（n6），很难应用于PCP问题。ALM方法是求解PCP问题的最快算法。增广拉格朗日函数定义如下。l（ L， S， Y，µ）=L+λS1+Y M−L−S+µmM−L−S2。提出了一种跟踪算法GRASTA。该算法从噪声、损坏和不完整的数据中估计低秩模型，即使最好的低秩模型可能会随着时间的推移而变化。然而，该论文并没有证明算法的收敛性在[5]中，Feng等人提出了一种比GRASTA更有效的算法.他们开发了一种在线鲁棒PCA（OR-PCA）方法。与以往的基于批处理的方法不同，该算法不需要重复使用所有过去的样本，并且实现了更有效的存储效率。OR-PCA的主要思想是通过将核范数分解为两个低秩矩阵的显式乘积来重新表达PCP的目标函数。给出了OR-PCA方法的收敛性分析，并证明了OR-PCA渐近收敛于批RPCA的解。在本文中，不同于传统的方法，我们提出了一个基于投影的在线算法。传入的数据向量被投射到预先计算的低秩子空间，该子空间定期更新。3. 问题公式化假设观测数据M∈Rm×n由一个低秩矩阵L∈Rm×n和一个稀疏矩阵S∈Rm×n组成。2为了将其扩展到在线算法，让我们假设为了使函数l（ L， S， Y）最小化，我们可以利用另一种方法，迭代方向方法，其如下迭代地更新L、 S和Y算法：交替方向主成分追踪[23]在每个时刻添加由低秩项LtRm和稀疏项StRm组成的数据向量MtRm现有的RPCA算法大多是基于批处理的方式，每当有新的数据向量加入时，都要重新运行整个算法。很难运行这些批处理模式算法，因为没有足够的空间来存储1：初始化：S0Y00，µ >02：未收敛时执行3：计算L D M S−1Y4：计算Sk+1Sλµ M Lk+1µ−1Yk5：计算Yk1 Ykµ（M Lk1 Sk1）6：结束时7：输出：L，S该算法的计算复杂度为O（n3），因为在计算Lk1时需要进行奇异值分解（SVD），并且它消耗了大部分的计算量.这些算法在数据量较小的情况下工作良好。然而，当涉及到大数据时，它们不再起作用，因为ALM算法的计算复杂度是O n3。我们需要一种不同的方法来应用于实时处理，即使有一些性能下降。2. 相关工作鲁棒主元分析（RPCA）的目的是从高度不连续的测量矩阵中重新覆盖一个低秩矩阵和一个稀疏矩阵。最近的文献[1]证明了RPCA可以通过求解核范数最小化（PCP）问题来解决然而，这种核范数最小化方法是以批处理模式实现的。因此，很难应用于实时处理。关于在线算法，现有的文献不多鲁棒PCA [4，5]。在[4]中，提出了一种鲁棒 在线子空间跟踪算法，称为Grassmannian鲁棒自适应子空间数据，并且随着数据大小的增加，执行鲁棒PCA的计算变得过于繁重。为了解决这个问题，我们提出了一个基于投影的RPCA，这将在下一节中描述。4. 基于投影的RPCA现有的RPCA算法在每次插入新数据时都需要对整个数据进行处理，难以应用于在线算法。随着数据量的增加，计算复杂度增加，实时处理是不可能的。如果我们使用基于投影的方法，则很容易实时处理数据，因为我们不必使用整个存储的数据，而只需使用先前计算结果的插入数据投影方法基于以下观察结果。如果数据大小变大，则在使用附加数据运行鲁棒PCA之后，低秩分量矩阵很可能例如，当我们在对具有1000行的测量矩阵执行鲁棒PCA之后获得10维低秩矩阵时，具有1001行的测量矩阵的低秩分量（第1001行是新数据）很可能仍然具有10维。利用这一点，我们可以将新数据投影到低秩空间，并将误差作为稀疏向量，而不是每次增加一个新数据就执行整个鲁棒PCA算法，从而使计算复杂度指数级然而，随着数据的堆积，计算的投影子空间和实际列空间←=--L=UVnewnew=−联系我们中国=++×+ =+−+H. Lee，J. Lee / ICT Express 1（2015）59-6261的低秩矩阵的增加，所以我们必须定期更新的低秩空间，通过执行整个鲁棒PCA算法的所有数据。图1描述了基于投影的鲁棒PCA算法的概念。例如，如果更新周期（T）为1000，则我们可以以T（1000）的周期更新通过批模式鲁棒PCA算法获得的低秩矩阵的列空间，然后将下一个T（1000）数据投影到更新后的低秩空间。我们可以将误差视为稀疏分量，并更新稀疏矩阵。这种方法虽然由于低秩空间的不准确而使性能略有损失，但它降低了计算量。这是因为它仅需要一列的投影操作，而不是在每个时刻执行鲁棒PCA。Fig. 1. 基于投影的RPCA。算法：基于投影的鲁棒PCA输入：M1、M2、. . . 、.、 M Tn（观测数据），T（空间更新周期），k1到n1 do(1) 使用批处理RPCA [M1]更新低秩矩阵MTk]LnewSnew(2) 利用奇异值分解H新U Unew对于t1 到T，(1) 利用投影LT k tU UH U−1 UH MT k t(2) 计算稀疏项ST k tMT k tLT k t首尾相接返回L=[L1：LTn]（低秩矩阵），S=[S1：STn]（稀疏矩阵）876543210图二.比较RPCA、移动RPCA和基于投影的RPCA的MMSE。表1算法的计算速度（CPU时间）比较5. 仿真结果5.1. 随机矩阵我们通过实现3种不同的算法来评估性能和计算速度，假设最初有100 × 300个矩阵数据，并且100个列向量被添加30次以上。输入矩阵M通过将秩为5的低秩矩阵L0和稀疏度（非零元素的比率）为0.1的稀疏矩阵S0相加第一种算法是传统的RPCA算法（全批处理模式算法），它在每次数据插入时执行RPCA该方法具有理想的性能，但是，随着数据大小的增加，实际实施变得不可能。移动RPCA是RPCA方法，它只使用最新的20个数据列向量。投影RPCA是所提出的算法。图2和表1显示了算法的性能和算法的速度。所提出的算法的性能有所下降操作时间（s）批次RPCA 31.4移动RPCA 21.51. 2 ×10−3与RPCA相比，它具有更好的性能。该算法的计算速度是其他算法的20倍。5.2. 应用：Foreground–background separation is one of primary 如今，在大多数城市都有无数的监视摄像头.为了处理这种实时的大数据，需要一种鲁棒的PCA在线算法。在本节中，我们将所提出的算法应用于实际的监控视频数据，并比较算法的性能。视频数据由240帧组成，并且每帧具有400 300像素的分辨率换句话说，每个时刻都有120，000个新数据添加我们假设前200帧62H. Lee，J.Lee/ICT Express 1（2015）59图3.第三章。比较批处理RPCA和投影RPCA用于并且依次添加剩余的40个帧。对于批处理RPCA，我们使用ALM算法，这是迄今为止已知的最快的算法。利用投影RPCA，我们将其余40帧投影到低秩空间上，该低秩空间是对初始200帧进行批量RPCA的结果。图3示出了两种算法的第201帧的结果，图4示出了第240帧的结果。第201帧的结果表明，投影RPCA的性能退化然而，第240帧的结果表明，前景部分（稀疏部分）具有一些背景，因为低秩空间在投影时段中发生了微小变化。在计算复杂度方面，由于ALM算法是基于奇异值分解（SVD）的，因此其计算复杂度为O（n3）而投影RPCA的计算复杂度为O（ n），因此计算复杂度降低因子为O（n2）.两种算法对于40帧的运算速度如表2所示。在ALM情况下，每帧的处理时间的平均值为253.1 s。然而，在投影RPCA情况下，它是0.11s。6. 结论和今后的工作本文提出了一种基于投影的RPCA算法，该算法大大降低了计算复杂度，可以作为一种在线（递归）算法。仿真结果表明，该算法在性能略有下降的情况下，计算复杂度大大降低，可用于实时数据处理。见图4。批量和投影RPCA在前景-背景分离中的比较表2批处理和投影RPCA的计算速度比较。操作时间（每帧）（s）批次RPCA（ALM）253.1投影RPCA 0.11致谢这项研究得到了BasicNRF的科学研究计划（NRF-2013 R1 A1 A2008956），仿生机器人研究中心由国防采购计划管理局（UD 130070 ID）、INMAC和BK 21-plus资助引用[1] E.J. Cande` s，X。Li，Y.妈妈，J。Wright，Ro用主成分分析，J. ACM（2015），http://dl.acm.org/citation.cfm? doid=1970392.1970395。[2] M. Grant，S. Boyd ，CVX：Matlab software for disciplinary convexprogramming，（2009），http：//stanford.edu/cvboyd/cvx.[3] X.袁，J.杨，稀疏和低秩矩阵分解通过交替方向方法，太平洋J。（ 2013 ） ， http ： //www. ybook 。 有 限 jp/online2/oppjo/vol9/p167.HTML.[4] Jun He，Laura Balzano，John Lui，Online robust subspace trackingfrom partial information，（2015），arXiv：1109.3827.[5] J. Feng，H. Xu，S. Yan，通过随机优化的在线鲁棒PCA，神经信息。过程（2013），http://papers.nips.cc/paper/5131-online-robust-pca-via-stochastic-optimization.