低秩矩阵分解

2020-05-15

低秩表示子空间聚类

目录 展开

1. 简介

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

本文介绍无噪声无异常数据 $A$ 的低秩逼近，并证明最优解.

2. 最佳秩 k 逼近

用低秩矩阵 $X$，逼近原始数据矩阵 $A$ 的最优化问题：

$$
\begin{aligned}
\mathop{\min}\limits_{r(X)\le k}\quad \|A-X\|^2_F
\end{aligned}
\tag{2.1.1}
$$
其中 $F$ 范数为 $\|A\|^2_F = \sqrt{\sum_i\sum_j|a_{ij}|^2}$

最优解为

$$
\begin{aligned}
X_k = \sum_{i=1}^k \delta_iu_iv_i^T = U_1 \Sigma_1V_1^T
\end{aligned}
$$

其中 $\Sigma_1 = diag(\sigma_1,\sigma_2,···,\sigma_k)$ 为 $A$ 的最大 $k$ 个特征值构成的对角矩阵；

$U_1 = [u_1,u_2,···,u_k],V_1 = [v_1,v_2,···,v_k]$ 为 $A$ SVD 分解的最大 $k$ 个特征值对应的左右特征向量。

下面是它的证明$^{[2]}$。

2.1 最佳秩 k 逼近的证明

若矩阵 $A$ 中的所有元素 $a_{ij} \le 0$，则记为 $A\preceq 0$。若 $A-B\preceq 0$，则记为 $A\preceq B$。令 $e$ 为单位列向量，$I$ 为单位方阵。

引理 1： 若 $n$ 阶非负矩阵（每个元素都 $\ge 0$）$W$ 满足

$$W \cdot e \preceq e, e^TW \preceq e^T \text{（即 } W \text{的每行、每列之和均 } \le \text{1）}\tag{2.1.2}$$

则对任意两个元素分别递减的 $n$ 维非负列向量 $a,b$ 满足

$$a^T(I-W)b \ge 0$$

证明： 先构造矩阵序列 $Q_1,Q_2,···,Q_n$ 其中 $Q_t$ 为 $t\times t$ 方阵，$Q_1 = 0$。对于 $Q_t$ 中的元素 $(Q_t)_{ij}$，有

$$(Q_t)_{ij}=
\begin{cases}
\max\lbrace \sum_{k\ne j,k \le t}w_{jk}, \sum_{k\ne j,k \le t}w_{kj} \rbrace& i=j \\
-w_{ij}& i \ne j
\end{cases}
$$

解释一下：$Q_t$ 的对角线 $(Q_t)_{ii}$ 是 $Q$ 前 $t \times t$ 的第 $i$ 行之和再加上 $-w_{ii}$，或者第 $i$ 列之和再加上 $-w_{ii}$；其余位置就是 $-w_{ij}$。如此可以保证：

  1. $Q_t + Q$ 为对角矩阵，且 $Q_t + Q \preceq I$（由 2.1.2 可得）
  2. $Q_t$ 的各行之和、各列之和均非负
  3. 对于选定的 $j$，$Q_t$ 的第 $j$ 个对角元素随 $t$ 单调递增

再构造向量序列 $\alpha_1,\alpha_2,···,\alpha_n$，其中 $\alpha_n = a$，其余 $\alpha_t$ 如下递归定义：

$$\alpha_t = [\alpha_t(1) – \alpha_t(t),···,\alpha_t(t-1) – \alpha_t(t)]^T,\quad t = n,···,2$$

$\alpha_{t-1}$ 的维数比 $\alpha_t$ 的维数少一维。由于 $a$ 中元素递减，所以 $\alpha_t$ 为非负向量。类似地，定义 $\lbrace \beta_t\rbrace$

由 2.1.2 可得：

$$a^T(I-W)b \ge a^TQ_nb = \alpha_n^TQ_n\beta_n$$

下面证明 $\lbrace \alpha_t^TQ_t\beta_t \rbrace$ 是递减序列，这样一来，$\alpha_n^TQ_n\beta_n > \alpha_1^TQ_1\beta_1 = 0$ 得证。

$$
\begin{aligned}
& \alpha_t^TQ_t\beta_t – (\alpha_t – \alpha_t(t)e)^TQ_t(\beta_t – \beta_t(t)e) \\
=& \alpha_t^TQ_t\beta_t – \alpha_t^TQ_t(\beta_t – \beta_t(t)e) + (\alpha_t(t)e)^TQ_t(\beta_t – \beta_t(t)e) \\
=& \alpha_t^TQ_t\beta_t(t)e + (\alpha_t(t)e)^TQ_t(\beta_t – \beta_t(t)e) \ge 0
\end{aligned}
$$

