低秩表示不完整的数据

文摘

低秩矩阵恢复(LRMR)已经成为一个越来越受欢迎的技术分析数据与失踪的条目,总资产管理和异常值。LRMR的重要组成部分,低秩表示模型(远程雷达)寻求最低等级表示在所有样本和是强劲的恢复子空间结构。本文试图解决问题部分的远程雷达观测到的条目。首先,我们构造一个凸极小化的低繁茂,健壮性和不完全考虑。然后我们采用增广拉格朗日乘数法的技术来解决该项目。最后,合成和真实数据集上实验结果验证该方法的可行性和有效性。

1。介绍

社区的模式识别、机器学习和计算机视觉,调查数据集通常有内在的低秩结构虽然他们可能是高维。低秩矩阵恢复(LRMR) (1- - - - - -3]是一种模型,该模型不仅利用关键的低信息完成缺失的条目,恢复稀疏噪声,识别异常值,并建立一个关联矩阵。它也可以被看作是压缩传感的概括从一个以两个订单由于低繁茂的稀疏矩阵的等价于奇异值。最近,LRMR已经收到了越来越多的关注领域的信息科学与工程,取得了巨大的成功在视频背景建模4,5),协同过滤(6,7),和子空间聚类3,8,9),这些只是其中一部分。

一般来说,LRMR主要由三个吸引人的类型,也就是说,矩阵完成(MC) [1),稳健主成分分析(RPCA) [2,4低秩表示(远程雷达)[的],3,8]。其中,MC旨在完成失踪的条目的援助低秩财产和最初被描述为一个仿射最小化问题。在过去的几年中,仿射排名最小化凸圆地放松成核范数最小化(10),它是证明,如果采样条目的数量和奇异向量满足一些条件,然后由解决大多数低秩矩阵可以完全恢复上述凸程序(1]。

经典的主成分分析(PCA) (11小高斯噪声非常有效,但它不工作在实践中当样品损坏的数据异常值或大型稀疏噪声。为此,提出了几个强大的变异PCA先后在过去二十年(12,13]。由于开创性的研究工作(4),主成分(PCP)追求RPCA方法已经成为一个标准。这种方法最大限度地减少核规范和加权组合与线性等式约束规范。是证明低秩和稀疏的组件可以恢复完全主导概率在某些条件下通过求解卡式肺囊虫肺炎(4]。

在子空间聚类,常用的假设是,数据在多个低秩子空间的联盟,每个子空间有足够的样品相比,其排名。刘等人。3通过远程雷达)提出了一个健壮的子空间恢复技术。任何样本在每个子空间可以表示为基础的线性组合。的低复杂性系数线性表示利用低秩结构是非常有用的。远程雷达试图寻求共同的最低等级表示所有数据,这是表明,受污染的数据异常值可以完全恢复在一定条件下通过求解一个凸程序(8]。如果选择的基础是一个单位矩阵的列和规范是用来测量稀疏,那么远程雷达是变成RPCA的卡式肺囊虫肺炎。

失踪的条目的数据集和大型稀疏的腐败、子空间结构的强劲复苏可能是一个具有挑战性的任务。可用的算法MC总值不健壮的腐败。此外,大量的缺失值将恢复远程雷达的性能的退化或RPCA。在本文中,我们试图解决这一问题的低秩子空间恢复缺失的存在价值和稀疏的噪音。具体来说,我们提出的模型不完整的低秩表示(ILRR)这是一个直接的远程雷达泛化。ILRR模型可以归结为一个凸优化模型,最大限度地减少核规范和的结合规范。为了解决这个项目,我们设计一个迭代计划通过应用不精确的增广拉格朗日乘数法的方法(ALM)。

本文的其余部分组织如下。部分2简要回顾LRMR的预赛和相关工作。提出了ILRR的模型和算法部分3。节4,我们将讨论ILRR及其关系的扩展与现有的作品。我们比较ILRR与最先进的算法的性能在合成数据和真实数据集的部分5。最后,部分6得出一些结论。

2。预赛和相关工作

本节介绍相关的初步材料有关矩阵和代表的低秩矩阵模型复苏(LRMR)。

矩阵的选择规范在LRMR中扮演一个重要的角色。在下面,我们目前的四个重要类型的矩阵规范。对于任意的弗罗贝尼乌斯规范表达的是,规范是,规范是,核规范,在那里是th的条目和是最大奇异值。其中,矩阵核规范是最紧凑的秩函数的凸松弛,和规范和规范经常用来测量噪声的稀疏矩阵。

