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