$$
\begin{aligned}
\Rightarrow \alpha_t^TQ_t\beta_t \ge & (\alpha_t – \alpha_t(t)e)^T Q_t (\beta_t – \beta_t(t)e) \\
\ge & \alpha_{t-1}^T Q_{t-1} \beta_{t-1}
\end{aligned}
$$

其中 $(\alpha_t – \alpha_t(t)e)^T \ge \alpha_{t-1}^T$ 是因为这两个向量前 $t-1$ 项相等，而 $\alpha_{t-1}$ 比 $\alpha_{t}$ 少一维；$Q_t \ge Q_{t-1}$ 是因为 $Q_{t-1}$ 对角线上的每个元素均 $\le Q_{t}$ 同位置上的数。

所以，$\lbrace \alpha_t^TQ_t\beta_t \rbrace$ 是递减序列，引理 1 得证。

引理 2： $A,B$ 为 $n$ 阶实对称矩阵，$A,B$ 的特征值 $\lbrace\sigma_i(A)\rbrace_{i=1}^n,\lbrace\sigma_i(B)\rbrace_{i=1}^n$ 为从大到小排列的序列，则：

$$\max\limits_{U^TU = V^TV = I} tr(AUBV^T) = \sum_{i=1}^n\sigma_i(A)\sigma_i(B) \tag{2.1.3}$$

证明：

由于 $tr(A) = tr(PAP^{-1})$，对 $A,B$ 进行 SVD 分解，可得

$$
\begin{aligned}
& \max\limits_{U^TU = V^TV = I} tr(AUBV^T) \\
&= \max tr(diag(a)U diag(b) V^T)
\end{aligned}
$$

其中 $diag(a)$ 是与 $A$ 同形的对角矩阵，对角线上元素为 $A$ 的特征值从大到小排列。

$$
\begin{aligned}
tr(diag(a)U diag(b) V^T) &= \sum_{i,j}a_iu_{ij}v_{ij}b_j \\
&\le \sum_{i,j}a_i|u_{ij}v_{ij}|b_j\\
&\triangleq \sum_{i,j}a_iw_{ij}b_j = a^TWb\\
\end{aligned}
$$

根据柯西不等式，$\sum_{i,j}w_{ij} = \sum_{i,j}|u_{ij}v_{ij}| \le \|u_j\|_2\cdot\|v_j\|_2 = 1$

所以有 $e^TW\preceq e^T,We\preceq e$，根据引理 1，$a^TWb \preceq a^Tb$，因此

$$tr(diag(a)U diag(b) V^T) \le a^Tb = \sum_{i=1}^n\sigma_i(A)\sigma_i(B)$$

当 $U,V$ 取单位矩阵时，两边取等号

引理 3：

$$|A|^2_F = \sum_i\sigma_i(A)^2 \tag{2.1.4}$$

证明：
$$\because A\cdot\vec{x} = \sigma\cdot\vec{x},\quad |A^T – \lambda E| = |A-\lambda E|$$
$$
\begin{aligned}
\therefore A^T\cdot\vec{x} =& \sigma\cdot\vec{x} \\
AA^T\cdot\vec{x} =& \sigma^2\cdot\vec{x} \\
\end{aligned}
$$
$$\therefore \sum_i\sigma^2 = tr(AA^T) = \sum_{i,j}a_{ij}\cdot a_{ij} = \|A\|^2_F $$

现在回到（2.1.1）的证明

$$
\begin{aligned}
\|A-B\|^2_F &= \sum_{i,j}(a_{ij} – b_{ij})^2 \\
&= \sum_{i,j}(a_{ij}^2 + b_{ij}^2) – 2\sum{i,j}a_{ij}b_{ij}\\
&= \|A\|^2_F + \|B\|^2_F – atr(AB^T)\\
&\ge \sum_{i=1}^n\sigma_i(A)^2 + \sum_i\sigma_i(B)^2 – 2\sum_{i=1}^n\sigma_i(A)\sigma_i(B)\quad (由 2.1.3 \; 2.1.4)\\
&= \sum_{i=1}^n(\sigma_i(A) – \sigma_i(B))^2 \\
&= \sum_{i=1}^k(\sigma_i(A) – \sigma_i(B))^2 + \sum_{i=k+1}^n\sigma_i(A)^2 \\
&\ge \sum_{i=k+1}^n\sigma_i(A)^2
\end{aligned}
$$

因此，只有 $\lbrace\sigma_i(A)\rbrace_{i=1}^k$ 是最大的特征值，$\lbrace\sigma_i(A)\rbrace_{i=k+1}^n$ 是最小的特征值，差才最小。因此最优解用最大的 $k$ 个特征值近似表示。

3. 引用

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

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

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

[mathjax]

发表评论