本人入门小白一个，如有翻译的不正确的地方，欢迎大神们指正哈。

1 引言

1.1 想法的来源

假设我们有一个大的数据矩阵
$M$
，并且知道它可以被分解为

$M=L_{0}+S_{0}$
，

其中，
$L_{0}$
是低秩的，
$S_{0}$
是稀疏的，这两个分量的大小是任意的。我们不知道
$L_{0}$
的低维列空间和行空间，甚至不知道它们的维数。同样地，我们也不知道
$S_{0}$
中非零元素的位置，甚至不知道有多少个非零元素。我们有希望准确地(甚至精确地)和有效地恢复低秩和稀疏分量吗?

对于上述问题，一个可证明正确和可扩展的解可能会对当今数据密集型的科学发现产生影响。近年来，科学、工程和社会领域中大量高维数据的激增，给图像、视频、多媒体处理、web相关性数据分析、搜索、生物医学成像和生物信息学等领域带来了机遇，也带来了挑战。在这样的应用领域中，数据通常存在于数千甚至数十亿个维度中，其中一些样本有时具有相同的数量级。

为了减轻维度和数据量带来的影响（要么是随着维数的增加而急剧增加的算法的复杂性，要么是指随着维数的增加而急剧下降的算法的性能），我们必须利用 “

这些数据具有较低的内在维度

” 这样一个事实，例如它们位于某个低维子空间上，在某个基底上是稀疏的，或者位于某个低维manifold上(manifold：多支管、有多种分支或形式的物体)。也许最简单和最有用的假设是，数据都位于某个低维子空间附近。更准确地说，这意味着如果我们将所有数据点作为矩阵
$M$
的列向量进行叠加，那么这个矩阵应该是(近似地)低秩的：数学上

$M=L_{0}+N_{0}$
，

其中，
$L_{0}$
是低秩的，
$N_{0}$
是一个小的扰动矩阵。经典的主成分分析法通过求解下式来寻求
$L_{0}$
(在
$\l ^{2}$
意义上)的最佳rank-k估计：

$\textup{min} \left \| M-L \right \|\, \, \, \, \, \, \textup{subject to}\, \, \, \, \,\textup{rank}\left ( L \right )\leq k$

（在整篇论文中，
$\left \| M \right \|$
表示的是
$M$
的2-范数，也就是
$M$
的最大奇异值。）

通过奇异值分解(SVD)可以有效地求出它的解，并且当噪声
$N_{0}$
较小，是独立同分布的高斯随机变量时具有许多最优解。

Robust PCA

：PCA可以说是目前应用最广泛的数据分析和降维的统计学工具。然而实际应用中，当数据错误或者缺失时，PCA不能很好的抓住数据的真实子空间结构，因此效果比较差，特别是错误或缺失较大时，效果更差。不幸的是，在图像处理、web数据分析和生物信息学等现代应用程序中，严重的数据缺失无处不在，其中一些测量数据可能会被任意破坏(由于闭塞、恶意篡改或传感器故障)，或者与我们试图识别的低维结构完全无关。在过去几十年的文献中，已经探索并提出了一些自然的方法来改进PCA。代表性的方法有影响函数法、多元修剪法、交替极小化法和随机抽样法。不幸的是，这些现有的方法都不能生成在广泛条件下具有强大性能保证的多项式-时间算法（随机抽样方法保证了近似最优估计，但其复杂度在矩阵
$L_{0}$
的秩上呈指数级增长。裁剪算法的计算复杂度相对较低，但只能保证局部最优解）。

我们在这里考虑的新问题可以被认为是Robust PCA的一个理想化版本，我们的目标是从一个被严重破坏的数据矩阵
$M=L_{0}+S_{0}$
中恢复出低秩矩阵
$L_{0}$
。

与经典PCA中的小噪声项
$N_{0}$
不同，
$S_{0}$
中的元素可以具有任意大的量级，并且假设它们的support是稀疏但未知的（误差的未知support使得问题比最近研究较多的矩阵补全问题更加困难）。

应用

：在许多重要的应用中，研究中的数据可以自然地建模为低秩分量与稀疏分量的和。我们的模型适用于所有寻找鲁棒主成分的统计应用。下面，我们给出了一些受当代计算机科学挑战启发的例子，并注意到根据应用示例的不同，低秩分量或稀疏分量都可能是我们感兴趣的对象：

视频监控

：给定一系列监控视频画面，我们通常需要从背景中识别出突出的活动。如果我们将视频帧叠加为矩阵
$M$
的列，那么低秩分量
$L_{0}$
自然对应于静止背景，而稀疏分量
$S_{0}$
则对应于前景中的运动对象。然而，每个图像帧有成千上万的像素，每个视频片段包含成百上千的帧。以这种方式分解
$M$
是不可能的，除非我们有一个真正可伸缩的解决方案来解决这个问题。在第4节中，我们将展示我们的视频分解算法的结果。
人脸识别

：众所周知，在不同光照条件下的凸兰伯曲面(a convex, Lambertian surface)的图像跨越了一个低维子空间。这一事实是解释为什么低维模型对图像数据最有效的主要原因。特别是，人脸的图像可以用低维子空间很好地近似。能够正确地检索这个子空间在人脸识别和对齐等许多应用中是至关重要的。然而，逼真的人脸图像往往会受到自阴影、反射或亮度饱和的影响，这使得识别非常困难，从而影响了识别性能。在第4节中，我们将展示我们的方法如何能够有效地去除人脸图像中的此类影响。
潜在语义索引

：Web搜索引擎经常需要分析和索引大量文档的内容。一种流行的方案是潜在语义索引(LSI)。基本思想是收集文档-关键词矩阵
$M$
，
$M$
中的元素通常是关键词与文档之间相关性的编码，如文档中出现的频率(例如TF/IDF)。传统上，PCA(或SVD)用于将矩阵分解为低秩分量与残差的和，其中的残差项并不一定是(我们希望的)稀疏的。如果我们能够将
$M$
分解为低秩分量
$L_{0}$
和稀疏分量
$S_{0}$
的和，那么
$L_{0}$
就可以捕获所有文档中使用的通用单词，而
$S_{0}$
则捕获少数几个最能将每个文档与其他文档区分开来的关键字。
排名和协同滤波

：在在线商务和广告中，预测用户口味的问题越来越重要。现在，公司通常会收集各种产品的用户排名，例如电影、书籍、游戏或网络工具，其中最著名的是Netflix的电影排名。问题是使用用户对某些产品提供的不完整的排名来预测任何给定用户对任何产品的偏好。这个问题通常被转换为低秩矩阵解决问题。然而，由于数据收集过程通常缺乏控制，或者有时甚至是特别的，所以可用排名的一小部分可能是嘈杂的，甚至是被篡改的。这个问题更具挑战性，因为我们需要同时完成矩阵和纠正错误。也就是说，我们需要从一组不完整且已损坏的项中推断出一个低秩矩阵
$L_{0}$
。在第1.6节中，我们将看到我们的结果如何可以扩展到这种情况。

类似的问题也出现在许多其他应用中，如图形模型学习、线性系统识别和光学系统中的相干分解，如[12]中所讨论的。

综上所述，我们上面所列的新应用要求解决特高维矩阵在更广的条件下的低秩稀疏分解问题，这也是本文的目标。

1.2 一个令人惊讶的消息

乍一看，

分解问题

似乎无法解决，因为
$L_{0}$
和
$S_{0}$
要推断的未知数的数量是
$M\in \mathbb{R}^{n_{1}\times n_{2}}$
中给定测量值的两倍。此外，我们期望可靠地获得低秩矩阵
$L_{0}$
，但
$S_{0}$
的误差是任意大的，这似乎更令人气馁。

在本文中，我们将会非常惊奇地看到，这个问题不仅可以被解决，而且

可以通过可处理的凸优化来解决

。

让
$\left \| M \right \|_{\ast } :=\sum _{i}\sigma _{i}\left ( M \right )$
表示矩阵
$M$
的核范数（
$M$
的奇异值的和），

让
$\left \| M \right \|_{1}=\sum _{ij}\left | M_{ij} \right |$
表示矩阵
$M$
的
$l_{1}$
-范数，在
$\mathbb{R}^{n_{1}\times n_{2}}$
中被看作是一个长向量。

然后我们会证明

在弱假设下，解式(1.1)时，主成分追踪(PCP)估计精确地恢复了低秩分量
$L_{0}$
和稀疏分量
$S_{0}$

（虽然这个名称很自然地暗示了对低秩分量恢复的强调，但我们重申，在某些应用示例中，稀疏分量确实是我们感兴趣的对象。）。

$\textup{min} \left \| L \right \|_{\ast }+\lambda \left \| S \right \|_{1} \, \,\, \, \, \, \, \textup{subject to} \, \, \: \, L+S=M\, \, \, \, \, \, \, \, \, \,\, \, (1.1)$

从理论上讲，即使
$L_{0}$
的秩在矩阵的维数上几乎是线性增长的，也是可以保证上式成立的，并且
$S_{0}$
中的误差小于所有元素的一个常数比例。在算法上，

我们将看到上述问题可以通过高效和可伸缩的算法来解决，其代价并不比经典的PCA高多少。

从经验上讲，我们的模拟和实验表明，这种方法适用于各种类型的真实数据。在第1.5节中，我们将对在准备本文过程中发布的论文[12]中所采用的类似方法进行评论。

1.3 什么时候分解才有意义?

正常的反应是，这篇论文的目标无法实现。事实上，似乎没有足够的信息来完美地分离低秩和稀疏分量。事实上，这是有一定道理的，因为这显然是一个可识别性的问题。例如，假设矩阵
$M$
等于
$e_{1}e_{1}^{\ast }$
(这个矩阵左上角有一个1，其他地方都是0)。那么矩阵
$M$
既是稀疏的又是低秩的，我们如何判断它是低秩的还是稀疏的呢？为了使问题有意义，我们需要

使低秩分量
$L_{0}$
不是稀疏的

。在本文中，我们将借用在[8]中引入的

矩阵补全问题的非相干性的一般概念

；这是一个关于低秩分量的奇异向量的假设。
$L_{0}$
的奇异值分解记为

$L_{0}=U\Sigma V^{\ast }=\sum _{i=1}^{r}\sigma _{i} u_{i} v_{i}^{\ast }$
，

其中，
$r$
是矩阵的秩，
$\sigma _{1},\cdots, \sigma _{r}$
表示正奇异值，
$U=\left [ u_{1},\cdots ,u_{r} \right ]$
和
$V=\left [ v_{1},\cdots ,v_{r} \right ]$
分别是左奇异向量和右奇异向量组成的矩阵。带有参数
$\mu$
的非相干条件写为：

$\textup{max}_{i}\left \| U^{\ast }e_{i} \right \|^{2}\leq\frac{\mu r}{n_{1}},\: \: \: \: \: \: \textup{max}_{i}\left \| V^{\ast }e_{i} \right \|^{2}\leq\frac{\mu r}{n_{2}},\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: (1.2)$

和
$\left \| UV^{\ast } \right \|_{\infty }\leq \sqrt{\frac{\mu r}{n_{1}n_{2}}}.\: \: \: \: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: (1.3)$

在整篇文章中，
$\left \| M \right \|_{\infty }=max_{ij}\left | M_{ij} \right |$
，即矩阵
$M$
的
$l_{\infty }$
-范数被看作是一个长向量。注意，由于在
$U$
的列空间上的正交投影
$P_{U}$
是由
$P_{U}=UU^{\ast }$
给出的，(1.2)等价于
$max_{i}\left \| P_{U}e_{i} \right \|^{2}\leq \frac{\mu r}{n_{1}}$
，
$P_{V}$
也是一样。正如前面的文献[8,10,22]所讨论的，

非相干条件表明对于小的值，奇异向量

是合理分布的，换句话说，

不是稀疏的

。

如果稀疏矩阵的秩较低，就会出现另一个可识别性问题

。如果
$S$
的所有非零项都出现在一列或几列中，就会出现这种情况。例如，假设
$S_{0}$
的第一列与
$L_{0}$
相反，并且
$S_{0}$
的所有其他列都消失了。那么很明显，我们不能用任何方法来恢复
$L_{0}$
和
$S_{0}$
，因为
$M=L_{0}+S_{0}$
会有一个列空间等于
$L_{0}$
，或者包含在
$L_{0}$
的列空间中。

为了避免这种无意义的情况，我们假设稀疏分量的稀疏模式是随机均匀选择的。

1.4 主要结果

令人惊讶的是，在这些最小限度的假设下，简单的PCP解能够完美地恢复低秩和稀疏分量，当然前提是低秩分量的秩不是太大，并且稀疏分量是合理稀疏的。下面，
$n_{(1)}=\textup{max}(n_{1},n_{2})$
，
$n_{(2)}=\textup{min}(n_{1},n_{2})$
。

定理1.1

：假设
$L_{0}$
的大小是
$n\times n$
的，满足 (1.2) 和 (1.3)，
$S_{0}$
的support set均匀分布于所有基数为
$m$
的集合中（support set是非零元素的位置索引）。如果

