Robust Subspace Segmentation by

2019-01-11 本文已影响1人 hzb_ml

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维的欧几里得空间中，将所有的数据向量放入到他们各自的子空间中。

两种假设：

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

在这两种假设前提下，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

使用 $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}$

使用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}$

优化步骤

完整步骤如上图。