引用

Ding T, Zhu Z, Vidal R, et al. Dual principal component pursuit for robust subspace learning: Theory and algorithms for a holistic approach[C]//International Conference on Machine Learning. PMLR, 2021: 2739-2748.

摘要

本文提出了双主成分追踪(DPCP)方法来从被破坏的数据中鲁棒地恢复高相对维数的子空间。然而，DPCP 现有的分析和算法主要集中在寻找包含内点的单个超平面的法线。尽管这些算法可以通过递归方法扩展到更高余维的空间，其中的递归方法顺序地找到与子空间正交的空间中新的基元素，但是该过程计算量大并且不能保证收敛。在这篇文章中，我们考虑了一种 DPCP 方法，通过求解一个非凸非光滑优化问题来同时计算正交补子空间的整个基(我们称之为拟线性方法)。我们提供了全局最优性的几何和统计分析，并证明了在无噪声和有噪声的情况下，它可以容忍与内点数的平方一样多的异常值。然后我们给出了问题的黎曼正则性条件，然后用它来证明黎曼次梯度方法线性收敛到正交子空间的一个邻域，其误差与噪声水平成正比。

1 引言

从高维受损数据中鲁棒地学习线性子空间已经成为机器学习、模式识别和计算机视觉中的一个基本问题。真实数据中通常会出现两种形式的损坏-异常值和噪声。

异常值和噪声：与精确位于子空间中的内点不同，异常值远离子空间，并且不呈现线性结构。数据中的噪声意味着内点受到干扰，因此它们靠近子空间或位于子空间上，也就是说，它们不再是内点。数据集的这种损坏给子空间恢复任务带来了巨大的挑战。

在过去的十年中，在高维数据可以被低维结构很好地模拟的前提下，已经出现许多稳健的子空间恢复(RSR)方法。它们通常用凸优化求解。然而，理论和算法的保证是为具有 d<< D 其中 d 和 D 分别是子空间维数和环境维数。在 d/D≈1 的高相对维度区域，这一点可能无法被保证。我们还观察到，在 ImageNet 中，从单个对象类别的图像中提取的深度特征所跨越的子空间具有较高的相对维数，这使得现有的离群点检测方法在理论上不适用 ImageNet。

双主成分追踪(DPCP)是一种 RSR 方法，被开发用于直接处理高相对维数区域，因为它估计了 S⊂RD 子空间的正交补的基，用于解决球面上的非凸 L1 问题:

然而，问题（1）只能找到单个超平面的法线，同时恢复余维 c=D −d>1 需要递归应用（1）c 次，每次都要找到一个与先前计算的法向量正交的法向量。该过程计算量大，缺乏收敛性分析。此外，递归过程中累积的错误会导致其行为难以被分析。

本文考虑通过以下公式同时估计正交补子空间 S⊥ 的整个基

与问题(1)的递归方法相比，我们称问题(2)为递归方法。请注意，(2)是(1)的自然扩展，它寻找一个正交列与尽可能多的数据点正交的矩阵。我们注意到(2)是 Grassmannian (D，c)上的一个优化问题，即维数子空间 RD 上的集合，因此其本质上是非凸的。RecentlyZhu 等人提出了一种求解广义非凸优化问题的黎曼次梯度方法(RSGM )，然而目前我们还不清楚类似的情况在嘈杂的环境中是否成立。

此外，有理由问在当不存在噪声时在什么样的条件下(2)的每个全局解 B*都是 S⊥ 的正交基，或者当数据有噪声时，Span(B∗)和 S⊥ 之间的主角度是如何作为噪声级的函数来工作的。