$\textup{rank}\left ( L_{0} \right )\leq \rho _{r}n\mu ^{-1}\left ( \textup{log}\: n \right )^{-2}\: \: \: \: \: \: \: \: \textup{and}\: \: \: \: \: \: \: \: m\leq \rho _{s}n^{2},\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 1.4 \right )$

那么有一个数值常数
$c$
，至少有
$1-cn^{-10}$
的概率（在选择
$S_{0}$
的support上），使得
$\lambda = \frac{1}{\sqrt{n}}$
时，PCP(1.1)是精确的，即
$\widehat{L}=L_{0}$
和
$\widehat{S}=S_{0}$
。（原文是：Then there is a numerical constant
$c$
such that with probability at least
$1-cn^{-10}$
(over the choice of support of
$S_{0}$
), Principal Component Pursuit (1.1) with
$\lambda = \frac{1}{\sqrt{n}}$
is exact,

i.e.

$\widehat{L}=L_{0}$
and
$\widehat{S}=S_{0}$
, provided that (1.4). ）其中，
$\rho_{r}$
和
$\rho _{s}$
是正常数。一般情况下，
$L_{0}$
的大小是
$n_{1}\times n_{2}$
，
$\lambda = \frac{1}{\sqrt{n_{\left ( 1 \right )}}}$
时，PCP成功的概率至少为
$1-cn_{(1)}^{-10}$
的条件是
$\textup{rank}(L_{0})\leq \rho _{r}n_{(2)}\mu ^{-1}\left ( \textup{log}\: n_{(1)} \right )^{-2}$
和
$m\leq \rho _{s}n_{1}n_{2}$
。

换句话说，如果矩阵
$L_{0}$
的奇异向量或主成分分布合理，则可以从任意且完全未知的破坏模式中以接近1的概率恢复矩阵
$L_{0}$
（只要这些模式是随机分布的）。事实上，这适用于秩比较大的情况，即当
$\mu$
不太大时的
$\frac{n}{\left ( \textup{log }n \right )^{2}}$
阶。我们想强调，在我们的假设中，唯一的“随机性”与
$S _{0}$
的非零元素的位置有关，其他的一切都是确定的。特别地，我们对
$L _{0}$
的要求是它的奇异向量不是尖峰的。同样，我们没有对
$S _{0}$
的非零分量的大小和符号做任何假设。为了避免歧义，我们的
$S _{0}$
模型是这样的：取一个任意矩阵
$S$
并将其在随机集
$\Omega ^{c}$
上的元素设为零；进而得到
$S _{0}$
。

一个相当值得注意的事实是，我们的算法中没有需要调的参数。在定理的假设下，最小化
$\left \| L \right \|_{\ast }+\frac{1}{\sqrt{n_{\left ( 1 \right )}}}\left \| S\right \|_{1 }$
总是会返回正确的答案，其中
$n _{(1)}=\textup{max}\left ( n_{1},n_{2} \right )$
。这是令人惊讶的，因为人们可能期望必须选择正确的尺度
$\lambda$
来适当地平衡
$\left \| L \right \|_{\ast }+\lambda \left \| S\right \|_{1 }$
中的两个项（可能取决于它们的相对大小）。然而，情况显然并非如此。从这个意义上说，选择
$\lambda = \frac{1}{\sqrt{n_{\left ( 1 \right )}}}$
是普遍的。此外，还不清楚为什么无论
$L _{0}$
和
$S _{0}$
是什么，
$\lambda = \frac{1}{\sqrt{n_{\left ( 1 \right )}}}$
都是正确的选择。数学分析揭示了这个值的正确性。事实上，定理的证明给出了一个完整的正确值范围，我们在这个范围内选择了一个足够简单的值。另一种意见是，可以获得成功概率更大的结果，即
$\beta >0$
时的形式
$1-O\left ( n^{-\beta } \right ) \: \textup{or} \: 1-O\left ( n_{(1)}^{-\beta } \right )$
，但代价是降低
$\rho _{r}$
的值。

1.5 与先前工作的联系和创新

在过去的一两年里，有关[8]中引入的矩阵补全问题的研究得到了快速发展，参见[7,10,22,23,43]及其参考文献。简而言之，矩阵补全问题就是从一个低秩矩阵的一小部分项中恢复一个低秩矩阵，进而从一个小的线性泛函中恢复一个低秩矩阵。虽然已有其他方法提出[43]，但选择的方法是采用凸优化[7,10,22,23,45]：在所有与数据一致的矩阵中，只需找到核范数最小的矩阵。上面引用的文献都证明了这种方法的数学有效性，我们的数学分析借鉴了这些文献，特别是那些在[8]中率先提出的文献。我们的方法也很大程度上依赖于David Gross在量子态x射线断层摄影术背景下介绍的强大的思想和优雅的技术[22,23]。特别地，聪明的高尔夫方案[22]在我们的分析中起着至关重要的作用，我们引入了对该方案的两个新的修改。

尽管有这些相似之处，我们的想法在几个方面与矩阵补全的文献也有不同之处。

首先，

我们的结果显然是不同性质的。

其次，

我们可以把分离问题，以及低阶分量的恢复，看作是一个矩阵补全问题。事实上，我们没有一小部分观察到的条目可用，而另一部分丢失了，我们有一小部分可用，但不知道是哪一个，而另一个没有丢失，但完全损坏了。虽然，这是一个比较困难的问题，但是我们的算法的一个想法是，它同时检测损坏的条目，并将低秩分量完美地匹配到被认为可靠的其余条目。在这个意义上，我们的方法和结果超出了矩阵补全。

第三

，我们引入了一个新的反随机参数，它允许我们修正稀疏分量的非零项的符号。我们相信这项技术会有许多应用。其中一个应用是在压缩感知领域，对于信号的符号的随机性的假设是很常见的，而且仅仅是出于方便而不是需要;这一点很重要，因为假设独立的信号符号对于许多实际应用可能没有多大意义，因为所涉及的信号可能都是非负的(例如图像)。

我们在前面提到了相关的工作[12]，它也考虑了将一个给定的数据矩阵分解成稀疏和低秩分量的问题，并给出了凸规划成功的充分条件。这些条件是用两个量来表示的。第一个是
$l _{\infty }-$
范数与算子范数之间的最大比值，限制在其行或列空间与
$L _{0}$
的行或列空间一致的矩阵生成的子空间内。第二个是算子范数和
$l _{\infty }-$
范数之间的最大比值，限制于在
$S _{0}$
的support中消失的矩阵的子空间。Chandrasekaran等人的研究表明，当这两个量的乘积很小时，在正则化参数的一定区间内恢复是准确的。

这个条件的一个非常吸引人的方面是它是完全确定的：它不依赖于
$L _{0}$
或
$S _{0}$
的任何随机模型。它产生了一个很容易与我们的结果相比较的推论：为了简单起见，假设
$n _{1}=n _{2}=n$
，并且让
$\mu _{0}$
表示满足(1.2)的最小量，那么当
$\textup{max} _{j} \left \{ i:\left [ S_{0} \right ]_{ij} \neq 0 \right \}\times \sqrt{\frac{\mu _{0}r}{n} }< \frac{1}{12}$
时，就会得到正确的恢复。式子左边是至少和
$\rho _{s}\sqrt{\mu _{0}nr}$
一样大，其中
$\rho _{s}$
是
$S _{0}$
的非零项的分数。由于
$\mu _{0}\geq 1$
始终成立，因此该语句仅保证当
$\rho _{s}=O\left ( \left ( nr \right )^{-0.5} \right )$
时的恢复；即，即使
$\textup{rank}\left ( L_{0} \right )=O\left ( 1 \right )$
，
$S _{0}$
中元素的消失分数也只能为非零。

相比之下，我们的结果表明，对于非相干
$L _{0}$
，
$\textup{rank}\left ( L_{0} \right )$
在
$\frac{n}{\mu \textup{log}^{2}n}$
的阶数和
$S _{0}$
中的一些非零项在
$n ^{2}$
的阶数上都有很高的概率发生正确恢复。也就是说，秩比较大的矩阵可以从稀疏误差的非消失分数中恢复出来。这种改进是以引入一种随机性为代价的：错误support的统一模型（注意，[12]的边界只依赖于对
$S _{0}$
的支持，因此可以解释为关于
$S _{0}$
符号的最坏情况。相比之下，我们的结果并没有对符号进行随机化，而是假定它们是从固定的符号模式中采样的。虽然由于空间的限制，我们不在这里继续研究，但我们的分析也得到了一个结果，它适用于最坏情况下的符号模式，并且保证了
$\textup{rank}\left ( L_{0} \right )=O\left ( 1 \right )$
的正确恢复，并且对于一些
$\rho >0$
，基数
$\rho n_{1}n_{2}$
的稀疏模式是正确的）。

我们的分析还有一个额外的优点，这一点具有重要的实际意义：它确定了正则化参数
$\lambda$
的一个简单的、非自适应的选择。相比之下，Chandrasekaran等人给出的正则化参数的条件依赖于实际中未知的量。[12]的实验部分建议通过求解多个凸规划来寻找正确的
$\lambda$
。另一方面，我们的结果表明，简单的选择
$\lambda = \frac{1}{\sqrt{n}}$
对于恢复任何平方非相干矩阵具有很高的概率。

1.6 严重损坏的数据对矩阵补全的影响

我们已经看到，我们的主要结果表明可以恢复低秩矩阵，即使它的元素中有很大一部分已损坏。然而，在某些应用程序中，某些元素可能也会丢失，本节将讨论这种情况。设
$P_{\Omega }$
是
$\Omega \subset \left [ n _{1} \right ]\times \left [ n_{2} \right ]$
support上的矩阵在线性空间上的正交投影，

$P_{\Omega } = \left\{\begin{matrix} X_{ij},\: \: \left ( i,j \right )\in \Omega \\ 0,\: \: \: \: \: \: \left ( i,j \right )\notin \Omega \end{matrix}\right.$

然后假设我们只有
$L_{0}+S_{0}$
的几个元素，方便起见，我们写成
$Y= P_{\Omega _{\textup{obs}}}\left ( L_{0}+S_{0} \right )=P_{\Omega _{\textup{obs}}} L_{0}+S_{0}^{'}$
；

也就是说，我们只看到
$\left ( i,j \right )\in \Omega _{\textup{obs}}\subset \left [ n_{1} \right ]\times \left [ n_{2} \right ]$
的这些元素。这个模型模拟了以下问题：我们希望恢复
$L_{0}$
，但是只看到关于
$L_{0}$
的小部分元素，其中有一部分碰巧被损坏，当然我们不知道是哪些元素。很容易看出，这是矩阵补全问题的一个重要扩展，它寻求从欠采样但在其他方面完美的数据
$P_{\Omega _{\textup{obs}}} L_{0}$
中恢复
$L_{0}$
。

我们提出通过解决以下问题来恢复
$L_{0}$
：

$\textup{min}\left \| L \right \|_{\ast }+\lambda \left \| S \right \|_{1}\: \: \: \: \: \: \: \textup{s.t.}\: \: \: P_{\Omega_{\textup{obs}} }\left ( L+S \right )=Y\: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 1.5 \right )$

也就是说，在所有与可用数据匹配的分解中，PCP 找到了核范数和
$l_{1}-$
范数的加权组合最小化的分解。我们观察到，在某些条件下，这种简单的方法可以准确地恢复低阶分量。事实上，本文开发的技术证明了这一结果：

定理1.2：

假设
$L_{0}$
的大小是
$n\times n$
的，满足 (1.2) 和 (1.3)，且
$\Omega _{\textup{obs}}$
在服从
$m = 0.1n^{2}$
的所有基数
$m$
集合中均匀分布。为简单起见，假设每个观察到的条目被破坏的概率都是
$\tau$
，且各个条目之间是否被损坏是相互独立的。如果

$\textup{rank}\left ( L_{0} \right )\leq \rho _{r}n\mu ^{-1}\left ( \textup{log}\: n \right )^{-2}\: \: \: \: \: \: \: \: \textup{and}\: \: \: \: \: \: \: \: \tau \leq \tau _{s}\: ,\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 1.6 \right )$

那么，有一个数值常数
$c$
，至少有
$1-cn^{-10}$
的概率，使得
$\lambda = \frac{1}{\sqrt{0.1n}}$
时，PCP(1.1)是精确的，即
$\widehat{L}=L_{0}$
。（原文是：Then there is a numerical constant
$c$
such that with probability at least
$1-cn^{-10}$
, Principal Component Pursuit (1.5) with
$\lambda = \frac{1}{\sqrt{0.1n}}$
is exact,

i.e.

