《Robust Recovery of Subspace Structures by》由会员分享，可在线阅读，更多相关《Robust Recovery of Subspace Structures by（27页珍藏版）》请在金锄头文库上搜索。
1、Robust Recovery of Subspace Structures byLow-Rank Representation摘要：本文讨论子空间聚类问题。给定一个数据集样本，近似的来自于多个子空间的联合。目的是把样本聚类到各自的子空间，然后去除极端值点。最后，提出一个新的目标函数：低秩表示，他能够在样本中找寻低秩表示，即能够把样本表示为给定字典中基的线性组合。凸问题结合低秩表示能够解决如下的子空间聚类问题：1.当数据很干净无噪声时，低秩表示能恢复真实的子空间结构；2.当数据包含异常值，在确定的条件下，低秩表示可以恢复原始数据的行空间以及发现异常值；3.当数据包含稀疏噪声时，低秩表示在理论上
2、可以近似恢复行空间。既然子空间关系被行空间所决定，也就意味着低秩表示可以精确高效大的用作鲁棒子空间聚类和误差修正。关键词：低秩表示；子空间聚类，分割，异常值检测引言：在模式分析和信号处理中，基本原则是数据经常由几种类型的结构组成，能够被用来智能表示和处理。所以，就需要一个参数模型来描述给定的数据集。常见的（线性）子空间是最常用的选择，主要是因为她们很容易计算而且在实际应用中很有效。一些类型的可视数据，如：运动、人脸和纹理等，已经被子空间所表示。而且，通过使用再现核希尔伯特空间，就可以把线性模型推广到处理非线性数据上。所以子空间问题得到了很大的重视。例如,使用广泛的主成份分析，以及最近建立的矩阵
3、完备和恢复，这些都是基于数据近似的来及低秩的子空间这样的假设。然而，给定的数据很少能被一个单一的子空间所描述。一个更合理的模型是考虑数据分布在多个子空间中，也就是说数据可以看作来自多个低秩子空间的样本。子空间的普遍性和重要性引出一个非常有挑战性的问题：子空间分割（或聚类），目的是把数据分割成多个簇，每个簇和一个子空间相关。子空间分割是一个重要的数据聚类问题，在很多领域得到应用，包括计算机视觉、图像处理和系统识别等。当数据很干净时，比如样本直接来自子空间，有一些现存的方法来解决子空间分割。所以，就像论文3和14中说的那样，子空间分割最大的挑战是处理数据中存在的错误（比如噪声和扰动），比如处理那些
4、并不是直接遵循子空间结构的数据。有了这个观点，在本文中，我们研究如下的子空间聚类问题：问题1.1、（子空间聚类）：给定一个来自线性组合的子空间的样本数据集，修复错误的同时把他们分割到各自的子空间中。注意到，error这个词一般意味着假设模型（子空间）和数据之间的偏差。通常表现为噪声、丢失的数据、异常值和扰动等。图2说明了三种典型的error在子空间模型中。本文中，重点放在图（c）的情况上。而对于前面两种只做初略的讨论。注意到，一个异常是一个不同于子空间的模型，也不同于属于子空间的受到污染的数据。我们把他们放在同一个策略下考虑是因为她们可以用同样的方法处理，在V-B这一节中做介绍。为了从包含er
5、ror中的数据恢复出子空间结构，本文提出了一个新的方法，叫做低秩表示。给定一个样本数据集，里面的每一个样本都可以用字典里的基线性表示，低秩表示的目的是找到所有的数据的最低秩表示。低秩表示的计算过程是解决一个核范数正则化最优化问题，这个问题是凸的而且可以用多项式来求解。通过选择一个特别的字典，低秩表示可以很好的解决子空间聚类问题：当数据是干净的时候，低秩表示可以精确的恢复数据的行空间；对于包含异常值的数据，在一定的条件下，低秩表示可以精确的恢复原始数据的行空间以及发现异常值；对于被随机error污染的数据，理论证明低秩表示可以近似的恢复行空间。既然所有的子空间被证明是由行空间决定（将在III-B
6、节中讨论），也就意味着低秩表示可以进行鲁棒子空间聚类和修正错误。本文的主要贡献为：本文提出了一种简单且有效的方法，叫做低秩表示（LRR），这种方法在很多应用上（如运动分割、图像分割、显著性检测、人脸识别）得到了很好的效果。本文的工作可以从在单一子空间中恢复被污染的数据扩展到多个子空间中。和文献【20】（需要知道子空间的基来处理多个子空间中的被污染的数据）相比，本文的方法更具有自主性，即不需要额外的干净的数据。提供了鲁棒恢复的结果。本文的分析使用和矩阵完备及鲁棒主成份分析中相同的特征，这样更具有挑战性，因为在LRR中存在一个字典。II、相关工作在这一节中，本文讨论一些现存的子空间分割方法。一般的
7、现存的方法可以分为如下的四个主要的种类：高斯混合模型、分解、代数和光谱型的方法。在概率学习中，混合的数据典型的被建模为来自于混合概率模型的一个独立样本集。因为单独的子空间可以表示为一个（退化的）高斯分布，那么可以进一步假设每一个概率分布都是高斯分布，比如说采用混合高斯模型。然后数据分割问题就转换为一个模型估计问题。这种估计可以使用期望最大化方法（EM）来找到最大的邻域估计，或者通过迭代找到最小最大估计（如K-subspaces 和随机样本合一random sample consensus）。这些方法对error很敏感。所以一些工作用来提高她们的稳定性，比如说the Median K-flats
8、 22 for K-subspaces, the work 23 for RANSAC, and 5 use a coding length to characterize a mixture of Gaussian. 这些方法可能会引进一些鲁棒性。然而，这个问题仍然没有得到很好的解决由于优化的难度。这也是这些方法的一个瓶颈。基于分解的方法试图将给定的数据矩阵看作两个矩阵的和。为了对噪声具有鲁棒性，这些方法修改公式（增加额外的正则项）。然而，这样的修改通常导致非凸优化问题，就需要启发式的算法来解决（通常基于交替最小化或者EM算法）。陷入局部极值的问题可能破坏效果，特别是当数据严重损坏。低秩表示
9、将被看作是文献【12】(文章中看作PCA方法)中方法的鲁棒性归纳。低秩表示的公式是凸的而且可以在多项式时间内解决。广义主成份分析提出了一种代数方法对来自多子空间的数据建模。这种方法使用多项式在这个点的梯度来描述包含一个数据点的子空间。然后使用子空间分割也就是多项式拟合。广义主成份分析在特定的条件下可以确保成功的分割，而且在子空间不引入任何限制。然而，这种方法对噪声敏感，由于从真实数据中估计多项式是困难的，而且计算也要花费很大的时间。目前，鲁棒代数分解（RAS）被提出用来解决广义主成份分析（）的鲁棒性。然而，拟合多项式的计算复杂度是很大的。所以RAS只有在数据维度低和子空间个数小的情况下有用。作
10、为一个数据聚类问题，子空间分割可以首先从给定的数据中学习一个亲和度矩阵，然后得到通过特殊的聚类算法（ 比如归一化割（Ncut）得到分割的结果。许多现有的方法，例如稀疏子空间聚类，光谱曲线聚类，低秩表示等。主要的区别是学习亲和度矩阵的方法。在数据是干净的且子空间是独立的假设下，【13】表明稀疏表示的方法可以达到所谓的L1子空间检测性能（L1-SDP）：类内亲和力是稀疏的，类间亲和力都是0。在异常值存在的情况下，【15】指出SR方法可以遵循L1-SDP。然而，L1-SDP可能对确保子空间分割成功性不充分。当前，【34】证明在一定的条件下，多子空间结构可以通过Lp最小化精确的恢复。然而，既然这个方法
11、是非凸的，如何有效的得到全局最优化解仍然是未知的。相比之下，低秩表示的模式是凸的，而且相应的优化问题可以在多项式时间内解决。而且，尽管数据被异常值污染，所提出的低秩表示被证明精确的恢复正确的行空间，被证明决定子空间分割的结果（在III-B中讨论）。对于任意error的存在，低秩表示可以得到近似的恢复。III、准备工作和问题声明A、 主要符号总结在本文中，矩阵用大写字母表示。特别的I表示单位矩阵，矩阵的元素表示为和下标。例如，M是个矩阵，为了便于表述，水平（垂直）关于行和列可以表示为.由形成的块对角矩阵表示为: .等等表示. 矩阵的支撑是矩阵中非零元的索引, .矩阵是对于所有的将映射到0.B、
12、分割和行空间的关系假设Xo表示直接从联合多子空间中得到的数据样本，子空间的关系由Xo的行空间决定。的却，在【12】中，当子空间相互独立，形成对角矩阵:只有当第i个和第j个样本来自于同一个子空间，的（i,j）元素才不是0.因此，这个矩阵被用来做子空间分割。以前的方法简单的计算数据矩阵的SVD ，然后使用，做子空间分割。然而，当有异常值存在时，Vx偏离Vo很远（Vo是干净的），所以分割就不精确。相比之下，LRR可以恢复，即使数据矩阵X被异常值污染。如果子空间不相互独立，那么也就不严格是块对角型。这确实是好的预期，既然当子空间有非零的交叉点，然后一些数据样本就会同时属于多个子空间。当子空间两两不想交
13、（不是相互独立）时，数值实验表明和块对角矩阵很接近。所以恢复对子空间分割很有意义。C、 问题描述问题1.1只是初略的描述了所要研究的问题。更精确说明，本文解决如下的问题。问题3.1（子空间聚类）设有若SVD分解，保存有n个d维的样本直接来自于k个不知维数的联合子空间（k也未知）。给定一个观察向量集X，由下式产生：目标是恢复Xo的行空间，或者恢复。恢复行空间可以确保高的分割精度，在III-B中介绍。而且，恢复行空间也意味着修正error。所以把子空间聚类的目标定位为恢复行空间是充分的。便于说明，考虑下面这个问题在三个增加实用性和难度的假设下。假设1：数据是干净的。假设2：部分样本数据被严重污染，
14、其他的很干净，比如说Eo稀疏的列支撑。假设3：部分数据被严重污染，其他被高斯噪声污染。如图2中（a）和（C）的混合情况。不像文献【14】，本文不对子空间的独立性做强调。因为，本文的分析是恢复，而不是得到块对角矩阵。IV、低秩表示用于矩阵恢复本节将在理论上说明用了LRR从污染的观测数据矩阵中恢复矩阵。基本的定理和优化算法被提及。特殊的方法和理论来处理子空间聚类，将在V节讨论。A、 低秩表示为了从被error污染的给定观测矩阵X中恢复出低秩矩阵Xo，可以直接考虑下面的正则项，秩最小化问题：其中是参数，L 范数代表具体的正则化策略。比如说用于对图2（a）中噪声建模的平方F范数。Lo范数描述随机污染如
15、图2（b）中。L2，0范数处理样本特定瑕疵。假设是变量D的最小值，然后他给了一个低秩的恢复对于原始矩阵。上面的方法已经被RPCA所采用，在许多领域已经得到了好的效果。然而，这种方法含蓄的假设潜在的数据结构是一个单一的低秩子空间。当数据来自多个联合的子空间时，表示为：，它实际上将数据看作采样自一个单一子空间定义为：。既然的和比联合单元大得多，那么单个子空间的特殊性就没被考虑进去，所以恢复就不精确。为了更好的处理混合的数据，我们考虑一个更一般的秩最小化问题：式中A是一个dictionary，线性集合的数据空间。称最小因子Z*（对于变量Z而言）为数据X在字典A下的最低秩表示。在得到最优的结果后，就可
16、以使用AZ*或X-Z*恢复原始数据。既然，那么AZ*也是原始数据Xo的低秩恢复。通过将A=I，公式（3）就变成公式（2）。所以LRR可以看作RPCA的一般情况，使用标准基作为字典。通过选择一个合适的字典A，最低秩表示可以恢复潜在的行空间一遍重现最真实的数据分割。所以LRR可以处理来自多个子空间联合的数据。B、 LRR问题分析优化问题公式（3）很难解决，由于秩函数的离散性。为了便于分析，我们假设数据无error。我们就考虑如下秩优化：很容易看到公式（4）的解不唯一。作为一个常用的秩最小化问题，用核范数来代替秩函数，得到如下的凸优化的问题：本文将表明（5）的解就是（4）的解。特殊解对子空间分类很有用。下面将说明（5）的一些有用性质。这些一般结论构成了LRR的基础。） 极小值的唯一