贡献：我们在无噪声和有噪声环境下为非凸 DPCP 问题(2)的全局可估计性提供几何和统计分析。我们证明了在无噪声数据的情况下，在一定条件下,(2)的任何全局解 B*都是 S⊥ 的正交基。随着数据集被噪声进一步污染，我们表明 Span(B*)和 S⊥ 之间的子空间角度的上限与噪声水平成比例。在这两种情况下，我们推导出的概率参数表明，DPCP 问题(2)可以处理 M=O(N2)异常值，这优于理论上可以容忍最大 O(N)异常值的其他现有 RSR 方法。此外，我们证明了在适当的初始化条件下和几何递减步长选择下，RSGM 线性收敛到与噪声水平成正比的 S⊥ 的邻域。在合成数据上的实验表明，整体方法(2)与递归方法(1)以及其他 RSR 方法相比，在高相对维数范围内表现的更加良好。

2相关工作

主成分分析(PCA)是将线性子空间拟合到数据的传统方法。主成分分析即使在数据有噪声的情况下也能很好地工作，但是当数据集被异常值破坏时，它就受到限制，因为主成分分析中基于 L2 的 loss 对异常值很敏感。另一个经典的方法是 RANSAC，它在时间预算内从随机采样点重复估计子空间，然后根据被分类为内点的点的数量输出最佳结果。

近年来出现了许多 RSR 方法，最小化所有数据点和子空间之间的距离之和——正是本文中考虑的公式(2)。这些现有的方法大多是为低相对维数的情况(d<< D)进行设计的。与这项工作并行的是，他们考虑用 G(D，d)代替 G(D，c)来解决非凸优化问题。

很多 RSR 方法的理论保证通常在高相对维数范围(d/D≈1)内变得不再适用，并且算法的计算变得昂贵，因为在 G(D，d)上的优化是非常低效的。据我们所知，DPCP 是唯一直接针对恢复高相对维度子空间的方法。Tsakiris & Vidal 首先通过求解(1)介绍了递归学习 S⊥ 上的基的思想。朱等人利用可解释的更紧的几何量改进了(1)的分析，并首次证明异常值可以被处理。此外，他们还提出了一种有效的投影次梯度方法，该方法在适当的初始化条件下线性收敛。到目前为止，基于求解(1)的 DPCP 先前工作需要计算包含内点的单个超平面的法线，当其递归地应用于寻找更高余维的 S⊥ 空间上的新基元时，事情就会变得麻烦且低效。我们的工作通过提出一种整体方法成功地解决了这个问题，该方法同时计算了 S⊥ 上的整个基，并在无噪声和有噪声环境下提供了(2)的全局最优性和收敛性理论。

3背景

本文考虑的设置是单位 L2 范数数据集 X' =[X+EO]T∈Rd×L，其中 X= [x1…xN]∈ RD×N 是在 d 维子空间 S 内的内点，E= [e1…en]∈RD×N 是加在内联体上的加性噪声，O= [o1… oM]∈RD×M 不呈现线性结构的内点中的离群点，T 是未知的置换矩阵。我们的目标是从损坏的数据中恢复底层子空间。我们让 c:= D-d 记下 S 的余维。因为我们对 c<< d 的高相对维度机制感兴趣,直观地说，在无噪声的情况下(E=0)，如果 B 是 S⊥ 的一个正交基，那么(2)中的 f(B)只依赖于异常值，并且对选择不敏感，因为异常值是非结构化的，这启发了我们的公式(2)。我们用集合 O(D，c) :={B∈RD×c:BTB= I}中的正交矩阵来参数化 Grassmannian G(D，c)。特别地，当 c= 1 时，我们也使用 SD-1，即单位球，作为 O(D，1)的替代。此外，为了简单起见，我们使用 O(c)来表示 O(c，c)。让 S⊥∈O(D，c)是 S⊥ 的正交基。由于(2)中的 f 是旋转不变的，我们考虑矩阵的等价类。特别地，对于 U，V∈G(D，c)，如果 Span(U) = Span(V)，那么我们认为 U 是等价于 V ，使用 U 来表示等价类[U] :={UR:R∈O(c)}。由于数据集被噪声污染，解决方案 B 预计会从 S⊥ 处受到扰动，这可以通过测量两个子空间之间的主角度进行几何测量。

定义一：