$\widehat{L}=L_{0}$
, provided that (1.6). ）其中，
$\rho_{r}$
和
$\tau _{s}$
是正常数。一般情况下，
$L_{0}$
的大小是
$n_{1}\times n_{2}$
，
$\lambda = \frac{1}{\sqrt{0.1n_{\left ( 1 \right )}}}$
时，PCP在
$m = 0.1n_{1}n_{2}$
条目损坏的情况下成功的概率至少为
$1-cn_{(1)}^{-10}$
的条件是
$\textup{rank}(L_{0})\leq \rho _{r}n_{(2)}\mu ^{-1}\left ( \textup{log}\: n_{(1)} \right )^{-2}$
。

简而言之，通过凸优化可以从不完整和损坏的条目中完全恢复。

一方面，这个结果以如下方式扩展了我们先前的结果。如果所有条目都可用，即
$m = n_{1}n_{2}$
，则这是定理1.1。另一方面，它扩展了矩阵补全的结果。实际上，如果
$\tau =0$
，这是一个纯正的矩阵补全问题，它来自于总条目数的一小部分，并且只要
$r$
服从（1.6），我们的定理就保证了完全恢复，对于较大的
$r$
值，它与可用的最强结果相匹配。我们注意到，恢复是准确的，但是用的是另一种算法。可以肯定的是，在矩阵补全中，典型的例子是在约束
$P_{\Omega _{\textup{obs}}}L=P_{\Omega _{\textup{obs}}}L_{0}$
下最小化核范数
$\left \| L \right \|_{\ast }$
。这里，我们要求解的是

$\textup{min}\left \| L \right \|_{\ast }+\lambda \left \| S \right \|_{1}\: \: \: \: \: \: \: \textup{s.t.}\: \: \: P_{\Omega_{\textup{obs}} }\left ( L+S \right ) = P_{\Omega_{\textup{obs}} }L_{0}\:, \: \: \: \: \: \: \: \: \: \: \: \: \left ( 1.7 \right )$

并返回
$\hat{L}=L_{0}$
，
$\hat{S}=0$
！在这种情况下，定理1.2证明了矩阵补全相对于总误差是稳定的。

注意：

我们提出定理1.2仅仅是为了解释我们的思想如何从欠采样和可能严重损坏的数据中较容易地适应处理低阶矩阵恢复问题。在我们的陈述中，我们选择了看到10%的条目，但是，自然地，类似的结果适用于所有其他正分数，只要它们足够大。我们想说明的是，一个更仔细的研究可能会导致定理1.2的一个更强的版本。特别是，对于非常低阶矩阵，我们期望看到类似的结果，其观测值要少得多；也就是说，在大矩阵的极限下，从条目的减少部分得到的结果。事实上，我们的技术已经建立了如此清晰的结果，但我们现在不想停留在这样的改进上，而把这留给以后的工作。

1.7 符号

我们提供了整个论文中使用的符号的简要总结。我们将使用矩阵的五个范数。

（1）
$\left \| X \right \|$
：算子范数或 2-范数

（2）
$\left \| X \right \|_{F}$
：F-范数

（3）
$\left \| X \right \|_{\ast }$
：核范数

（4）
$\left \| X \right \|_{1}$
：
$l_{1}$
范数

（5）
$\left \| X \right \|_{\infty }$
：
$l_{\infty }$
范数

前三个是奇异值的函数，后两个被看作是长矢量（seen as a long vector）。两个矩阵之间的欧氏内积由公式
$\left \langle X,Y \right \rangle:=\textup{trace}\left ( X\ast Y \right )$
定义，因此，
$\left \| X \right \|_{F }^{2}=\left \langle X,X \right \rangle$
。

此外，我们还会对作用于矩阵空间的线性变换进行巧妙的处理；会对如
$\emph{P}_{\Omega }X$
中的操作符采用花体字母表示；一个字母多个意义：
$\Omega$
也可以表示为 support set在
$\Omega$
上的矩阵的线性空间；
$\emph{P}_{\Omega ^{\perp }}$
表示 support set 在
$\Omega ^{c}$
上的矩阵空间上的投影，因此
$\emph{I}=\emph{P}_{\Omega }+\emph{P}_{\Omega^{\perp } }$
，
$\emph{I}$
是identity operator(恒等算子;恒等运算符;单位算子;识别算子)；我们将考虑这些的一个范数，即由
$\left \| A \right \|$
表示的算子范数(上面的奇异值)，我们可以把它看作是
$\left \| A \right \|=\textup{sup}_{\left \{ \left \| X \right \|_{F}=1 \right \}}\left \| \emph{A}X \right \|_{F}$
，例如，无论
$\Omega \neq \not{0}$
，
$\left \| \emph{P}_{\Omega } \right \|=1$
。

1.8 本文结构

论文的结构如下。在第二节中，我们给出了证明定理1.1的关键步骤。此证明取决于双重证书的两个关键属性，这在单独的第3节中建立。之所以分开阅读，是因为在第一次阅读中，读者可能想跳到第4节，该节介绍了视频监控和计算机视觉的应用程序。第五节介绍了当
$M$
是非常大的规模时，求PCP解的算法思想。在第六节中，我们对未来的研究方向进行了讨论。最后，定理1.2的证明和中间结果一起在附录第7节中。

2 证明

本节介绍证明我们主要结果的关键步骤，定理1.1。为了简单起见，我们将证明平方矩阵的结果，并让
$n=n_{1}=n_{2}$
。当然，我们将指出在什么地方需要修改论点来处理一般情况。在开始之前，回顾一些基本概念并引入贯穿整个应使用的附加符号是很有帮助的。对于给定的标量
$x$
，我们用
$\textup{sgn}\left ( x \right )$
表示
$x$
的符号，当
$x=0$
时，我们取
$\textup{sgn}\left ( x \right )=0$
。引申而言，
$\textup{sgn}\left ( S \right )$
是一个矩阵，它的元素对应于
$S$
中各元素的符号。我们记得support set在
$\Omega$
上的
$S_{0}$
的
$l_{1}$
范数的任意子梯度，都是
$\textup{sgn}\left ( S_{0} \right )+F$
的形式，其中，
$\emph{P}_{\Omega }F=0$
(
$F$
vanishes on
$\Omega$
)，
$\left \| F \right \|_{\infty } \leq 1$
。

我们还将处理核规范的一组次梯度。从现在开始，我们假设秩为
$r$
的
$L_{0}$
具有奇异值分解
$U\Sigma V^{\ast }$
，其中，
$U,V\in \mathbb{R}^{n\times r}$
(如1.3节所述) 。那么核范数在
$L_{0}$
处的任何次梯度都是
$UV^{\ast }+W$
的形式，其中，
$U^{\ast }W=0,\: WV=0,\: \left \| W \right \|\leq 1$
。用
$T$
表示矩阵的线性空间：

$T:=\left \{ UX^{\ast }+YV^{\ast },\: X,Y\in \mathbb{R}^{n\times r} \right \}\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 2.1 \right )$

用
$T^{\perp }$
表示它的正交补。不难看出，把
$U^{\ast }W=0$
和
$WV=0$
结合起来，就等于
$\emph{P}_{T}W=0$
，其中，
$\emph{P}_{T}$
是在
$T$
上的正交投影。另一种说法是
$\emph{P}_{T^{\perp }}W=W$
。顺便说一下，注意对于任何矩阵
$M$
，
$\emph{P}_{T^{\perp }}M=\left ( I-UU^{\ast } \right )M\left ( I-VV^{\ast } \right )$
，我们认识到
$\left ( I-UU^{\ast } \right )$
是
$U$
的列所跨越的线性空间的正交补集上的投影，对于
$\left ( I-VV^{\ast } \right )$
也是这样。这个简单观察的结果是：对于任何矩阵
$M$
，
$\left \| \emph{P}_{T^{\perp }}M \right \|\leq \left \| M \right \|$
，我们接下来将多次使用这个事实。另一个结果是：对于任意
$e_{i}e_{j}^{\ast }$
形式的矩阵，

$\left \| \emph{P}_{T^{\perp }} e_{i}e_{j}^{\ast } \right \|_{F}^{2}=\left \| \left ( I-UU^{\ast } \right )e_{i} \right \|^{2}\left \| \left ( I-VV^{\ast } \right )e_{j} \right \|^{2}\geq \left ( 1-\frac{ur}{n} \right )^{2}$

其中，我们假定
$\frac{ur}{n} \leq 1$
。因为
$\left \| \emph{P}_{T} e_{i}e_{j}^{\ast } \right \|_{F}^{2}+=\left \| \emph{P}_{T^{\perp }} e_{i}e_{j}^{\ast } \right \|_{F}^{2}=1$
，这就得到

$\left \| \emph{P}_{T} e_{i}e_{j}^{\ast } \right \|_{F}\leq \sqrt{\frac{2\mu r}{n}}\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \left ( 2.2 \right )$

对于矩形矩阵，这个估计变为
$\left \| \emph{P}_{T} e_{i}e_{j}^{\ast } \right \|_{F}\leq \sqrt{\frac{2\mu r}{\textup{min}\left ( n_{1},n_{2} \right )}}$
。

最后，在后续部分中，我们将写一个事件在概率至少为
$1-O\left ( n^{-10} \right )$
的情况下以高概率或大概率成立(对于矩形矩阵，
$n_{\left ( 1 \right )}$
代替
$n$
)。

2.1 一个消除定理

我们从一个有用的定义和一个我们将使用几次的基本结果开始。

定义2.1：