考虑一个数据矩阵堆放的训练样本,每一列的表明样本的维数。LRMR的领域内,以下三个近端最小化问题(3,4)广泛使用: 在哪里是一个积极的常数用来平衡正则化项和近似误差。对于给定和我们定义三个阈值操作符,,如下: 在哪里是奇异值分解)。这是证明,上述三个优化问题用封闭形式的解决方案(4),(14),而(8),分别。

我们假设是煤。因为低秩矩阵的自由度是远远低于其条目的数量,可以完全恢复所有失踪的条目从部分观察条目只要采样的数量满足某些条件的条目。在形式上,矩阵完成(MC)的问题1可以制定如下: 在哪里,,。我们定义了一个线性投影算符如下: 因此,约束问题(3)可以写成。

主成分分析得到最优估计小加性高斯噪声,但是对于大型稀疏分解污染。这里的数据矩阵被认为是一个低秩矩阵的叠加和稀疏噪声矩阵。在这种情况下,稳健主成分分析(RPCA)是非常有效的低秩和稀疏恢复组件通过求解一个凸的程序。数学上,RPCA可以被描述为以下核范数最小化[2]: 在哪里是一个积极的权重参数。顺序RPCA推广到一个稳定的版本,同时小扰动稳定和健壮的总值稀疏的腐败15]。

我们进一步假设数据集是自我表达的,也是低秩表示系数矩阵。基于上述两个假设,模型的低秩表示(远程雷达)3)表示为 在哪里是系数矩阵,是噪声矩阵,然后呢是一个积极的平衡参数。这个模型非常有效的检测异常值和最优支持子空间强劲复苏。子空间聚类的关联矩阵可以由最优问题(6)。

问题(3),(5)和(6)属于核的范数最小化。现有的算法前面的优化主要包括迭代阈值,加速梯度,近端双重方法,增广拉格朗日乘数法(ALM) (16]。这些算法是可伸缩的由于采用一阶信息。其中,ALM,也称为乘数的交替方向方法(小组ADMM) [17),是一个非常受欢迎的和有效的方法来解决核的范数最小化。

3所示。不完整的低秩表示的模型和算法

本节提出了一种低秩表示不完整的数据模型,开发相应的迭代方案这个模型。

3.1。模型

我们考虑一个不完整的数据矩阵并表示设定的采样指数。的th条目的缺少当且仅当吗。为了方便起见,我们将所有失踪的条目0。同时恢复丢失的条目和低秩子空间结构,我们构建一个不完整的低秩表示(ILRR)模型: 在哪里是一个积极的常数和对应于完成参数。如果没有任何遗漏的条目,也就是说,相当于远程雷达,那么上面的模型。换句话说,ILRR远程雷达是一个特例。

为了解决方便非凸核范数最小化(7),我们将介绍两个辅助矩阵变量和。在这种情况下,上述优化问题是新配方 这是相当于最小化问题 的因素。不考虑约束,我们构造增广拉格朗日函数的问题(9)如下: 在哪里之间的内积算子矩阵和是一个拉格朗日乘子矩阵,。在接下来的部分中,我们将提出一个不精确的增广拉格朗日乘数法(IALM)方法来解决问题(8)或问题(9)。

3.2。算法

不精确的ALM (IALM)方法使用一个交替更新策略和它最小化或最大化函数对每个块变量在每个迭代。让。

计算 。当是未知的和其他变量是固定的,计算过程的如下:

计算 。如果矩阵是未知的和其他变量,通过最小化更新: 让。通过设置的导数为零,我们有 或者,同样, 在哪里是一个阶单位矩阵。

计算 。矩阵的更新公式计算如下: 考虑约束条件进一步,我们得到的迭代公式 在哪里补充的吗。

计算 。修复,和最小化关于:

计算 。修复,计算如下: 在哪里。的导数是。因此,我们获得的更新通过设置:

计算 。鉴于,和,我们计算如下 在具体实现中,更新根据以下公式:

我们表示的零矩阵。整个迭代过程中概述的算法1。算法的停止条件1可以设置为 在哪里是一个足够小的正数。

3.3。收敛

