《robust principal component analysis》由会员分享，可在线阅读，更多相关《robust principal component analysis（7页珍藏版）》请在金锄头文库上搜索。
1、论文阅读报告题目：Robust Principal Component Analysis?作者：EMMANUEL J. CAND ES ,XIAODONG LI ,YI MA ,JOHN WRIGHT摘要大数据的降维与减轻规模是科学工程社会等领域的热点也是难点之一.它具有广泛的应用前景和重要的理论研究价值.给定一个数据矩阵,它是低秩成分和稀疏成分的叠加.在适当的假设下,通过解决一个称为 Principal Component Pursuit的非常恰当的凸规划,就可以精确地恢复低秩和稀疏成分.在所有可行的分解方法中,他们选择对核范数与 范数的加权组合进行最小化.并表明了原则方法对鲁1l棒主成分分
2、析的可能性,因为他们的方法和结果证明可以恢复数据矩阵的主成分即使它的元素的正定部分是任意毁坏的.这还拓展到小部分元素丢失的情形中.然后他们讨论解决这种最优问题的算法,以及在视频监控领域的应用现状.这里他们的方法考虑了在混乱背景中的检测目标,在人脸识别领域,提供了一种去除阴影和改善图片中人脸变形的情况的原则方法.对以后的工作启示为开发更好的伸缩性算法来处理大规模数据集.关键词：低秩成分 稀疏成分 PCP 伸缩性算法1、问题的提出最近的大量的高维数据在科学,工程和社会的爆炸给许多领域比如图片,视频,多媒体处理,关联网数据分析,搜索,生物医学成像和生物信息学带来了挑战和机遇.在这样的应用领域中,都需
3、要解决极高维以及广泛条件下矩阵的低秩和稀疏分解问题,本文主要是去解决这些问题.2、理论性研究PCA 在今天已经证明是在数据分析与降维方面具有广泛应用的统计工具.然而,剧烈毁坏的观察值的脆弱性经常使他们处于危险状态.一些鲁棒 PCA 的方法在几十年前就被提议和开发了.那些代表性的方法包括影响函数法,多元切尾法和随机抽样法,交替最小化法.但是,没有一种方法提出关于广泛的条件下强保证的多项式时间算法.我们研究的这个问题可以被认为是鲁棒 PCA 的理想化版本.此外,这个问题已经被 Chandrasekaran 以及其他人研究着.他们以公式化为基础,因此结果会有一些不同的性质.问题的解决：假设给定一个数
4、据大型 矩阵,它是低秩成分和稀疏成分的叠加,即M.这里 的是低秩矩阵, 是稀疏矩阵.所有成分的大小任意,以及0SLM00S的低维行空间与列空间,维数, 的非零项的位置和个数都是未知的.0对于这种棘手的问题,文章采用了凸规划来解决,即对核范数与 范数的加1l权组合进行最小化.在弱的条件下,利用低秩矩阵不稀疏这个特点,主成分追求（PCP）通过解决min1SL(1.1)subjectoM来精确的恢复低秩矩阵和稀疏矩阵.这里的 表示 矩阵的核范i)(*数, 表示 级 长向量的 范数.以及 的奇异值分解ijijM1nR1l 210nRL为 01riLUVuv这里的 是矩阵的秩, 是正的奇异值, ,rr,
5、21KruU,21K分别是矩阵的左奇异向量和右奇异向量,则参数 的关系为rvV,21K , , (1.2)1maxneUii 2*axneVii21nr这里的 ,即把 看成长向量的无穷范数,并且假设稀疏成分的ijjiM,稀疏模式被均匀随机的选择.在这些微小的假设下,PCP 方法很好的恢复了低秩成分和稀疏成分.当然低秩成分的秩不是很大,稀疏成分合理的稀疏.这篇文章中, ,211maxn,下面给出主要结果证明的关键步骤,212min定理 1.1 假设 是 的,满足(1.2)式.修正每一个 矩阵 的符号.假0Ln设 的支撑集 在所有基数为 的集中是均匀分布的,以及对于所有0Sm的 .则存在一个数值常
6、量 使得 PCP 对于 是准ji,ijijS0sgncn1确恢复的概率至少为 (超过 支撑的选择 ),即 , ,10c0S0L0S如果和 210)(log)(nLrankr2nms在这个方程中, 和 是正的常数.在普通方形矩阵中, 是 的,PCP 中取rs 0L21使得成功的概率至少为 ,如果110c和 .2120)(log)(nLrankr21ns换句话说,矩阵 的奇异值向量或者主成分合理的分布着,它能从任意和完0全未知的毁坏模式中(只要它们是随机分布的)恢复的概率接近 1.其中 的奇异0L向量不能是尖的.为了避免不明确,关于 的模型是,取任意一个矩阵,随机集0S的项设置零,这就是 矩阵.c
7、0S这篇文章的思想主要来源于矩阵完成文献的几个方面,不同的结果是它拓展了矩阵完成的结果以及参数 的问题.这里 是一个普遍值,即 ,这对于n1的生成模型完全未知的情况具有很好的意义.M定理 1.1 的证明依赖于双认证的两个临界性质.其中需要一个消去定理,解随机处理,以及双认证和高尔夫计划的双认证.为了解释本文的思想很容易适用于从欠采样的可能毁坏严重的数据中处理低秩矩阵恢复问题.给出下面的定理：定理 1.2 假设 是 的,满足(1.2)式.在所有基数 的集中是一0Ln21.0nm致分布的.简单假设,每一个观察元素都是以概率为 且独立于其他元素毁坏.则,存在一个数值常量 使得 PCP 关于 的精确恢
8、复的概率至少为cn10,也就是 , ,10cn0L0S如果, 和 .210)(log)(nrakrs在这个方程中, 和 是正的常数.在普通 方形矩阵中,PCP 关于rs 21从 毁坏元素中成功的概率至少为 ,如果1n21m10cn.20)(log)(nLrakr4.数值实验给出理论性结论之后,这篇文章执行数值实验去验证主要结果,使用的是 Lin et al. 2009a和 Yuan and Yang 2009中介绍的增广拉格朗日乘子算法.这一节首先研究了 PCP 精确地恢复各种密度误差的各种秩的矩阵的能力.降低了迭代计算成本.实验一表明了这篇文章在恢复过程中主张的内容除了在理论上成立,在实际中
9、也很实用.下一个实证调查 PCP 恢复不同秩不同稀疏误差矩阵的能力.实验更进一步证明了 的符号不是很重要,只要支撑的选择是均匀随机的就能保证恢复.使用增0S广拉格朗日乘子算法解决核范数最小化问题,如果 , 就301pFL0能被成功的恢复.紧接着,给出两个真实数据的例子,一个是视频监控的背景模型,一个是去除阴影和人脸图像的反光.在视频监控背景模型中,把背景变化当成低秩模型.而前景目标,一般只占用小部分图像的像素,因此视为稀疏错误.举这个例子并不是要设计一个完整的视觉监视系统而是证明这篇文章的理论与方法的潜在的现实实用性.应当注意真实数据的迭代次数明显高于仿真数据次数,原因可能是真实数据的结构稍微
10、偏离了理想的低秩和稀疏模型.但是实际应用提供的额外信息很重要,可以轻易的与更精确的信号模型合并,以至于获得更高效和精确地解决方案.人脸识别问题,因为面部既不是完全凸也不是郎伯特型,而且人脸图形经常违反低秩模型,错误量极大.但是 PCP 消除这些误差的可能性还是很大.实验证实不仅能在理论中保证低计算成本,而且对于实际图像来说也很实用.5.主要算法对于 PCP 问题 ,可以使用内点法 ,内点法的有限伸缩性催生了迭代阈值的一个一阶算法,这个算法的收敛性又通过使用 Nesterov 等人的非光滑化最小化的最优一阶算法大大改善.基于矩阵完成问题开发了一个近端加速梯度法（APG）,这个算法继承了这类问题的
11、最优收敛速率.在这篇文章中使用的却是增广拉格朗日乘子算法（ALM）.根据经验,ALM 比 APG 的精确度更高,迭代次数更少.在整个优化过程中,迭代的秩总是限制在 范围内,这是 APG 没有的.而交替方向0Lrank法是更一般的增广拉格朗日乘子法的一个特殊情况.ALM 算法算法流程：ALM 算法一般用于解决：minf(X),subject to h(X) = 0,这类约束优化问题，这里的 f : 和 h : .nRnmR然后定义拉格朗日函数为： 2(,),FLXYfYX这里的 Y 是拉格朗日乘子，用于去除等式约束. 是正定标量.6.结束语这篇文章表明,人们可以在广泛的条件下通过凸规划来分解低秩和稀疏成分.更进一步,矩阵完成于矩阵恢复有着密切的关系.本篇甚至推广到了那种既有完整又有毁坏的元素的情况中（即定理 1.2）.目前的研究受限于完全低秩的低秩成分,稀疏成分被完全稀疏.这篇文章对以后工作的意义是开发具有更好伸缩性的算法,可以很容易的实现与分布的计算基础设施平行.