如果
$\textup{supp}\left ( S' \right ) \subset \textup{supp}\left ( S \right )$
，且whenever
$S'_{ij}\neq 0$
时，
$S'_{ij}=S_{ij}$
，那么我们说
$S'$
是
$S$
的简化版本(a trimmed version)。

换句话说，通过将
$S$
的一些项设置为零，可以得到
$S$
的一个精简版本。尽管如此，下面的凭直觉得到的定理表明，如果主成分追踪正确地恢复了
$M_{0}=L_{0}+S_{0}$
的低秩和稀疏分量，那么它也能正确地恢复一个矩阵
$M'_{0}=L_{0}+S'_{0}$
的分量，其中
$S'_{0}$
是
$S_{0}$
的一个简化版本。这是很直观的，因为问题在某种程度上更简单，因为可以恢复的东西很少。

定理2.2：

假设输入数据为
$M_{0}=L_{0}+S_{0}$
时的(1.1)的解是唯一且精确的，并考虑
$M'_{0}=L_{0}+S'_{0}$
，其中
$S'_{0}$
是
$S_{0}$
的一个简化版本。那么用输入
$M'_{0}$
求（1.1）的解也是精确的。

证明：

对于一些
$\Omega _{0}\subset \left [ n \right ]\times \left [ n \right ]$
，令
$S'_{0}=\emph{P}_{\Omega _{0}}S_{0}$
，且令
$\left ( \hat{L},\hat{S} \right )$
为输入
$L_{0}+S'_{0}$
时(1.1)的解。那么

$\left \| \hat{L} \right \|_{\ast }+\lambda \left \| \hat{S} \right \|_{1}\leq \left \| L_{0} \right \|_{\ast }+\lambda \left \| \emph{P}_{\Omega _{0}}S_{0} \right \|_{1}$
，

因此，
$\left \| \hat{L} \right \|_{\ast }+\lambda \left \| \hat{S} \right \|_{1}+\lambda \left \| \emph{P}_{\Omega _{0}^{\perp}}S_{0} \right \|_{1} \leq \left \| L_{0} \right \|_{\ast }+\lambda \left \| S_{0} \right \|_{1}$
。

注意，对于该问题，当输入数据为
$L_{0}+S_{0}$
时，
$\left ( \hat{L},\hat{S}+\emph{P}_{\Omega _{0}^{\perp }}S_{0} \right )$
是可行的。因为
$\left \|\hat{S}+ \emph{P}_{\Omega _{0}^{\perp }}S_{0} \right \|_{1}\leq \left \| \hat{S} \right \|_{1}+\left \| \emph{P}_{\Omega _{0}^{\perp }}S_{0} \right \|_{1}$
，我们有

$\left \| \hat{L} \right \|_{\ast }+\lambda \left \| \hat{S} + \emph{P}_{\Omega _{0}^{\perp}}S_{0} \right \|_{1} \leq \left \| L_{0} \right \|_{\ast }+\lambda \left \| S_{0} \right \|_{1}$
。

然而，右边是最优值，根据最优解的唯一性，我们必须有
$\hat{L}=L_{0}$
和
$\hat{S} + \emph{P}_{\Omega _{0}^{\perp}}S_{0}=S_{0}$
或
$\hat{S}=\emph{P}_{\Omega _{0}}S_{0}=S'_{0}$
。这就证明了定理。

伯努利方程模型

：在定理1.1中，概率是关于基数
$m$
的一致随机子集
$\Omega =\left \{ \left ( i,j \right ):S_{ij}\neq 0 \right \}$
。在实践中，使用伯努利模型
$\Omega =\left \{ \left ( i,j \right ):\delta _{ij} = 1 \right \}$
更方便一些，其中，
$\delta _{ij}\: '\textup{s}$
是独立同分布的变量，Bernoulli 取值为1的概率为
$\rho$
，取值为0的概率为
$1- \rho$
，所以
$\Omega$
的期望基数是
$\rho n^{2}$
。从现在起，
$\Omega \sim \textup{Ber}\left ( \rho \right )$
表示
$\Omega$
是从参数为
$\rho$
的伯努利模型中取样得到的。

由于根据定理2.2，算法的成功在
$\left | \Omega \right |$
中是单调的，因此，如果我们允许在
$\frac{m}{n^{2}}$
附近的
$\rho$
中出现消失位移，则证明伯努利模型的任何保证也适用于一致模型，反之亦然。这种等价性的依据是标准的，见[9,10]，完整性见附录。

2.2 去随机化

在定理1.1中，
$S_{0}$
的非零项的值是固定的。事实证明，在一个更强的假设下证明这个定理更容易，这个假设是，非零项的符号是独立的对称伯努利变量，即取值为
$\pm 1$
的概率均为 0.5(与支持集的选择无关)。下面这个便利的定理表明，对随机符号建立结果足以对固定符号声明类似的结果。

定理2.3：

假设
$L_{0}$
满足定理1.1的条件，假设
$S_{0}$
的非零项的位置遵循参数为
$2\rho _{s}$
的伯努利模型，并且
$S_{0}$
的符号
$\pm 1$
是独立同分布的（并且独立于这些位置）。如果PCP解是精确解的概率较高，那么对于

符号固定且位置是从参数为
$\rho _{s}$
的伯努利模型中采样的

模型，也至少具有相同概率的精确解。

这个定理很方便，因为为了证明我们的主要结果，我们只需要证明在稀疏分量的符号是随机的情况下它是正确的。

证明：

考虑一个符号固定的模型，在该模型中，对于一些固定矩阵
$S$
来说，把
$S_{0}$
看作
$\emph{P}_{\Omega }S$
是很便利的，其中
$\Omega$
是从参数为
$\rho _{s}$
的Bernoulli模型中采样的。因此，
$S_{0}$
包含独立成分，这些独立成分的分布为

$\left ( S_{0} \right )_{ij}= \left\{\begin{matrix} S_{ij},\: \: \: \: \: \: \: \: \textup{w.p.}\: \: \rho _{s} \\ 0,\: \: \: \: \: \: \: \: \textup{w.p.}\: \: 1- \rho _{s} \end{matrix}\right. .$

现在考虑一个具有独立同分布项的随机符号矩阵，分布为

$E_{ij}= \left\{\begin{matrix} 1,\: \: \: \: \: \: \: \: \textup{w.p.}\: \: \rho _{s} \\ 0,\: \: \: \: \: \: \: \: \textup{w.p.}\: \: 1-2 \rho _{s} \\ 1,\: \: \: \: \: \: \: \: \textup{w.p.}\: \: \rho _{s} \end{matrix}\right.$

以及一个“消除”矩阵
$\Delta$
，其中的元素定义为
$\Delta _{ij}= \left\{\begin{matrix} 0,\: \: \: \: \: \: \: \: \textup{if}\: E_{ij}\left [ \textup{sgn}\left ( S \right ) \right ] _{ij}=-1 \\ 1,\: \: \: \: \: \: \: \: \textup{otherwise} \end{matrix}\right. .$

注意，
$\Delta$
的元素是独立的，因为它们是自变量的函数。

现在考虑
$S'_{0}=\Delta \circ \left ( \left | S \right |\circ E \right )$
，其中
$\circ$
表示Hadamard积或 componentwise积，所以，
$\left [ S'_{0} \right ]_{ij}=\Delta _{ij}\left ( \left | S_{ij} \right |E_{ij} \right )$
。然后我们说
$S'_{0}$
和
$S_{0}$
具有相同的分布。要知道为什么这是真的，独立检查边缘是否匹配就足够了。对于
$S_{ij}\neq 0$
，我们有

$\mathbb{P}\left ( \left [ S'_{0} \right ]_{ij}=S_{ij} \right ) \\=\mathbb{P}\left ( \Delta _{ij}=1 \: \: \textup{and} \:\: E_{ij}=\left [ \textup{sgn}\left ( S \right ) \right ] _{ij} \right ) \\ =\mathbb{P}\left ( E_{ij}\left [ \textup{sgn}\left ( S \right ) \right ] _{ij} \neq -1\: \: \textup{and}\: \:E_{ij}=\left [ \textup{sgn}\left ( S \right ) \right ] _{ij} \right ) \\ =\mathbb{P}\left ( E_{ij}=\left [ \textup{sgn}\left ( S \right ) \right ] _{ij} \right )\\=\rho _{s}$

从而证明了我们的判断。

这个构造允许证明这个定理。事实上，
$\left | S \right |\circ E$
现在服从随机符号模型，并且通过假设，PCP以高概率恢复
$\left | S \right |\circ E$
。通过消去定理，该程序还恢复了
$S'_{0}=\Delta \circ \left (\left | S \right |\circ E \right )$
。由于
$S'_{0}$
和
$S_{0}$
具有相同的分布，the theorem follows。

2.3 双重证明

我们引入了一个简单的条件，使得
$\left ( L_{0},S_{0} \right )$
对是 PCP的唯一最优解。这些条件是用对偶向量表示的，对偶向量的存在证明了最优性。(回想一下，
$\Omega$
是一个矩阵空间，与稀疏分量
$S_{0}$
具有相同的support set，
$T$
是通过低秩分量
$L_{0}$
的列空间和行空间定义的空间(式(2.1))。)

引理2.4：

假设
$\left \| \emph{P}_{\Omega }\emph{P}_{T } \right \|<1$
，在标准符号下，如果有一对
$\left ( W,F \right )$
满足

$UV^{\ast }+W=\lambda \left ( \textup{sgn}\left ( S_{0} \right )+F \right )$
，和
$\emph{P}_{T } W=0$
，
$\left \| W \right \|<1$
，
$\emph{P}_{\Omega } F=0$
，且
$\left \| F \right \|_{\infty }<1$
，

那么
$\left ( L_{0},S_{0} \right )$
是唯一解。

注意，条件
$\left \| \emph{P}_{\Omega }\emph{P}_{T } \right \|<1$
等价于
$\Omega \cap T=\left \{ 0 \right \}$
。

证明：

我们考虑了一个可行的扰动
$\left ( L_{0}-H, L_{0}+H \right )$
，并证明了whenever
$H\neq 0$
，目标函数是增加的，从而证明
$\left ( L_{0},S_{0} \right )$
是唯一解。为了做到这一点，设
$UV^{*}+W_{0}$
是
$L_{0}$
核范数的任意次梯度，
$\textup{sgn}\left ( S_{0} \right )+F_{0}$
是
$S_{0}$
的
$l_{1}$
范数的任意次梯度。根据次梯度的定义，

$\left \| L_{0}+H \right \|_{*}+\lambda \left \| S_{0}-H \right \|_{1}\geq \left \| L_{0} \right \|_{*}+\lambda \left \| S_{0} \right \|_{1}+\left \langle UV^{*}+W_{0},H \right \rangle-\lambda \left \langle \textup{sgn}\left ( S_{0} \right )+F_{0},H \right \rangle$
。

现在选择
$W_{0}$
使
$\left \langle W_{0},H \right \rangle=\left \| \emph{P}_{T^{\perp }}H \right \|_{*}$
，选择
$F_{0}$
使
$\left \langle F_{0},H \right \rangle=-\left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1}$
。（比如
$F_{0}=-\textup{sgn}\left ( \emph{P}_{\Omega ^{\perp }}H \right )$
就是这样一个矩阵，同样，通过核范数和算子范数之间的对偶性，有一个满足
$\left \| W \right \|=1$
的矩阵，使得
$\left \langle W,\emph{P}_{T^{\perp }}H \right \rangle=\left \| \emph{P}_{T^{\perp }}H \right \|_{*}$
，我们只取
$W_{0}=\emph{P}_{T^{\perp }}\left ( W \right )$
。）我们有

$\left \| L_{0}+H \right \|_{*}+\lambda \left \| S_{0}-H \right \|_{1}\\ \geq \left \| L_{0} \right \|_{*}+\lambda \left \| S_{0} \right \|_{1}+\left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\lambda \left \| \emph{P}_{T^{\perp }}H \right \|_{1}+ \left \langle UV^{*}-\lambda \textup{sgn}\left ( S_{0} \right ) ,H \right \rangle$
。

通过假设

$\left | \left \langle UV^{*}-\lambda \textup{sgn}\left ( S_{0} \right ) ,H \right \rangle \right |\leq \left | \left \langle W,H \right \rangle \right |+\lambda \left | \left \langle F,H \right \rangle \right |\leq \beta \left ( \left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\lambda \left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1} \right )$
，
$\beta =\textup{max}\left ( \left \| W \right \| ,\left \| F \right \|_{\infty }\right )<1$

因此，

$\left \| L_{0}+H \right \|_{*}+\lambda \left \| S_{0}-H \right \|_{1} \geq \left \| L_{0} \right \|_{*}+\lambda \left \| S_{0} \right \|_{1}+\left ( 1-\beta \right )\left ( \left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1}\right )$
。

因为假设
$\Omega \cap T=\left \{ 0 \right \}$
，我们有
$\left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1}>0$
，除非
$H=0$
。

因此，我们看到，为了证明恢复是准确的，产生一个服从式(2.3)的“双重证明”
$W$
就足够了。

$\left\{\begin{matrix} W\in T^{\perp } , \\ \left \| W \right \|<1, \\ \emph{P}_{\Omega }\left ( UV^{*}+W \right )=\lambda\: \textup{sgn}\left ( S_{0} \right ), \\ \left \| \emph{P}_{\Omega^{\perp } }\left ( UV^{*}+W \right ) \right \|_{\infty }<\lambda . \end{matrix}\right. \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 2.3 \right )$

然而，我们的方法很可能会产生一个稍有不同的证明。其思想是稍微放缩约束
$\emph{P}_{\Omega }\left ( UV^{*}+W \right )=\lambda\: \textup{sgn}\left ( S_{0} \right )$
，这是David Gross在[22]中在不同的上下文中引入的放缩。我们证明了以下定理。

引理2.5：

假设
$\left \| \emph{P}_{\Omega } \emph{P}_{T} \right \|\leq 0.5$
，
$\lambda < 1$
。然后用同样的符号，

$UV^{\ast }+W=\lambda \left ( \textup{sgn}\left ( S_{0} \right )+F+\emph{P}_{\Omega }D \right )$
，和
$\emph{P}_{T } W=0$
，
$\left \| W \right \|<0.5$
，
$\emph{P}_{\Omega } F=0$
，且
$\left \| F \right \|_{\infty }<0.5$
，
$\left \| \emph{P}_{\Omega }D \right \|_{F }<0.25$
，

那么
$\left ( L_{0},S_{0} \right )$
是唯一解。

证明：

根据定理2.4的证明，我们有

$\left \| L_{0}+H \right \|_{*}+\lambda \left \| S_{0}-H \right \|_{1} \\ \geq \left \| L_{0} \right \|_{*}+\lambda \left \| S_{0} \right \|_{1}+\frac{1}{2}\left ( \left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\lambda \left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1}\right ) - \lambda \left \langle \emph{P}_{\Omega }D,H \right \rangle \\ \geq \left \| L_{0} \right \|_{*}+\lambda \left \| S_{0} \right \|_{1}+\frac{1}{2}\left ( \left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\lambda \left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1}\right ) - \frac{\lambda }{4}\left \| \emph{P}_{\Omega }H \right \|_{F }$
。

现在观察到

$\left \| \emph{P}_{\Omega }H \right \|_{F }\\ \leq \left \| \emph{P}_{\Omega } \emph{P}_{T } H \right \|_{F } + \left \| \emph{P}_{\Omega } \emph{P}_{T^{\perp } } H \right \|_{F } \\ \leq \frac{1}{2}\left \| H \right \|_{F } + \left \| \emph{P}_{T^{\perp } } H \right \|_{F } \\ \leq \frac{1}{2} \left \| \emph{P}_{\Omega }H \right \|_{F } + \frac{1}{2} \left \| \emph{P}_{\Omega ^{\perp } } H \right \|_{F } + \left \| \emph{P}_{T^{\perp } } H \right \|_{F }$

因此，
$\left \| \emph{P}_{\Omega }H \right \|_{F } \leq \left \| \emph{P}_{\Omega^{\perp } }H \right \|_{F } + 2 \left \| \emph{P}_{T^{\perp } }H \right \|_{F }$
。

总之，

$\left \| L_{0}+H \right \|_{*}+\lambda \left \| S_{0}-H \right \|_{1} \\ \geq \left \| L_{0} \right \|_{*}+\lambda \left \| S_{0} \right \|_{1}+\frac{1}{2}\left ( \left ( 1-\lambda \right )\left \| \emph{P}_{T^{\perp }}H \right \|_{*}+\frac{\lambda}{2 } \left \| \emph{P}_{\Omega ^{\perp }}H \right \|_{1}\right )$
，

当
$H\neq 0$
时，括号之间的项是严格正的。作为引理2.5的结果，它现在足以产生一个双重证明
$W$
服从

$\left\{\begin{matrix} W\in T^{\perp },\\ \left \| W \right \| < \frac{1}{2}\\ \left \| \emph{P}_{\Omega }\left ( UV^{*}-\lambda \: \textup{sgn}\left ( S_{0} \right )+W \right ) \right \|_{F}\leq \frac{\lambda }{4}\\ \left \| \emph{P}_{\Omega^{\perp } }\left ( UV^{*}+W \right ) \right \|_{\infty }\leq \frac{\lambda }{2} \end{matrix}\right. \: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \left ( 2.4 \right )$

此外，我们还想指出，关于矩阵补全的现有文献给出了
$\left \| \emph{P}_{\Omega }\emph{P}_{T} \right \|$
上的良好边界，请参见2.5节中的定理2.6。

2.4 基于高尔夫方案(

the golfing scheme

)的双重证明

在文献[22,23]中，Gross引入了一种新的方案，称为高尔夫方案，来构造矩阵补全问题的双重证书，即从其项的子集重构低秩矩阵的问题。在本节中，我们将采用这个聪明的高尔夫方案，并对其进行两个重要的修改，以适应我们的分解问题。

在介绍我们的构造之前，我们的模型假定
$\Omega \sim \textup{Ber}\left ( \rho \right )$
，或者它的等价形式
$\Omega^{c} \sim \textup{Ber}\left (1- \rho \right )$
，现在
$\Omega^{c}$
的分布和
$\Omega^{c}= \Omega _{1}\cup \Omega _{2}\cup\cdots \cup \Omega _{j_{0}}$
的分布是一样的。其中，每个
$\Omega _{j}$
服从参数为
$q$
的伯努利模型，它有一个显式表达式。要看到这一点，请注意，通过独立性，我们只需要确保以正确的概率选择任何元素
$\left ( i,j \right )$
。我们有

$\mathbb{P}\left ( \left ( i,j \right )\in \Omega \right )=\mathbb{P}\left ( \textup{Bin}\left ( j_{0},q \right ) =0 \right )=\left ( 1-q \right )^{j_{0}}$
，

如果
$\rho =\left ( 1-q \right )^{j_{0}}$
，这两个模型是相同的，因此证明我们的断言。

注意，因为
$\Omega _{j}\: 's$
之间的重叠，
$q\geq \frac{\left ( 1-\rho \right )}{j_{0}}$
。

我们现在打算构造一个双重证书
$W=W^{L}+W^{S}$
，其中各组成部分如下：

1、基于高尔夫球方案构造
$W^{L}$
。确定一个整数

$j_{0}\geq 1$
，其值将在稍后讨论，并让
$\Omega _{j},1\leq j\leq j_{0}$
定义为上面所述那样，以便
$\Omega ^{c}=\cup _{1\leq j\leq j_{0}}\Omega _{j}$
。然后从
$Y_{0}=0$
开始，归纳定义

$Y_{j}=Y_{j-1}+q^{-1}\emph{P}_{\Omega _{j}} \emph{P}_{T}\left ( UV^{*}-Y_{j-1} \right )$
，

令
$W_{L}=\emph{P}_{T ^{\perp }}Y_{j_{0}}.\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 2.5 \right )$

这是在[22]中讨论的高尔夫方案的一个变体，它假设
$\Omega _{j}\: 's$
是用替换的方式采样的，并且不使用投影向量
$\emph{P}_{\Omega _{j}}$
，而是考虑到特定元素被采样的次数的一些更复杂的东西。

2、基于最小平方法构造
$W^{S}$
。假设
$\left \| \emph{P}_{\Omega }\emph{P}_{T } \right \|<0.5$
。那么
$\left \| \emph{P}_{\Omega }\emph{P}_{T }\emph{P}_{\Omega } \right \|<0.25$
，因此算子
$\emph{P}_{\Omega } - \emph{P}_{\Omega }\emph{P}_{T }\emph{P}_{\Omega }$
将
$\Omega$
映射到它自身是可逆的；我们将该算子的逆表示为
$\left ( \emph{P}_{\Omega } - \emph{P}_{\Omega }\emph{P}_{T }\emph{P}_{\Omega } \right )^{-1}$
。然后我们设

$W^{S}=\lambda \emph{P}_{T^{\perp }}\left ( \emph{P}_{\Omega } - \emph{P}_{\Omega }\emph{P}_{T }\emph{P}_{\Omega } \right )^{-1}\textup{sgn}\left ( S_{0} \right )\: \: \: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \left ( 2.6 \right )$

显然，通过收敛的诺伊曼级数得到它的一个等价定义是

$W^{S}=\lambda \emph{P}_{T^{\perp }} \sum _{k\geq 0} \left ( \emph{P}_{\Omega }\emph{P}_{T }\emph{P}_{\Omega } \right )^{k}\textup{sgn}\left ( S_{0} \right )\: \: \: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \left ( 2.7 \right )$

注意，
$\emph{P}_{\Omega }W^{S}=\lambda \emph{P}_{T} \left ( I-\emph{P}_{T } \right ) \left ( \emph{P}_{\Omega } - \emph{P}_{\Omega }\emph{P}_{T }\emph{P}_{\Omega } \right )^{-1}\textup{sgn}\left ( S_{0} \right ) =\lambda\: \textup{sgn}\left ( S_{0} \right )$
，由此，该构造有一个自然的解释：可以证明在所有服从
$\emph{P}_{\Omega }W^{S}=\lambda\: \textup{sgn}\left ( S_{0} \right )$
的矩阵中，
$W^{S}$
是具有最小Frobenius范数的矩阵。

因为
$W^{L}$
和
$W^{S}$
都属于
$T^{\perp }$
，且
$\emph{P}_{\Omega }W^{S}=\lambda\: \textup{sgn}\left ( S_{0} \right )$
，我们将证实
$W^{L}+W^{S}$
是一个有效的双重证明，如果它服从

$\left\{\begin{matrix} \left \| W^{L}+W^{S} \right \|< 0.5 \\ \left \| \emph{P}_{\Omega }\left ( UV^{*}+W^{L} \right ) \right \|_{F} \leq \frac{\lambda }{4} \\ \left \| \emph{P}_{\Omega^{\perp } }\left ( UV^{*}+W^{L}+W^{S} \right ) \right \|_{\infty } \leq \frac{\lambda }{2} \end{matrix}\right. .\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 2.8 \right )$

2.5 关键的引理

现在我们陈述三个引理，它们共同构成了我们的主要定理。第一个可能在[8]中被发现。

定理2.6：

[8]中的定理4.1

假设
$\Omega _{0}$
是从参数为
$\rho _{0}$
的伯努利模型中抽样得来的。那么有很大的概率

$\left \| \emph{P}_{T}-\rho _{0}^{-1} \emph{P}_{T} \emph{P}_{\Omega _{0}}\emph{P}_{T} \right \|\leq \epsilon\: , \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 2.9 \right )$