当通过IALM方法解决ILRR,块变量或者更新。现在,我们这五块变量同时进行更新;也就是说, 修改后的方法被调用的ALM方法。因为问题的目标函数(8)是连续的,确切的ALM方法是收敛的18]。然而,它仍然是很难证明IALM的收敛。困难有两个原因:一是凸约束的存在(8),另一块变量的数量是两个以上。然而,部分的实验结果5证明算法的正确性和有效性1在实践中。

4所示。模型的扩展

在ILRR模型中,这个词的主要目的是增强鲁棒性噪声和离群值。如果我们不考虑异常值应该换成。为新ILRR模型,我们可以设计一个算法只修改步骤4的算法1如下: 如果我们的替代品为并设置,然后问题(7)是低秩子空间聚类的完整版本(LRSC)与未堕落的数据9]。如果我们更换和通过和分别和合并到限制,然后问题(7)是稀疏的子空间聚类的完整版本(SSC)没有茂密的错误(19]。

ILRR使用数据自己是字典。现在,我们扩展字典和噪音稀疏到更一般的情况下。因此,我们获得一个全面的ILRR形式: 在哪里代表了字典,是系数矩阵,然后呢表明一定标准的。如果是一个阶单位矩阵,被选为,然后问题(25)对应的完整版本RPCA [20.]。如果我们进一步加强,然后问题(25)成为MC的等效公式16]。此外,如果是一个未知的正交矩阵和,然后问题(25MC)相当于矩阵分解方法(21]。最后,如果我们让和堆叠的测试样本和训练样本,分别取而代之的是,让,然后问题(25)变成了健壮的模式识别通过稀疏表示的完整版本(22]。

5。实验

在本节中,我们验证了该方法的有效性和效率进行实验合成数据和实际数据集。实验结果不完整的低秩表示(ILRR)与其他先进的方法:稀疏的子空间聚类(SSC),低秩子空间聚类(LRSC)和低秩表示(远程雷达)。对于后者的三种方法,缺失的值替换为0。SSC和LRSC,参数调整来实现最佳的性能。容忍的错误被设置为在所有的实验。

5.1。合成数据

我们随机生成一个正交矩阵和一个旋转矩阵。其他四个构造正交矩阵,。因此,五个独立的低秩子空间是横跨的列,分别。我们画40从每个子空间向量的数据,的条目是相互独立的,他们服从标准正态分布。我们设置和随机选择20列向量是损坏的。在本部分中,所选的列向量由高斯噪声污染与零均值和标准偏差。由此产生的矩阵表示为。

我们把样品根据均匀分布和表示抽样指数集。抽样率(SR)被定义为,在那里的基数和意味着没有条目失踪。因此,一个不完整的矩阵是由。权衡参数在远程雷达和ILRR设置为0.1。在运行算法1,我们获得最优矩阵低秩表示。的基础上,我们构造一个关联矩阵,在那里是指绝对值运算符。然后我们选择光谱聚类(23)作为聚类算法通过归一化互信息和评估集群性能(敝中断)。让集群是一组真实的标签,让集群是一组得到的谱聚类算法。敝中断是计算 在哪里互信息度量和吗的熵。敝中断值在和一个更大的敝中断值表示一个更好的聚类性能。

在实验实施,我们不同SR 1从0.2到0.1的区间。对于每个固定的老,我们重复实验和报告平均敝中断10倍。我们首先比较亲和矩阵由SSC, LRSC、远程雷达和ILRR,部分如图所示1。从图1,我们注意到,我们的方法表现出明显的块结构与其他三种方法相比,而SSC, LRSC,远程雷达没有block-diagonal结构。这个观察意味着只有ILRR可以保持紧凑的表示相同的子空间和发散表示为不同的子空间,当大量的值是失踪。

其次,我们比较敝中断ILRR值与其他三种方法在不同的SR,如图2。从这个图可以看出,敝中断值SSC,远程雷达,ILRR几乎是一个如果,而ILRR敝中断值高于其他三种方法。换句话说,SSC的敝中断值,LRSC,远程雷达大大降低老的减少这些观察验证ILRR比其他方法更健壮的缺失值。

5.2。面对集群

