低秩自表示子空间聚类

  • 1. 简介
  • 2. 最佳秩 k 表示
  • 3. 缺失数据下低秩表示的不适定性
  • 4. 低秩表示的正则化方法
  • 5. 引用

1. 简介

子空间聚类的总体介绍请移步这里

稀疏表示的子空间聚类方法对于含高斯小噪声比较有效,但是对含有错误、稀疏大噪声的数据非常敏感。低秩子空间聚类是通过构建低秩矩阵 $X$,逼近原始数据矩阵 $A$,得到数据的子空间表示。从另外一个角度理解,原来 $rank(A)$ 维的数据就被降到了 $rank(X)$ 维。

何为低秩?如果数据矩阵表达的是结构性信息,即矩阵的行列数据之间存在一定的相关性,那么这个矩阵是含有冗余信息的,可以用一个低秩矩阵近似表示。

2. 最佳秩 k 表示

详见这篇文章

3. 缺失数据下低秩表示的不适定性

适定性条件:存在、唯一、稳定($x$ 变化很小,$y$ 变化也不大)

不满足适定性条件之一,则为不适定问题。

e.g. 求积分-适定,求导-不适定(受扰动干扰很大);生成训练数据-适定,数据拟合曲面-不适定(可能有多解)。

低秩逼近的不适定性,也就表现在以上两个方面。

选择特定的范数,可以消除不适定性:矩阵范数衡量的就是矩阵引起变化的大小,因此对范数约束,即使解更加稳定。

4. 低秩表示的正则化方法

求带稀疏噪声 $E$ 的数据 $D$ 的低秩表示 $A$,可构造双目标优化问题:

$$\begin{aligned}
\begin{cases}
\mathop{\min_{A,E}} \|E\|_F\\
rank(A) \le r
\end{cases}
\quad s.t. \; D = A+E
\end{aligned}
$$

引入 trade off parameter $\lambda$:

$$\mathop{\min_{A,E}} rank(A) + \lambda \|E\|_F \quad s.t. \;D=A+E$$

$rank(A)$ NP 难,不好求,松弛成核范数:

$$\mathop{\min_{A,E}} \|A\|_* + \lambda \|E\|_F \quad s.t. \;D=A+E$$

为了解决不适定,再加入一个 l2 正则:

$$\mathop{\min_{A,E}} \|A\|_* + \lambda \|E\|_F +\mu(\|A\|^2_F + \|E\|^2_F)\quad s.t. \;D=A+E$$

最后再用拉格朗日乘子 $Y$ 将等式约束松弛到目标函数之中,得到最后的拉格朗日函数:

$$L(A,E,Y) = \|A\|_* + \lambda \|E\|_F +\mu(\|A\|^2_F + \|E\|^2_F) – \phi<Y,D-A-E>$$

以上就是低秩表示的问题描述。其中关于核范数、l2 范数的详细介绍可见我这篇文章。而关于这个问题的解,请见后文(马上写)。

5. 引用

[1] 孙素敏,“子空间聚类及其应用”,西安建筑科技大学硕士学位论文

[2] 赵科科,“低秩矩阵分解的正则化方法与应用”,浙江大学博士学位论文

[3] 机器学习的数学原理之——不适定问题的计算方法(一))

[mathjax]

Leave a Comment

电子邮件地址不会被公开。