如果对于某个数值常数
$C_{0}> 0$
，
$\rho _{0}\geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n }{n}$
（
$\mu$
是非相干系数，

the incoherence parameter

）。对于矩形矩阵，我们要求
$\rho _{0}\geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n_{\left ( 1 \right )} }{n_{\left ( 2 \right )}}$
。

除了别的以外，这个引理很重要，因为它表明
$\left \| \emph{P}_{\Omega } \emph{P}_{T} \right \|\leq 0.5$
，前提是
$\left | \Omega \right |$
不太大。的确，如果
$\Omega \sim \textup{Ber}\left ( \rho \right )$
，我们有

$\left \| \emph{P}_{T}-\left ( 1-\rho \right )^{-1} \emph{P}_{T} \emph{P}_{\Omega ^{\perp }}\emph{P}_{T} \right \|\leq \epsilon\: ,$

其中，
$1-\rho \geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n}{n}$
。但是注意，因为
$\emph{I}=\emph{P}_{\Omega }+\emph{P}_{\Omega^{\perp } }$
，

$\emph{P}_{T}-\left ( 1-\rho \right )^{-1} \emph{P}_{T} \emph{P}_{\Omega ^{\perp }}\emph{P}_{T} = \left ( 1-\rho \right )^{-1} \left ( \emph{P}_{T} \emph{P}_{\Omega }\emph{P}_{T}-\rho \emph{P}_{T} \right ),$

因此，根据三角不等式
$\left \| \emph{P}_{T} \emph{P}_{\Omega }\emph{P}_{T} \right \| \leq \epsilon \left ( 1-\rho \right )+\rho \left \| \emph{P}_{T} \right \| = \rho +\epsilon \left ( 1-\rho \right )$
。

因为
$\left \| \emph{P}_{\Omega }\emph{P}_{T} \right \| ^{2}=\left \| \emph{P}_{T} \emph{P}_{\Omega }\emph{P}_{T} \right \|$
，我们确定了以下内容：

推

论2.7：

假设
$\Omega \sim \textup{Ber}\left ( \rho \right )$
，那么
$\left \| \emph{P}_{\Omega }\emph{P}_{T} \right \| ^{2} \leq \rho +\epsilon$
的条件是
$1-\rho \geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n}{n}$
，其中，
$C_{0}$
如定理2.6所述。对于矩形矩阵，修改如定理2.6所示。

下面的引理被证明为第三节。

引理2.8：

假设
$\Omega \sim \textup{Ber}\left ( \rho \right )$
，
$\rho \leq \rho _{s}$
，
$\rho _{s}> 0$
。设
$j_{0}=2\left \lceil \textup{log}\: n \right \rceil$
，（如果是矩形矩阵，我们采用
$\textup{log}\: n_{\left ( 1 \right )}$
）。然后在定理1.1的其他假设下，矩阵
$W^{L}$
(2.5)满足

（a）
$\left \| W^{L} \right \|\leq 0.25$
，

（b）
$\left \| \emph{P}_{\Omega }\left ( UV^{*}+W^{L} \right ) \right \|_{F} < \frac{\lambda }{4}$
，

（c）
$\left \| \emph{P}_{\Omega^{\perp } }\left ( UV^{*}+W^{L} \right ) \right \|_{\infty } < \frac{\lambda }{4}$
。

由于
$\left \| \emph{P}_{\Omega }\emph{P}_{T} \right \| <1$
的概率很大，
$W^{S }$
的定义很好，如下所示。

引理2.9：

假设
$S_{0}$
的support set是
$\Omega$
，
$\Omega$
是如引理2.8中那样进行采样得到的。
$S_{0}$
的符号矩阵是独立同分布的，对称的（与
$\Omega$
相互独立）。然后在定理1.1的其他假设下，矩阵
$W^{S}$
(2.6)满足

（a）
$\left \| W^{S} \right \|\leq 0.25$
，

（b）
$\left \| \emph{P}_{\Omega^{\perp } } W^{S} \right \|_{\infty } < \frac{\lambda }{4}$
。

证明也在第三节。可见，
$W^{L}$
和
$W^{S}$
满足(2.8)，从而证明当
$S_{0}$
的符号随机时，PCP能够正确地恢复低秩和稀疏分量的概率较高。前面的去泛化论证证明了定理1.1。

3 双重证明的证明

本节证明了两个重要的估计，引理2.8和引理2.9。

3.1 前言

我们首先记录两个结果，这两个结果将有助于证明引理2.8。虽然定理2.6说明，在很大的概率下，对于所有的
$Z\in T$
，

$\left \| Z-\rho _{0}^{-1} \emph{P} _{T} \emph{P} _{\Omega _{0}} Z \right \|_{F} \leq \epsilon \left \| Z \right \|_{F}$
，

下一个引理表明对于一个固定的
$Z$
，（在很大概率下）
$Z- \rho _{0}^{-1} \emph{P} _{T} \emph{P} _{\Omega _{0}} \left ( Z \right )$
的范数也不会增加。

引理3.1：

假设
$Z\in T$
是一个固定的矩阵，且
$\Omega_{0} \sim \textup{Ber}\left ( \rho_{0} \right )$
。那么高概率情况下

$\left \| Z-\rho _{0}^{-1} \emph{P} _{T} \emph{P} _{\Omega _{0}} Z \right \|_{\infty } \leq \epsilon \left \| Z \right \|_{\infty },\: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.1 \right )$

前提是
$\rho_ {0} \geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n}{n}$
(对于矩形矩阵是
$\rho _{0}\geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n_{\left ( 1 \right )} }{n_{\left ( 2 \right )}}$
) ，其中数值常数
$C_{0}> 0$
。

这个证明是伯恩斯坦(Bernstein)不等式的一个应用，可以在附录中找到。[44]中有一个式(3.1)的相似版本，但略有不同。

第二个结果在[8]中得到了证明。

引理3.2：

[8, Theorem 6.3] 假设
$Z$
是固定的，且
$\Omega_{0} \sim \textup{Ber}\left ( \rho_{0} \right )$
。那么高概率情况下，对于某个较小的数值常数
$C_{0}'> 0$
，