有了定义 1，我们就能计算出 Span(B)和 Span(S⊥)=S⊥ 之间的距离。特别是，当 Span(B) =S⊥，我们有 θ1(B,S⊥) =….. =θc(B,S⊥) = 0，这意味着他们的子空间角度为零，从而证明了定义。

对于与任意 a∈Rc 的||a||2 的次微分由下式给出：

集合 Sgn(a)中特别感兴趣的一个元素是:

由于优化问题(2)被置于 Grassmannian G(D，c)之上，我们将(2)的最优性条件与黎曼几何联系起来。用 ∂f 来表示黎曼次微分学， ∂f(B) = (I−BBT)∂f(B)，即将 ∂f(B)投影到 B 中的切线空间的 G(D，c)。此外，当且仅当 0∈∂f(B)，B 是问题(2)的一个临界点，这将在下一节用来研究(2)的全局最优性。

4全局最优性分析

在本节中，我们分析了无噪声环境和有噪声环境中的非凸非光滑 DPCP 问题(2)。为此，我们首先定义了本文所考虑的随机球面模型。

定义二：

4.1无噪声设置

几何量：现在，我们介绍几个几何量，这些几何量描述了无噪声环境中的内点和离群点的分布。对于内点，我们有磁导统计量：

分布良好的内点会产生很大的 cx,min 值，要知道我们很难找到一个与大多数点正交的方向。对于异常值，我们通过定义将 Zhu 等人中余维 c= 1 的 ηO 量推广到更一般的情况。对于异常值，我们将共维数 c=1 的 ηO 量推广到更一般的 c 情形 ≥1，通过以下定义来实现：

利用上面的几何量，我们有下面的引理，它陈述了(2)的临界点的几何意义。

引理二：

引理 2 推广了特殊情况 c= 1。它认为在无噪声数据的情况下, （2）的任何临界点都跨越 S⊥ 或者跨越远离 S⊥ 的子空间. 请注意，对于均匀分布的内点和离群点，B∗ 的几何位置会变得更加受限。观察任何临界点 B∗ 使得 Span（B∗) 足够接近 S⊥（角度小于 θ），前提是必须满足 Span(B∗) =S⊥. 这激发了关于全局极小元几何的下一个结果。

定理一：

定理 1 是对超平面情形的扩展。首先请注意，根据(8)，当 M→∞ 时 cO,max,c- cO,min,c→0。然后(9)告诉我们，利用 M/N 和 c，只要我们有越来越多的分布良好的数据点，(9)就会被满足，(2)的任何全局解决方案都将得到满足。该结果用无噪声数据表征全局最优性。

定理二：

条件(10)用自然量如 n、M、D、D 和 c 来解释定理 1 的全局最优性条件(9)。它验证了在 Grassmannian G(D，c)上 DPCP 的新公式(2)仍然能够容忍 O(N2)异常值，而这些会用于恢复 S⊥ 上的整个正交基。

4.2噪声设置

我们现在考虑当内点 x 进一步被噪声污染时的情况，即定义 2 中的 σ> 0 和和 e！=0。我们分解噪声项为 e=es+en，其中 es 是 E 在 S 上的投影，En 是在 S⊥ 上的投影。观察项 es 与内点起着相同的作用，因为它的列正好位于 S 中，其中分量 en 是影响(2)的全局解的有效噪声。我们可以将(2)中的目标重写为:

几何量:首先注意，之前与异常值相关的量，即 ηO，c，cO，max，c 和 cO，min，c 保持不变。对于有噪声的内点，由于我们已经分离出了有效噪声，因此我们有以下两个关于 X’和 e’的额外量:

当 σ→0 时，我们知道 ρ(σ)→1 和 δ(σ)→0。 特别地，当 nσ= 0(E=0)时，cx’,min 的上述结果与 cx,min (8)的结果相同，但是对于 ce’,max,c 它并不能立即表明 ce’,max,c=0。

引理四：

