Robust Subspace Segmentation by

作者: hzb_ml | 来源:发表于2019-01-11 12:01 被阅读1次

    Robust Subspace Segmentation by Low-Rank Representation

    使用低秩表示(LRR)分割从多个线性(或affine)子空间中得到的数据。给定一组数据向量情况下,LRR寻找秩最低的表示。Sparse representation(SR)计算每个数据向量的最稀疏表示,而LRR是找到向量集合的最低秩表示。

    Problem Formulation

    给出从未知维度的子空间中提取的足够密集的数据向量集合:X = \left[ x _{ 1 } , x_ { 2 } , \cdots , x _ { n } \right],每一列是一个样本,然后我们尝试在一个D维的欧几里得空间中,将所有的数据向量放入到他们各自的子空间中。

    两种假设:

    1. 子空间子空间是低秩和独立的,数据是低噪声的。
    2. 一小部分数据向量被噪声破坏或被异常值污染(包含稀疏和有适当界限的误差)。

    在这两种假设前提下,LRR是非常健壮的。

    Subspace Segmentation via LRR

    Low-Rank Representation

    给定一组足够密集的数据向量X = \left[ x _{ 1 } , x_ { 2 } , \cdots , x _ { n } \right](每一列是一个样本),可以被\mathbf{A}中基的线性组合表示X = A Z。其中Z是系数矩阵,A是一个dictionary。稀疏表示(SR)不能捕获数据的全局结构。

    寻找一个合适的\mathbf{Z}去解决

    \begin{array} { l } { \min _ { Z } \operatorname { rank } ( Z ) } \\ { \text { s.t., } X = A Z } \end{array}

    将最优解Z ^ { * }成为数据X关于字典A的低秩表示(LRR)。因为秩函数的离散性,上述优化很难解决,我们将上述问题转换为以下替代问题:

    \begin{array} { c } { \min _ { Z } \| Z \| _ { * } } \\ { \text { s.t. } , X = A Z } \end{array}

    \| \cdot \| _ { * }表示核范数。

    The Basic Messages

    为了将数据分割到各自的子空间中,我们需要计算一个affinity matrix来编码数据向量之间的成对关联。我们用数据X它自己作为字典。得出:

    \begin{array} { c } { \min _ { Z } \| Z \| _ { * } } \\ { \text { s.t. } , X = X Z } \end{array}

    这个是总是有解的,然后证明了总是存在这样的一个解,他是一个成块的对角矩阵。

    Z ^ { * } = \left[ \begin{array} {} { Z _ { 1 } ^ { * } } & { 0 } & { 0 } & { 0 } \\ { 0 } & { Z _ { 2 } ^ { * } } & { 0 } & { 0 } \\ { 0 } & { 0 } & { \ddots } & { 0 } \\ { 0 } & { 0 } & { 0 } & { Z _ { k } ^ { * } } \end{array} \right] _ { n \times n }

    这里,这个定理不能保证他的任意一个最优解都是块对角(block-diagonal)矩阵(最优解不唯一),只证明了存在一个最优解,他是一个成块的对角矩阵。但是在作者的实验中,所得到的解始终是块对角矩阵。

    Robustness to Noise and Outliers

    对小噪声甚至严重损坏或部分观察缺失,最合理的策略是放宽约束,得到以下目标函数:

    \begin{array} { c } { \min _ { Z , E } \| Z \| _ { * } + \lambda \| E \| _ { 2,1 } } \\ { \text { s.t.. } X = X Z + E } \end{array}

    \ell _ { 2,1 } - \mathrm { norm }鼓励E的列成为0,这里的假设是样本损坏只发生在特定样本。优化结束后我们就可以重构无噪声数据。

    Solving the Optimization Problem

    1. 使用J替换Z

    \begin{array} { c } { \min _ { Z , E , J } \| J \| _ { * } + \lambda \| E \| _ { 2,1 } } \\ { \text { s.t. } X = X Z + E } \\ { Z = J } \end{array}

    1. 使用ALM求解:

    \begin{array} { c } { \min _ { Z , E , J , Y _ { 1 } , Y _ { 2 } } \| J \| _ { * } + \lambda \| E \| _ { 2,1 } + } \\ { \operatorname { tr } \left[ Y _ { 1 } ^ { t } ( X - X Z - E ) \right] + \operatorname { tr } \left[ Y _ { 2 } ^ { t } ( Z - J ) \right] + } \\ { \frac { \mu } { 2 } \left( \| X - X Z - E \| _ { F } ^ { 2 } + \| Z - J \| _ { F } ^ { 2 } \right) } \end{array}

    优化步骤

    完整步骤如上图。

    相关文章

      网友评论

        本文标题:Robust Subspace Segmentation by

        本文链接:https://www.haomeiwen.com/subject/djxxdqtx.html