$\left \| \left ( I-\rho _{0}^{-1} \emph{P} _{\Omega _{0}}\right )Z \right \| \leq C_{0}'\sqrt{\frac{n\: \textup{log}\: n}{\rho _{0}}} \left \| Z \right \|_{\infty },\: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.2 \right )$

前提是
$\rho_ {0} \geq C_{0}\frac{\mu \textup{log} \: n}{n}$
(或者对于矩形矩阵是
$\rho_ {0} \geq C_{0}'\frac{\mu \textup{log} \: n_{\left ( 1 \right )}}{n_{\left ( 2 \right )}}$
，其中，
$n_{\left ( 1 \right )}\: \textup{log} \: n_{\left ( 1 \right )}$
替代 (3.2)中的
$n\: \textup{log}\: n$
)。

请注意，如果用
$C\beta$
（其中数值常数
$C> 0$
）代替
$C_{0}$
，那么在概率至少为
$1-O\left ( n^{-\beta } \right )$
，
$\beta >2$
时，引理3.1和3.2以及定理2.6都成立。

3.2 引理2.8的证明

我们首先介绍一个符号，设
$Z_{j}=UV^{*}-\emph{P}_{T}Y_{j}$
满足
$Z_{j}= \left ( \emph{P}_{T}-q^{-1}\emph{P}_{T}\emph{P}_{\Omega _{j}}\emph{P}_{T} \right ) Z_{j-1}$
。

显然对于所有的
$j\geq 0$
，
$Z_{j}\in T$
。首先注意当
$q \geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n }{n}, \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.3 \right )$

（对于矩形矩阵，取
$q \geq C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n_{\left ( 1 \right )} }{n_{\left ( 2 \right )}}$
），由引理3.1，我们有
$\left \| Z_{j} \right \|_{\infty }\leq \epsilon \left \| Z_{j-1} \right \|_{\infty }, \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.4 \right )$

（这成立的概率很高，因为
$\Omega _{j}$
和
$Z_{j-1}$
是独立的，这就是高尔夫方案很容易使用的原因。）特别地，这个给出了
$\left \| Z_{j} \right \|_{\infty }\leq \epsilon ^{j} \left \| UV^{*} \right \|_{\infty }$
的概率很高。

当
$q$
服从相同的估计时，由定理2.6，
$\left \| Z_{j} \right \|_{F }\leq \epsilon \left \| Z_{j-1} \right \|_{F }, \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.5 \right )$

特别地，这给出了高概率情况下
$\left \| Z_{j} \right \|_{F }\leq \epsilon ^{j} \left \| UV^{*} \right \|_{F } =\epsilon ^{j} \sqrt{r}.\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.6 \right )$

下面我们假设
$\epsilon \leq e^{-1}$
。

（a）的证明：

我们证明引理的第一部分，这个论证与[22]相似，也见[44]。由
$Y_{j_{0}}=\sum _{j} q^{-1}\emph{P}_{\Omega _{j}}Z_{j-1}$
，我们推断

$\left \| W^{L} \right \| = \left \| \emph{P}_{T^{\perp }} Y_{j_{0}} \right \|_{\infty } \\ \leq \sum _{j}\left \| q^{-1} \emph{P}_{T^{\perp }} \emph{P}_{\Omega _{j }} Z_{j-1}\right \| \\ = \sum _{j}\left \| \emph{P}_{T^{\perp }}\left ( q^{-1} \emph{P}_{\Omega _{j }} Z_{j-1} - Z_{j-1} \right ) \right \| \\ \leq \sum _{j}\left \| q^{-1} \emph{P}_{\Omega _{j }} Z_{j-1}-Z_{j-1}\right \| \\ \leq C_{0}' \sqrt{\frac{n \textup{log} \: n}{q}} \sum _{j}\left \| Z_{j-1} \right \|_{\infty } \\ \leq C_{0}' \sqrt{\frac{n \textup{log} \: n}{q}} \sum _{j} \epsilon ^{j-1} \left \| UV^{*} \right \|_{\infty } \\ \leq C_{0}' \left ( 1-\epsilon \right )^{-1} \sqrt{\frac{n \textup{log} \: n}{q}} \left \| UV^{*} \right \|_{\infty }$
。

第四步是从引理3.2开始的，第五步是从引理(3.5)开始的。因为
$\left \| UV^{*} \right \|\leq \frac{\sqrt{\mu r}}{n}$
，这就得到无论
$q$
是否满足(3.3)式，对于数值常数
$C'$
，
$\left \| W^{L} \right \|\leq C'\epsilon$
。

（b）的证明：

因为
$\emph{P}_{\Omega }Y_{j_{0}}=0$
，
$\emph{P}_{\Omega }\left ( UV^{*}+ \emph{P}_{T^{\perp } }Y_{j_{0}} \right ) = \emph{P}_{\Omega }\left ( UV^{*}- \emph{P}_{T }Y_{j_{0}} \right ) =\emph{P}_{\Omega }\left ( Z_{j_{0}} \right )$
，

由(3.6)可知，
$\left \| Z_{j_{0}} \right \|_{F}\leq \epsilon ^{j_{0}} \left \| UV^{*} \right \|_{F}=\epsilon ^{j_{0}} \sqrt{r}$
。

因为
$\epsilon \leq e^{-1}$
，
$j_{0}\geq 2\, \textup{log}\: n$
，
$\epsilon ^{j_{0}} \leq \frac{1}{n^{2}}$
，这就得出了这个结论。

（c）的证明：

我们有
$UV^{*}+W^{L}=Z_{j_{0}}+Y_{j_{0}}$
，且已知
$Y_{j_{0}}$
的support set是
$\Omega ^{c}$
。因此，
$\left \| Z_{j_{0}} \right \|_{F}\leq \frac{\lambda }{8}$
足以说明
$\left \| Y_{j_{0}} \right \|_{\infty }\leq \frac{\lambda }{8}$
。我们有

$\left \| Y_{j_{0}} \right \|_{\infty }\\ \leq q^{-1}\sum _{j}\left \| \emph{P}_{\Omega _{j}}Z_{j-1} \right \|_{\infty } \\ \leq q^{-1}\sum _{j}\left \| Z_{j-1} \right \|_{\infty } \\ \leq q^{-1}\sum _{j}\epsilon ^{j} \left \| UV^{*} \right \|_{\infty }$
。

因为
$\left \| UV^{*} \right \|_{\infty }\leq \frac{\sqrt{\mu r}}{n}$
，得出无论
$q$
是否满足(3.3)，对于数值常数
$C'$
，
$\left \| Y_{j_{0}} \right \|_{\infty } \leq C' \frac{\epsilon ^{2}}{\sqrt{\mu r\left ( \textup{log}\: n \right )^{2}}}$
。

因为
$\lambda =\frac{1}{\sqrt{n}}$
，如果
$\epsilon \leq C \left ( \frac{\mu r\left ( \textup{log}\: n \right )^{2}}{n} \right )^{\frac{1}{4}}$
，那么
$\left \| Y_{j_{0}} \right \|_{\infty }\leq \frac{\lambda }{8}$
。

总结：

我们已经看到如果
$\epsilon$
足够小，且
$j_{0}\geq 2\, \textup{log}\, n$
，(a)和(b)就都满足了。对于(c)，我们可以取
$\epsilon$
的
$\left ( \frac{\mu r\left ( \textup{log}\: n \right )^{2}}{n} \right )^{\frac{1}{4}}$
次方，只要(1.4)中的
$\rho _{r}$
足够小，它也足够小。注意，由于
$C_{0}\epsilon ^{-2}\frac{\mu r\textup{log} \: n }{n} < 1$
，所以一切都是一致的。这就是引理2.8的证明。

3.3 引理2.9的证明

方便起见，引入符号矩阵
$E=\textup{sgn}\left ( S_{0} \right )$
，它的分布为