我们开展面对集群实验扩展的一部分耶鲁脸上数据库B (24拥有大量的腐败。整个数据库包含38个对象,每个对象拥有大约64的图像。我们选择第一个10对象和每个图像的大小为32×32。因此,面对图像数据集表示为一个矩阵,大小为1024×640。每一列的数据矩阵归一化到一个单位长度的考虑可变光照条件和姿势。

样本集的生成方式类似于前面的部分。我们改变老的值从0.1到1的间隔0.1和设置在远程雷达和ILRR。SSC敝中断的比较值比较,LRSC,远程雷达,ILRR,如图3,每个敝中断值是10个重复实验的平均结果。从图可以看出3如果,ILRR达到相对稳定的敝中断值,而其他三种方法获得更糟比ILRR敝中断值。这个观察表明,SSC, LRSC和远程雷达更敏感比ILRR SR。

此外,ILRR恢复优势低秩组件相对于其他三种方法。在下面,我们给经济复苏ILRR的性能对比。在这里,我们只考虑两种不同的老;也就是说,和。对于这两个给定的SR,原始图像采样图像,图像中恢复过来,而且噪声图像部分在图所示4和5,分别。在这些采样图像,未取样的条目显示在白色的。从这两个数字,我们不仅可以看到ILRR自动纠正错误(阴影和噪声),但也恢复有效低秩组件。

5.3。运动分割

在这一部分中,我们测试提出ILRR运动分割的任务的方法。我们认为8序列的户外交通场景,霍普金斯155数据集的一个子集25]。这些序列是由一个移动的手持相机,他们跟踪两辆车翻译和旋转的一条街上,部分如图所示6。这些序列是来自两个或三个动作,一个运动对应一个子空间。总共有8个集群任务以来每个序列的运动分割是唯一聚类任务。运动分割的任务是根据给定的特征进行提取和跟踪在多个帧的视频序列。

每个序列的提取特征点可以被改造成一个大约低秩矩阵列,=特征点的数量。详细实验实现,我们考虑不同SR变化从0.2到1,间隔0.2。正则化参数设置在远程雷达和ILRR设置为2。老固定序列和固定,每个方法重复10次,意味着敝中断值记录下来。我们报告的平均和标准推导敝中断8序列值,如表所示1。

从表1,我们可以看到,尤其是ILRR获得很高的敝中断值,而敝中断其他三种方法的值是不可接受的。尽管SSC段每个子空间时老,小有致命影响SSC的分割性能。总之,ILRR更健壮的大量缺失值比其他三种方法。

6。结论

在本文中,我们调查的低秩表示模型不完整的数据,它可以被视为低秩表示和矩阵的推广完成。不完整的低秩表示的模型,我们提出一个迭代计划基于增广拉格朗日乘数法。实验结果表明,该方法是可行的和有效的在恢复低秩结构,完成缺失项,消除噪音。它仍然需要进一步研究如何构造一个低秩矩阵恢复的一般模型和设计相应的算法。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这部分工作是由中国国家自然科学基金(没有。61403298,没有。11326204,没有。11401457,没有。11401357),陕西省自然科学基础研究计划(没有。2014 jq8323也没有。2014 jq1019),陕西省教育部门(没有。2013 jk0587也没有。2013 jk0588),汉中政府科技(没有。2013 hzzx-39)。

引用

