Robust Principal Component Analysis.doc

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