满足条件(16)的(RO/X’，c，RE’/bX，c)的可行区域在图 1 中显示为曲线下的区域，这意味着离群值与内点之比和噪声与内点之比不能同时是一个很大的值。

接下来，可以证明四次方程（19）必须有两个非负根（t1 较小的情况），条件（16）确保 t1≤t2。 然后，(17) 表明噪声问题 (2) 的任何临界点 B∗ 跨越一个接近 S⊥ 或 S 的子空间。图 1 提供了对 t1 和 t2 的更好理解：具有更小的异常值与异常值比率和噪声与内点比，t1 更接近 0（更亮），t2 更接近 1（更暗），使得 B*的几何位置更受限制。与无噪声情况下的引理 2 相比，如果 B∗ 是 S⊥ 的精确正交基，且它离 S 足够远，由于噪声这里我们只能保证它位于 S⊥ 的邻域内，即 θ∗c≤sin− 1(t1)。可以通过以下方式进一步约束 t1

当没有噪声时，从(20)我们得到 t1= 0。此外，当离群值与内点之比和噪声与内联值之比都很小的时候(20)表明 t1 很小，并且与有效噪声水平成比例。最后，与 c = 1 的噪声问题的临界点分析相比，这里使用的证明技术是不同的，因为问题(2)是在 Grassmannian 上定义的，这需要考虑 G(D，c)中子空间的几何性质。特别地，在丁等人中，t1 和 t2 都由(19)的非负根定义，而在该广义分析中，t2 与(19)解耦。

使用引理 4，我们现在可以刻画噪声 DPCP 问题(2)的全局解

定理三：

条件(21)足以确保(2)的全局解跨越接近 S⊥ 的子空间。我们对(21)的解释如下:在固定 M/N 的情况下，由于数据点不断增加(cO，max，c- co，min，c→ 0)且分布均匀(cx’，min 较大，RO/ X‘，c 较小)，且有效噪声较弱(RE’/ X’，c 较小)，(21)将得到满足，且(2)的全局解必须接近 S⊥。接下来，我们给出它的概率特征。

定理四：

我们注意到当 σ = 0 时，条件(23)不一定具有条件(10)的相同形式，或者当 c = 1 时，条件(23)不一定具有丁等中的条件，因为技术证明细节不同。然而，它们都揭示了 DPCP 问题能处理的异常值，这与理论上只能处理 O(N)异常值的其他 RSR 方法相比是一个明显的优势。

注意，我们专注于学习一个高相对维数的子空间，其中 d/D ≈ 1，余维 c = D-d 非常小。因此，本节中导出的理论保证非常适合 c = O(1)的情况。

特别是，当 c=1 时，DPCP 问题简化为球体上的优化问题。一般来说，对于非常大的 c，例如 c=O（D），DPCP 方法只能处理少量的异常值。事实上，由于子空间现在是低维的，因此针对低维子空间设计的方法更合适。

5 投影黎曼次梯度法的收敛性分析

在这一节中，我们研究了由算法 1 给出的投影黎曼次梯度法(RSGM)，其用于求解格拉斯曼 G(D，c)上的 DPCP 问题(2)。分析结果不能立即推广到有噪声的情况，在这种情况下，人们只能期望它最好收敛到 4.2 节中有噪声分析所建议的 S⊥ 附近。我们将表明，当数据被噪声破坏时,( 2)的 RRC 仅在半径与有效噪声水平成比例的 S⊥ 邻域之外成立，然后用于表明 RSGM 线性收敛到 S⊥。

我们将任意 A，B ∈ O(D，c)之间的距离定义为：

命题一：

命题 1 说明了 θc(A，B)和 dist(A，B)在表征 A 和 B 彼此有多接近方面是等价的，而后者便于我们的收敛性分析。让 S⊥ 作为 S⊥ 的一个正交基，我们证明了 DPCP 问题(2)满足 S⊥ 环形邻域中的特定 RRC。