1. e . j .萤石和b·雷希特“确切矩阵通过凸优化完成,”计算数学基础,9卷,不。6,717 - 772年,2009页。视图:出版商的网站|谷歌学术搜索|MathSciNet
2. j·赖特,y, y, a . Ganesh和s . Rao,“稳健主成分分析:精确恢复损坏的低秩矩阵的凸优化”学报》第23届年会在神经信息处理系统(捏' 09)22卷,第2088 - 2080页,2009年12月。视图:谷歌学术搜索
3. g .刘、林z和y,“健壮的子空间分割在低秩表示,”学报》第27届国际会议上机器学习,第670 - 663页,2010年。视图:谷歌学术搜索
4. e . j .萤石x, y,和j·赖特,“稳健主成分分析?”ACM的杂志,卷。58岁的没有。3、第十一条,2011年。视图:出版商的网站|谷歌学术搜索|MathSciNet
5. t . Bouwmans和e·h·Zahzah”,通过主成分追求稳健的主成分分析:比较评价的回顾视频监控,“计算机视觉和图像理解卷。122年,22-34,2014页。视图:出版商的网站|谷歌学术搜索
6. j·d·m·兰尼和n . Srebro“快速最大优势矩阵分解的协同预测,”学报》第二十二届国际会议上机器学习(ICML ' 05)2005年8月,页713 - 719。视图:出版商的网站|谷歌学术搜索
7. f .聂h . Wang x Cai et al .,“强大的矩阵完成通过联合Schatten p-norm lp-norm最小化,”学报》第12届IEEE国际会议数据挖掘,第574 - 566页,2012年。视图:谷歌学术搜索
8. 林z . g . Liu,燕,j .太阳和马y, y Yu”强劲复苏的子空间结构低秩表示,“IEEE模式分析与机器智能,35卷,不。1,第184 - 171页,2013。视图:出版商的网站|谷歌学术搜索
9. r·维达尔和p . Favaro低秩子空间聚类(LRSC)”模式识别的字母,43卷,不。1,47 - 61、2014页。视图:出版商的网站|谷歌学术搜索
10. m·b·雷希特泽,p . a . Parrilo”保证minimum-rank通过核范数最小化线性矩阵方程的解决方案,“暹罗审查,52卷,不。3、471 - 501年,2010页。视图:出版商的网站|谷歌学术搜索|MathSciNet
11. i t . Jolliffe主成分分析,施普林格系列统计,第二版,2002年版。
12. f . De La Torre和m . j .黑色,“计算机视觉,稳健主成分分析”第八届国际会议上计算机视觉学报》上2001年7月,页362 - 369。视图:谷歌学术搜索
13. c .叮,d .周x他et al .,“R1-PCA:旋转不变L1-norm主成分分析对健壮的子空间分解,”学报》第23届国际会议上机器学习,第288 - 281页,2006年。视图:谷歌学术搜索
14. 肯尼迪。Cai、e . j .萤石和z沈,“矩阵奇异值的阈值算法完成。”暹罗杂志上优化,20卷,不。4、1956 - 1982年,2010页。视图:出版商的网站|谷歌学术搜索|MathSciNet
15. 李x, z周,j·赖特,e .萤石和y妈,“主成分追求稳定,”《IEEE国际研讨会信息理论(有10)德克萨斯州奥斯汀市,页1518 - 1522,美国2010年6月。视图:出版商的网站|谷歌学术搜索
16. 林z, m . Chen l .吴et al .,“增广拉格朗日乘子方法精确恢复损坏的低秩矩阵,“技术。众议员uilu - eng - 09 - 2215,伊利诺斯,2010年。视图:谷歌学术搜索
17. x元,j .杨“稀疏低秩矩阵分解的,通过交替方向方法,”香港浸会大学的技术报告,2009年。视图:谷歌学术搜索
18. d . p . Bertsekas约束优化和拉格朗日乘子方法、计算机科学和应用数学,学术出版社,纽约,纽约,美国,1982年。视图:MathSciNet
19. 大肠Elhamifar r·维达尔,“稀疏的子空间聚类算法,理论,应用程序,”IEEE模式分析与机器智能,35卷,不。11日,第2781 - 2765页,2013年。视图:出版商的网站|谷歌学术搜索
20. j·史、郑x和l .勇”不完整的稳健主成分分析,ICIC表达字母B部分:应用程序,5卷,不。6,1531 - 1538年,2014页。视图:谷歌学术搜索
21. 刘y和f .商”,一个高效的矩阵张量分解方法完成,”IEEE信号处理信件,20卷,不。4、307 - 310年,2013页。视图:出版商的网站|谷歌学术搜索
22. j·赖特,a, y, a . Ganesh s Sastry,和y妈,“基于稀疏表示的人脸识别,”IEEE模式分析与机器智能没有,卷。31日。2、210 - 227年,2009页。视图:出版商的网站|谷歌学术搜索
23. Ng, m·乔丹和y . Weiss,“光谱聚类:分析和一种算法,”先进的神经信息处理系统,14卷,第856 - 849页,2002年。视图:谷歌学术搜索
24. a . s . Georghiades p . n . Belhumeur, d . j . Kriegman”从几个到许多:光照锥模型下的人脸识别变量照明和姿势,”IEEE模式分析与机器智能,23卷,不。6,643 - 660年,2001页。视图:出版商的网站|谷歌学术搜索
25. r·维达尔和r·哈特利”三个视图多体结构与运动,”IEEE模式分析与机器智能,30卷,不。2、214 - 227年,2008页。视图:出版商的网站|谷歌学术搜索

版权

版权©2014 Jiarong史等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。