logo资料库

Robust Recovery of Subspace Structures by Low-Rank Representatio....docx

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

    相关推荐

    资料库

    信息化

    共收录1827份资料，累计6个分类，关注成员有19位，主要包括：管理软件,企业管理,电子商务,其它,IT管理,项目管理

    热门标签

    管理软件 企业管理 电子商务 其它 IT管理 项目管理

    最新资料