首先，dist(B,S⊥)的下限 ω 导致 S⊥ 周围的区域的 RRC 无法被保证，并使得整个引理减少到无噪声情况，其中半径 ω 与有效噪声水平成比例。我们注意到(26)给出了 τ 的有效范围，从而确保了(27)的有效性。给定 dist(B,S⊥)∈|ω，τ|，RRC 条件(28)指出负黎曼次梯度 G(B)与 B 中的指向 S⊥ 的方向有一个小角度。RRC 条件给出||G(B)||F≥ α，这意味着 ξ ≥ α。利用引理 5 中陈述的问题(2)的 RRC，我们提供了 RSGM(算法 1)的收敛性分析，其具有更新步长的两种不同策略:恒定步长和几何递减步长。

命题二：

命题 2 表明，在步长不变的情况下，如果正确的初始化，那么算法 1 确保收敛到 S⊥ 邻域。如果 dist(Bk,S⊥) > uξ2/α + ω，那么Bk将更接近 S⊥ 直到迭代进入 dist(Bk,S⊥) ≤ uξ2/α + ω 的区域，此后不再进一步衰减。此外，更大的步长 u 导致 Bk 更快地收敛到更大的 S⊥ 邻域。

我们现在考虑减小步长。

定理五：

利用算法 1 中的几何递减步长策略，定理 5 表明具有适当初始化的 RSGM 以线性速率收敛到 S⊥ 的邻域，其半径 ω 与有效噪声水平成比例。我们注意到 dist(Bk,S⊥)的衰减率是由递减因子 β 决定的。较大的 β 可能导致收敛速度较慢，而较小的 β 可能导致发散。

此外，如果不存在噪声，我们有 ω = 0，这意味着线性收敛到 S⊥。上述讨论在图 1a 和 1b 中展示。当应用于问题(2)时，我们还证明了余维 c = D-d 对 RSGM 的影响。如图 1c 和 1d 所示，对于不同的变量 c，RSGM 表现出类似的模式:在无噪声数据的情况下它线性收敛于 S⊥，并当噪声水平适中收敛于 S⊥ 附近。

图 1： DPCP关于噪声问题的收敛性

然而，由于 GGD 的目标问题与（2）相似，只是它学习的是 S 的基而不是 S⊥, 我们还应用 GGD 学习 S⊥ 的基, 称之为 GGD-dual。我们进行了 D=1000、c=50 和 N=10D 的实验，并绘制了在改变离群值比 M/（M+N）和噪声水平 σ 时（对偶）子空间的真值基与通过不同方法计算的基之间的距离的相变。

如图 4 所示，主成分分析和 REAPER 是测试中最没有竞争力的方法。我们推测 REAPER 作为 RSR 方法表现不佳，因为它需要更多的内点来使潜在的凸松弛有效(与 GGD 和 DPCP 使用的非凸方法相反)。接下来，GGD、GGD-dual 和 DPCP-holistic 在准确估计真值基方面表现相似。然而，GGD 需要更长的时间，因为它优化了 G(D，d)，而这在高相对维度区域是低效的。我们看到，应用 GGD 学习 G(D，c)中的对偶子空间，即 GGD 对偶，这样要快得多。最后，我们注意到基于用 RSGM 求解(1)的递归 DPCP 方法由于其计算成本而显得非常缓慢。我们的结论是，我们所提出的整体 DPCP 方法在相对维度较高的情况下表现优于竞争对手。

6结论

我们考虑了一种整体的对偶主成分追踪(DPCP)方法，用于学习在高相对维数区域中的鲁棒子空间，该方法包括在格拉斯曼基础上的非凸优化，同时估计正交补子空间的整个基。我们提供了全局最优性分析，并表明它可以在无噪声和有噪声的环境中处理 O((# inliners)2)个异常值。我们还证明了 RSGM 方法线性收敛到正交补子空间的邻域，其区域与噪声水平成正比。

我们未来工作的主题可能是将整体方法扩展到多个子空间。

致谢

本文由南京大学软件学院 2021 级硕士陈伟翻译转述,刘子夕审核。