$E_{ij}=\left\{\begin{matrix} 1, & \textup{w.p.}\: \: \frac{\rho }{2}\: , \\ 0,& \textup{w.p.}\: \: 1-\rho\: , \\ -1,& \textup{w.p.}\: \: \frac{\rho }{2}\: . \end{matrix}\right. \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \left ( 3.7 \right )$

我们将对事件
$\left \{ \left \| \emph{P}_{\Omega } \emph{P}_{T } \right \|\leq \sigma \right \}$
感兴趣，当
$\sigma =\sqrt{\rho }+\epsilon$
时，它以较高的概率成立，见推论2.7。特别是，对于任何
$\sigma > 0$
，
$\left \{ \left \| \emph{P}_{\Omega } \emph{P}_{T } \right \|\leq \sigma \right \}$
成立的概率较高，前提是
$\rho$
足够小。

（a）的证明：

构造

$W^{S}\\=\lambda \emph{P}_{T^{\perp }}E + \lambda \emph{P}_{T^{\perp }}\sum _{k\geq 1} \left ( \emph{P}_{\Omega } \emph{P}_{T}\emph{P}_{\Omega } \right )^{k}E \\ :=\emph{P}_{T^{\perp }}W_{0}^{S} + \emph{P}_{T^{\perp }}W_{1}^{S}$

对于第一项，我们有
$\left \| \emph{P}_{T^{\perp }}W_{0}^{S} \right \|\leq \left \| W_{0}^{S} \right \|=\lambda \left \| E \right \|$
，然后，若一个矩阵的元素是独立同分布的，关于该矩阵的范数的标准参数给出大概率情况下，
$\left \| E \right \|\leq 4\sqrt{n\rho }$
。因为
$\lambda = \frac{1}{\sqrt{n}}$
，得出
$\left \| W_{0}^{S} \right \|\leq 4\sqrt{\rho }$
。当矩阵是矩形时，高概率情况下，
$\left \| E \right \|\leq 4\sqrt{n_{\left ( 1 \right )}\rho }$
。因为这种情况下
$\lambda = \frac{1}{\sqrt{n_{\left ( 1 \right )}}}$
，我们也可以得出
$\left \| W_{0}^{S} \right \|\leq 4\sqrt{\rho }$
。

设
$\Re =\sum _{k\geq 1}\left ( \emph{P}_{\Omega } \emph{P}_{T} \emph{P}_{\Omega } \right )^{k}$
，观察到
$\Re$
是自共轭的。对于第二项，
$\left \| \emph{P}_{T^{\perp }}W_{1}^{S} \right \|\leq \left \| W_{1}^{S} \right \|$
，其中
$W_{1}^{S}=\lambda \Re \left ( E \right )$
。我们需要约束矩阵
$\Re \left ( E \right )$
的算子范数，并使用一个standard covering argument来做到这一点。自始至终，
$N$
表示
$\mathbb{S}^{n-1}$
的1/2-net，其大小不超过
$6^{n}$
（这样的net存在，见[30，定理4.16]）。然后一个standard argument[48]表明

$\left \| \Re \left ( E \right ) \right \| = \textup{sup}_{x,y\in \mathbb{S}^{n-1}}\left \langle y, \Re \left ( E \right ) x \right \rangle \leq 4\: \textup{sup}_{x,y\in N} \left \langle y, \Re \left ( E \right ) x \right \rangle.$

对于
$N\times N$
的单位标准化向量中的一个固定对
$\left ( x,y \right )$
，定义随机变量
$X\left ( x,y \right ):=\left \langle y,\Re\left ( E \right )x \right \rangle=\left \langle \Re\left ( yx^{*} \right ),E \right \rangle$
。

在
$\Omega =\textup{supp}\left ( E \right )$
条件下，
$E$
的符号是i.i.d对称的，Hoeffding不等式给出

$\mathbb{P}\left ( \left | X\left ( x,y \right ) \right | > t \mid \Omega \right ) \leq 2\: \textup{exp}\left ( -\frac{2t^{2}}{\left \| \Re \left ( xy^{*} \right ) \right \|_{F}^{2}} \right )$
。

现在因为
$\left \| yx^{*} \right \|=1$
，矩阵
$\Re \left ( yx^{*} \right )$
满足
$\left \| \Re \left ( yx^{*} \right ) \right \|_{F}\leq \left \| \Re \right \|$
，因此
$\mathbb{P}\left (\textup{supp} _{x,y\in N} \left | X\left ( x,y \right ) \right | > t \mid \Omega \right ) \leq 2\left | N \right |^{2}\: \textup{exp}\left ( -\frac{2t^{2}}{\left \| \Re \right \|^{2}} \right )$
。

所以，
$\mathbb{P}\left ( \left \| \Re \left ( E \right ) \right \|> t \mid \Omega \right ) \leq 2\left | N \right |^{2}\: \textup{exp}\left ( -\frac{t^{2}}{8 \left \| \Re \right \|^{2}} \right )$
。

关于事件
$\left \{ \left \| \emph{P}_{\Omega } \emph{P}_{T } \right \| \leq \sigma \right \}$
，
$\left \| \Re \right \|\leq \sum _{k\geq 1}\sigma ^{2k}= \frac{\sigma ^{2}}{1-\sigma ^{2}}$
，因此，无条件地，

$\mathbb{P}\left ( \left \| \Re \left ( E \right ) \right \|> t \right ) \leq 2\left | N \right |^{2}\: \textup{exp}\left ( -\frac{\gamma ^{2} t^{2}}{2 } \right ) +\mathbb{P}\left ( \left \| \emph{P}_{\Omega } \emph{P}_{T } \right \| \geq \sigma \right ),\: \: \: \: \: \: \: \: \gamma = \frac{1-\sigma ^{2}}{2\sigma ^{2}}$
。

这就得出
$\mathbb{P}\left ( \lambda \left \| \Re \left ( E \right ) \right \|> t \right ) \leq 2\times 6^{2n}\: \textup{exp}\left ( -\frac{\gamma ^{2} t^{2}}{2 \lambda ^{2} } \right ) +\mathbb{P}\left ( \left \| \emph{P}_{\Omega } \emph{P}_{T } \right \| \geq \sigma \right )$
。

当
$\lambda = \frac{1}{\sqrt{n}}$
时，
$\left \| W^{S} \right \|\leq \frac{1}{4}$
的概率较大，前提是
$\sigma$
或等效的
$\rho$
足够小。

（b）的证明：

观察到
$\emph{P}_{\Omega ^{\perp }}W^{S} = -\lambda \emph{P}_{\Omega ^{\perp }} \emph{P}_{T}\left ( \emph{P}_{\Omega } - \emph{P}_{\Omega } \emph{P}_{T } \emph{P}_{\Omega }\right )^{-1} E$
。

现在，对于
$\left ( i,j \right )\in \Omega ^{c}$
，
$W_{ij}^{S}=\left \langle e_{i},W^{S}e_{j} \right \rangle = \left \langle e_{i}e_{j} ^{*},W^{S}\right \rangle$
，我们有
$W_{ij}^{S}=\lambda \left \langle X\left ( i,j \right ),E \right \rangle$
，其中，
$X\left ( i,j \right )$
是矩阵
$-\left ( \emph{P}_{\Omega } - \emph{P}_{\Omega } \emph{P}_{T } \emph{P}_{\Omega }\right )^{-1} \emph{P}_{\Omega} \emph{P}_{T} \left ( e_{i}e_{j}^{*} \right )$
。在
$\Omega =\textup{supp}\left ( E \right )$
条件下，
$E$
的符号是i.i.d对称的，Hoeffding不等式给出

$\mathbb{P}\left ( \left | W _{ij}^{S} \right | > t \lambda \mid \Omega \right ) \leq 2\: \textup{exp}\left ( -\frac{2t^{2}}{\left \| X\left ( i, j \right ) \right \|_{F}^{2}} \right )$
，

因此，
$\mathbb{P}\left ( \textup{supp} _{i,j} \left | W _{ij}^{S} \right | > t \lambda \mid \Omega \right ) \leq 2 n^{2}\, \textup{exp}\left ( -\frac{2t^{2}}{\textup{supp} _{i,j} \left \| X\left ( i, j \right ) \right \|_{F}^{2}} \right )$
。

因为(2.2)成立，关于事件
$\left \{ \left \| \emph{P}_{\Omega } \emph{P}_{T } \right \| \leq \sigma \right \}$
，我们有
$\left \| \emph{P}_{\Omega} \emph{P}_{T} \left ( e_{i}e_{j}^{*} \right ) \right \| _{F} \leq \left \| \emph{P}_{\Omega} \emph{P}_{T} \right \| \left \| \emph{P}_{T} \left ( e_{i}e_{j}^{*} \right ) \right \| _{F} \leq \sigma \sqrt{\frac{2\mu r}{n}}$
。

在同一事件中，
$\left \| \left ( \emph{P}_{\Omega } - \emph{P}_{\Omega } \emph{P}_{T } \emph{P}_{\Omega }\right )^{-1} \right \| \leq \left ( 1-\sigma ^{2} \right )^{-1}$
，因此，
$\left \| X\left ( i,j \right ) \right \| _{F}^{2} \leq \frac{2\sigma ^{2}}{\left ( 1-\sigma ^{2} \right )^{2}}\, \frac{\mu r}{n}$
。

那么，无条件地，

$\mathbb{P}\left ( \textup{supp} _{i,j} \left | W _{ij}^{S} \right | > t \lambda \right ) \leq 2 n^{2}\, \textup{exp}\left ( -\frac{n \gamma ^{2} t^{2}}{\mu r} \right ) + \mathbb{P}\left ( \left \| \emph{P}_{\Omega } \emph{P}_{T} \right \|\geq \sigma \right ),\\ \gamma = \frac{\left ( 1-\sigma ^{2} \right )^{2}}{2\sigma ^{2}}$
。

当
$\mu r< \rho _{r}'n \left ( \textup{log}\, n \right )^{-1}$
，
$\rho _{r}'$
足够小时，定理就得到了证明。

4 数值实验与应用

在本节中，我们进行了数值实验，证实了我们的主要结果，并提出了它们在图像和视频分析中的许多应用。我们首先研究了主成分追踪从不同密度的误差中正确恢复不同秩矩阵的能力。然后，我们从应用到视频的背景建模中和人脸图像中的阴影和镜面反射的去除。

虽然定理1.1提供的精确恢复保证不依赖于求解主成分寻优的特定算法，但它对大规模问题的适用性取决于非光滑凸优化的可伸缩算法的可用性。在本节的实验中，我们使用了[32,51]中引入的增广拉格朗日乘子算法([32,51]都在网上发布了自己的代码)。在第5节中，我们将更详细地描述这个算法，并解释为什么它是我们用于稀疏和低秩分离的算法。

在我们的方法中，一个重要的实现细节是选择
$\lambda$
。通过分析，我们确定了一个选择方法，
$\lambda =\frac{1}{\sqrt{\textup{max}\left ( n_{1},n_{2} \right )}}$
，这个方法适用于非相干矩阵。为了说明这一理论，在本节中，我们总是会选择
$\lambda =\frac{1}{\sqrt{\textup{max}\left ( n_{1},n_{2} \right )}}$
。然而对于实际问题，根据解的先验知识选择
$\lambda$
通常可以提高性能。例如，如果我们知道
$S$
非常稀疏，增加
$\lambda$
将使我们得到较高秩的矩阵
$L$
。对于实际问题，我们建议将
$\lambda =\frac{1}{\sqrt{\textup{max}\left ( n_{1},n_{2} \right )}}$
作为一个好的经验法则，然后可以稍微调整以获得最好的结果。

4.1 从不同程度的误差中精确恢复

我们首先证明了定理1.1对随机生成问题的正确恢复现象。我们考虑不同维度
$n = 500,\cdots ,3000$
的平方矩阵。我们生成一个秩为
$r$
的矩阵
$L_{0}$
，
$L_{0}=XY^{*}$
，其中
$X$
和
$Y$
是
$n\times r$
的矩阵，其元素是从
$\mathfrak{N}\left ( 0,\frac{1}{n} \right )$
分布中独立采样得到的。
$S_{0}$
是在一个大小为
$k$
的support set
$\Omega$
上随机均匀生成的，令
$S_{0}=\emph{P}_{\Omega }E$
，其中
$E$
是一个具有独立伯努利
$\pm 1$
元素的矩阵。

表1(上半部分)给出了
$r=\textup{rank}\left ( L_{0} \right )=0.05\times n$
，
$k=\left \| S_{0} \right \|_{0}=0.05\times n^{2}$
时的结果，表1(下半部分)给出了在更具挑战性的场景中应用的结果，其中
$\textup{rank}\left ( L_{0} \right )=0.05\times n$
，
$k=0.10\times n^{2}$
。在所有的示例中，我们设
$\lambda = \frac{1}{\sqrt{n}}$
。注意，在所有情况下，求解凸PCP都会得到具有正确秩和稀疏性的结果
$\left ( L,S \right )$
。此外，相对误差
$\frac{\left \| L-L_{0} \right \|_{F}}{ \left \| L_{0} \right \|_{F}}$
较小，在所有的例子中都少于
$10^{-5}$
。（我们只用
$L$
来度量相对误差，因为在本文中我们把稀疏和低秩分解看作从总误差中恢复低秩矩阵
$L_{0}$
。当然，
$S_{0}$
也恢复得很好:在本例中，
$S$
中的相对误差实际上小于
$L$
中的相对误差。）

表1：大小不同的随机问题的正确恢复。

表1的最后两列给出了优化过程中计算的部分奇异值分解数(# SVD)和总计算时间。本实验在Mac Pro上使用Matlab进行，Mac Pro采用双四核2.66 GHz Intel Xenon处理器和16gb RAM。正如我们将在第5节中讨论的，求解凸程序的主要成本来自于每次迭代计算一个部分SVD。值得注意的是，在表1中，SVD计算的数量几乎是恒定的，无论维度如何，在所有情况下都小于17(有人可能会合理地问，这种接近常数的迭代次数是否是由于这样一个事实，即随机问题在某种意义上是条件良好的。我们将在实际的数据示例中看到，这种关注有一定的合理性。[32]建议一种延续策略(这里称为“不精确ALM”)，它用同样少的迭代产生质量上类似的解决方案。然而，就我们所知，它的收敛性并没有得到保证)。这表明，除了在理论上有充分的依据外，本文所提倡的恢复过程也是合理可行的。

4.2 秩和稀疏性的相变

定理1.1表明，凸规划正确恢复一个不相干的低秩矩阵的误差是一个常数分数
$\rho _{s}$
。然后，我们实证研究了该算法从不同稀疏性误差中恢复不同秩矩阵的能力。我们考虑一个
$n_{1}=n_{2}=400$
的方阵。我们生成低秩矩阵
$L_{0}=XY^{*}$
，其中，
$X$
和
$Y$
是独立选择的
$n\times r$
矩阵，具有均值为0、方差为
$\frac{1}{n}$
的独立同分布的高斯项。在我们的第一个实验中，我们为稀疏项
$S_{0}$
的support set 假设一个伯努利模型，带有随机符号：
$S_{0}$
的每个元素取0的概率为
$1-\rho$
，取
$\pm 1$
的概率分别为
$\frac{\rho }{2}$
。对于每个
$\left ( r,\rho \right )$
对，我们生成了10个随机问题，每个问题都通过第5节的算法来解决。如果恢复的
$\hat{L}$
满足

，我们就说这个试验是成功的。图1(左)画出了每个
$\left ( r,\rho \right )$
对的正确恢复率。请注意，有一个很大的区域恢复是精确的。这突出了我们研究结果的一个有趣方面：即使在某些情况下是
$\left \| S_{0} \right \|_{F}\gg \left \| L_{0} \right \|_{F}$
，恢复也是正确的(例如，
$\frac{r}{n}= \rho$
，
$\left \| S_{0} \right \|_{F}$
是
$\sqrt{n}=20$
倍大时)。可以从引理2.4中得到：双重证书是否存在仅取决于
$S_{0}$
的符号和support set 以及
$L_{0}$
的奇异空间的方向。

然而，对于非相干的
$L_{0}$
，我们的主要结果更进一步，表明
$S_{0}$
的符号也不重要：恢复是可以保证的，只要它的support set是均匀随机选择的。我们通过

再次对
$L_{0}$
采样作为高斯矩阵的乘积

以及

根据伯努利模型选择support set

来验证这一点，但这次设
$S_{0}=\emph{P}_{\Omega }\textup{sgn}\left ( L_{0} \right )$
。人们可能认为这样的
$S_{0}$
与
$L_{0}$
更难区分。尽管如此，我们的分析表明，当换成这个更困难的模型时，可以纠正的错误最多减少1/2。图1（中间）给出了改变
$r$
和
$\rho$
的10次试验中的正确恢复率。有趣的是，图1(中间)中正确恢复的区域实际上似乎比图1(左边)中更宽。诚然，左上角区域的形状令人费解，但已经通过几个不同的模拟实验(使用不同的求解器)得到了“证实”。

最后，受矩阵补全和鲁棒主成分分析之间联系的启发，我们将低秩稀疏分解问题的分解点与矩阵补全的核范数启发式分解行为进行了比较。通过比较这两种启发式方法，我们可以开始回答这个问题：通过知道损坏元素的位置可以获得多少信息？这里，我们再次生成
$L_{0}$
作为高斯矩阵的乘积。然而，但是，我们现在只为算法提供了其元素的不完全子集
$M=\emph{P}_{\Omega }L_{0}$
。每个
$\left ( i,j \right )$
是以概率
$1-\rho$
独立包括在
$\Omega$
中，而不是一个错误的概率，这里，
$\rho$
表示省略一个条目的概率。我们使用与第5节中讨论的非常相似的增广拉格朗日乘子算法来解最小化核范数的问题

$\textup{min}\: \left \| L \right \|_{*}\: \: \: \: \: \: \: \textup{subject to} \: \: \emph{P}_{\Omega ^{\perp }}L=\emph{P}_{\Omega ^{\perp }}M$
。

如果

，则再一次说明
$L_{0}$
被成功恢复。图1(右)给出了不同
$r$
，
$\rho$
值下的正确恢复率。请注意，核范数最小化在更大范围的(
$r$
,
$\rho$
)中成功恢复了
$L_{0}$
。这是有趣的，因为在

k

比较大

的情况下，每个启发式的最佳性能保证在其增长顺序上一致，都保证

的正确恢复。要完全解释这两个问题之间的性能差异，可能需要对各自的故障行为进行更清晰的分析。

4.3 应用案例：监控视频的背景建模

由于帧之间的相关性，视频是低秩建模的天然候选对象。视频监控中最基本的算法任务之一就是为场景中的背景变化估计一个好的模型。前景物体的存在使得该任务变得复杂：在繁忙的场景中，每一帧都可能包含一些异常。此外，背景模型需要足够灵活，以适应场景中的变化，例如不同光照的变化。在这种情况下，很自然地将背景变化建模为近似低秩。前景对象，如汽车或行人，通常只占图像像素的一小部分，因此可以作为稀疏误差处理。

我们研究了凸优化能否从低秩背景中分离稀疏误差。这里，需要重点指出的是错误的support 可能不能很好地建模为伯努利模型：误差往往是空间相干的，更复杂的模型，如马尔可夫随机场可能更合适[11,52]。因此，我们的定理并不能保证算法以高概率成功。然而，正如我们将看到的，在不使用任何额外的关于误差空间结构信息的情况下，PCP仍然为这个实际的低秩和稀疏分离问题提供了视觉上吸引人的解决方案。

我们考虑[31]中引入的两个视频。第一个是在机场拍摄的具有200个帧的灰度序列。这个视频有一个相对静态的背景，但前景变化比较显著。每个帧的分辨率为 176×144；我们将每帧的数据排列为矩阵

的一列。通过求解凸PCP问题(1.1)(其中，

)，我们将

M

分解为一个低秩项和一个稀疏项。在拥有2.33 GHz Core2双核处理器和2gb内存的桌面PC上，我们的Matlab实现需要806次迭代，大约需要43分钟的时间(论文[32]提出了ALM优化程序的一种改进，这里称为“不精确的ALM”，它采用了更少的迭代次数(少于50次)找到一个视觉上类似的分解。然而，由于该变量的收敛性保证较弱，我们选择在这里给出较慢一点的、精确的结果)。图2(a)显示了视频中的三帧；(b)和 (c)展示了低秩矩阵

和稀疏矩阵

对应的列（这里展示的是它们的绝对值）。我们注意到

是

正确恢复的背景，而

是正确识别出的移动的行人。

图像中出现的人在整个视频中是不移动的。

图2 (d)和(e)将PCP得到的结果与计算机视觉文献[47]中的最新技术进行了比较(使用的是从

http://www.salleurl.edu/~ftorre/papers/rpca/rpca.zip

下载的代码包，改进以选择在[47]中建议的近似的秩)。该方法也旨在鲁棒地恢复一个良好的低秩近似，但使用了一个更复杂的、非凸m-估计器，这个估计器包含了一个隐式利用自然图像空间特征的局部尺度估计。这使得问题变成了一个高度非凸的优化问题，我们通过交替最小化局部求解。有趣的是，尽管使用了更多关于信号被恢复的先验信息，这种方法的表现还是不如凸规划启发式：注意图2 (d)的顶部和底部行中的大artifacts。

在图3中，我们考虑了一个具有250帧的序列，其中有几帧光照变化比较剧烈。分辨率是168×120，因此

M

是一个20，168×250的矩阵。简单起见，为了说明上述理论结果，我们再次选

。(对于本例来说，实际上可以通过选择较大的λ(比如

)来获得更吸引人的结果)。对于本例，在相同的2.66 GHz Core 2 Duo机器上，算法总共需要561次迭代和36分钟才能收敛。

图3 (a)为取自原始视频的三帧，(b)和(c)分别为恢复的低秩和稀疏分量。请注意，低秩分量正确地将主要的光照识别为背景，将稀疏分量对应于场景中的运动。另一方面，[47]中的算法得到的结果将some of the first illumination 作为前景。尽管使用了较少的先验信息，PCP还是再次优于对比方法。这些结果表明了凸规划作为视频分析工具的潜力。

请注意，实际数据的迭代次数通常要高于表1中给出的随机矩阵的模拟次数。造成这种差异的原因可能是真实数据的结构与理想的低秩稀疏模型略有偏离。然而，重要的是要认识到实际应用，如视频监控，往往提供有关感兴趣信号的额外信息，例如稀疏前景的support是空间分段连续的，甚至施加额外的要求，例如恢复的背景需要是非负的等。我们注意到，我们的目标和解决方案的简单性表明，我们可以很容易地纳入附加的约束条件和更精确的信号模型，以便在未来获得更有效和更精确的解决方案。

4.4 应用案例：从脸部图像中消除阴影和高光

人脸识别是计算机视觉中的另一个研究领域，其中低维线性模型得到了广泛的关注。这主要是Basri 和 Jacobs所做的贡献，他们展示了对于凸面，兰伯式的物体(Lambertian objects)，在遥远的光照下拍摄的图像位于一个近似九维的线性子空间(即所谓的谐面)附近。然而，由于人脸既不是完美凸形，也不是朗伯式的，真实的人脸图像经常会由于投射阴影和不规则性而违背这个低秩模型。这些误差在量级上很大，但在空间域上是稀疏的。我们有理由相信，如果我们有足够多的同一张人脸的图像，PCP可以去除这些误差。与前面的例子一样，需要注意的是：理论结果表明，性能应该是好的，但不能保证它，因为错误的support不是完全遵循伯努利模型的。然而，正如我们将看到的，结果在视觉上是惊人的。

图4展示了两个示例，其中的人脸图像取自Yale B人脸数据库[18]。这里，每幅图像的分辨率都是192×168，每个主题总共有58个照明，我们将其堆叠在矩阵

的列中。再一次求解参数

的PCP模型，在这种情况下，算法需要642次迭代才能收敛，在同一台Core 2 Duo机器上的总计算时间为685秒。

图4绘制了作为凸优化问题解的低秩项

和稀疏项

的大小。稀疏项

补偿阴影和高光区域。在一个示例中(图4底部左行)，这项还可以补偿图像采集中的错误。这些结果可能对人脸识别训练数据的调整，以及在光照变化下的人脸定位和跟踪有帮助。

5 算法

定理1.1表明非相干低秩矩阵可以在多项式时间内从总误差的非缺失部分恢复。此外，正如上一节的实验所证明的那样，该方法不仅在理论上保证了较低的计算代价，而且在实际的成像问题中具有实用价值。由于非光滑凸优化的可扩展算法的快速发展，尤其是

范数和核范数最小化，使得这种实用价值得到了提高。在这一节中，我们简要回顾这一进展，并讨论对于这个问题，算法的选择。

对于小问题，PCP

可以使用现成的工具来执行，比如内部点法。在[16,45]中对秩最小化提出了这一建议，[12](也见[35])中对低秩稀疏分解提出了这一建议。然而，尽管其优越的收敛速度，内部点法通常局限于小问题，如 n < 100，这是因为每一步中计算方向的复杂度为

。

内点方法有限的可扩展性激发了最近对一阶方法的研究热潮。利用

”的迭代阈值算法进行类比，Cai等人开发了一种算法，通过反复收缩适当矩阵的奇异值来执行核范数最小化，本质上是将每次迭代的复杂性降低到一次SVD的代价。然而，对于低秩和稀疏分解问题，这种形式的迭代阈值分割收敛缓慢，需要多达

次迭代。Ma等人[20,36]建议使用连续技术改进收敛性，并证明了Bregman迭代[41]可用于核范数最小化。

利用Nesterov的光滑极小化一阶优化算法[37]的思想，迭代阈值法的收敛性也得到了很大的改善，该算法在[2，38]中扩展到了非光滑优化，并在[2，3，39]中应用到了

。基于[2]，Toh等人开发了一种用于矩阵补全的近端(proximal)梯度算法，他们称之为加速近端梯度(APG)。文献[33]提出了一种非常相似的APG算法用于低秩稀疏分解。该算法继承了这类问题的最优

收敛速度。经验证据表明，这些算法解决凸PCP问题的速度至少比直接的迭代阈值化快50倍(更多细节和比较，请参阅[33])。

然而，尽管APG具有良好的收敛性保证，但它的实际性能在很大程度上取决于良好的可扩展框架的设计(the design of good continuation schemes)。通常的可扩展性不能保证在广泛的问题设置中具有良好的准确性和收敛性(根据我们的经验，最优选择可能取决于L和S分量的相对大小和缺失数据的稀疏性)。在本文中，我们选择使用[32,51]中引入的增广拉格朗日乘子(ALM)算法来代替凸PCP问题(1.1)。在我们的经验中，与APG相比，ALM以更少的迭代次数获得了更高的精度。它在不调整参数的情况下稳定地运行在各种问题设置中。此外，我们观察到一个吸引人的(经验的)特性：在整个优化过程中，迭代的秩经常保持在

的范围内，这使得它们的计算特别有效。而APG没有这个属性。

ALM方法对增广拉格朗日函数进行运算：

一般的拉格朗日乘子算法[5]通过反复设置

来求解PCP，然后通过

更新拉格朗日乘子矩阵。对于低秩稀疏分解问题，通过recognize

和

都有非常简单和有效的求解方案，我们可以避免一系列凸优化问题的求解。让

表示收缩算子

，对每个元素应用该算子，将其扩展到矩阵的形式。容易得到

类似地，对于矩阵X，让

表示奇异值阈值运算符

，其中，

是任何奇异值分解。容易得出

因此，一个更实际的方案是先(固定S)，关于L最小化l，然后(固定L)，关于S最小化l，最后基于残差

更新拉格朗日乘子矩阵Y。方案总结如下算法1。

算法1是一种更一般的增广拉格朗日乘子法，常称为交替方向法的特殊情况。这些算法的收敛性已经得到了很好的研究(见e.g.[29,34]和其中的许多参考文献，以及[32,51]中的讨论)。算法1在很多问题上都有出色的表现：正如我们在第3节中看到的，相对较小的迭代次数足以获得较好的相对精度。每次迭代的主要代价是通过奇异值阈值法计算

。这就要求我们计算

的大于阈值μ的奇异值对应的奇异向量。根据经验，我们观察到这样大的奇异值的数量通常是由

限制的，从而允许通过部分SVD有效地计算下一个迭代(如[20]中核范数最小化所建议的，用近似SVD替换部分SVD可能会进一步提高性能)。该算法最重要的实现细节是μ的选择和停止条件。本文，如[51]建议的那样，我们简单地取

。当

时，终止算法。

类似的思想可以用于开发简单有效的增广拉格朗日乘子算法，用于矩阵补全[32]，以及在1.6节中讨论的鲁棒矩阵补全问题(1.5)，同样具有良好的性能。在上一节中，所有的模拟和实验都是使用基于ALM的算法进行的。更深入的讨论，实现细节和与其他算法的比较，请参见[32,51]。

6 讨论

这篇论文提供了一些相当令人惊讶的消息：我们可以通过凸规划精确地分解低秩和稀疏分量，并且在非常广泛的条件下，这被证明是有效的，比现有一些有最好结果的算法所提供的更广泛。此外，我们的分析揭示了矩阵补全和矩阵恢复(从稀疏误差)之间相当密切的关系，我们的结果甚至可以推广到同时存在不完整和损坏项的情况下(即定理1.2)。此外，PCP没有任何自由参数，可以用简单的优化算法求解，效率和精度显著。更重要的是，我们的结果可能为新的理论和算法问题以及现在可以系统地研究的新的实际应用提供了更广阔的空间。

到目前为止，我们的研究仅限于低秩分量恰好是低秩的，稀疏分量恰好是稀疏的。这将是一个有趣的调查：当其中一种假设或这两种假设都被放宽时的结果会是怎样。一种思考方法是通过新的观测模型

，其中，

是一个密集的小扰动，它说明了低秩分量只是近似低秩的事实，并且小的错误可以加到所有的项上(在某种意义上，该模型结合稀疏gross误差和密集小噪声，统一了经典PCA和鲁棒PCA)。在[7]中发展的关于小扰动下矩阵补全稳定性的思想在这里可能是有用的。更普遍的是，稀疏信号恢复、低秩矩阵补全、经典PCA和鲁棒PCA等问题都可以看作是下面这个一般测量模型的特殊情况：

其中

是已知的线性映射。一个雄心勃勃的目标可能是确切地了解在什么条件下，可以通过凸规划有效地从这些有噪声的线性测量中检索或分解
$S_{0}$
和
$L_{0}$
。

凸优化在恢复高维空间中的低秩矩阵和稀疏信号方面的卓越能力表明，它们将成为处理图像/视频处理、网络数据分析和生物信息学中出现的海量数据集的强大工具。这类数据通常有数百万甚至数十亿维，因此计算和内存开销可能远远超过一台典型的PC。因此，未来研究的一个重要方向是开发具有更好可伸缩性的算法，并且可以在新兴的并行和分布式计算基础设施上轻松实现。