定理奇异值分解

对任意矩阵 $A$, 存在正交矩阵 $U$ 和 $V$, 以及对角矩阵 $\Sigma$ 使得:

$$ A = U \Sigma V^T $$

证明

$A^TA$ 是对称的, $\text{rank}(A^TA) = r$, 则特征值 $\lambda_1 \ge \lambda_2 \ge \cdots \lambda_r > 0 = \lambda_{r+1} = \lambda_{r+2} = \cdots \lambda_n$, 可正交对角化:

$$A^TA = V \Lambda V^T$$

把 $V$ 分成两部分 $V=[V_1, V_2]$, 其中 $V_1 = [v_1, \cdots, v_r]$, $V_2 = [v_{r+1}, \cdots, v_n]$. 显见 $v_{r+1}, \cdots, v_n$ 恰好构成 $N(A^TA)$ 的标准正交基.

从 $V_1 = [v_1, \cdots, v_r]$ 出发考虑 $U_1 = [u_1, \cdots, u_r]$:

$$ u_i = \frac{1}{\sqrt{\lambda_i}} A v_i $$

则容易验证 $u_i$ 是 $R(A)$ 的标准正交基. $R(A)$ 的正交补是 $N(A^T)$, 考虑其一组正交基 $U_2 = [u_{r+1}, \cdots, u_n]$, 则 $U = [U_1, U_2]$ 是正交矩阵. 记:

$$ \Sigma_1 = \text{diag}(\sqrt{\lambda_1}, \cdots, \sqrt{\lambda_r}) \\ \Sigma = \begin{bmatrix} \Sigma_1 & 0 \\ 0 & 0 \end{bmatrix} $$

则可以得出 $U_1\Sigma_1 = AV_1$. 则:

$$ U \Sigma V^T = [U_1, U_2] \begin{bmatrix} \Sigma_1 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} V_1^T \\ V_2^T \end{bmatrix} = U_1 \Sigma_1 V_1^T = AV_1V_1^T = A $$

定义

对一个非零的 $m \times n$ 实矩阵 $A \in \mathbb{R}^{m \times n}$, 可将其表示为满足如下特性的三个实矩阵乘积形式的因子分解运算:

$$A = U \Sigma V^T$$

其中:

• $U$ 是 $m$ 阶正交矩阵, $U^T U = I$;
• $V$ 是 $n$ 阶正交矩阵, $V^T V = I$;
• $\Sigma$ 是由降序排列的非负的对角线元素组成的 $m \times n$ 矩形对角矩阵:

$$ \Sigma = \text{diag}(\sigma_1, \cdots, \sigma_p)$$

这里 $\sigma_1 \geq \cdots \geq \sigma_p \geq 0$, 且 $p = \min(m, n)$.

$U \Sigma V^T$ 称为 $A$ 的 奇异值分解, $\sigma_i$ 称为 $A$ 的 奇异值, $U$ 和 $V$ 的列向量分别称为 $A$ 的 左,右奇异向量.

特别地, 当 $\text{rank}(A)=r$ 时, $\Sigma$ 的前 $r$ 个对角线元素 $\sigma_1, \cdots, \sigma_r$ 是正的, 我们称 $U_r\Sigma_r V_r^T$ 为 $A$ 的 紧奇异值分解; 对于任意 $0 \lt k \lt r$, $U_k\Sigma_k V_k^T$ 称为 $A$ 的 截断奇异值分解.

定义

设 $A \in \mathbb{R}^{m \times n}$ 且 $A = [a_{ij}]_{m \times n}$, $A$ 的 Frobenius 范数 $\|A\|_F$ 定义如下:

$$\|A\|_F = \left[\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}^2\right]^{\frac{1}{2}}$$

定理

若 $Q$ 是 $m$ 阶正交矩阵, 则 $\|QA\|_F = \|A\|_F$.

证明

设 $A = [a_1, \cdots, a_n]$, 则:

$$ \begin{aligned} \|QA\|_F^2 &= \| [Qa_1, \cdots, Qa_n]\|_F^2 = \sum_{i=1}^{n} \|Qa_i\|^2 \\ &= \sum_{i=1}^{n} (Qa_i)^T (Qa_i) = \sum_{i=1}^{n} a_i^T Q^T Q a_i \\ &= \sum_{i=1}^{n} a_i^T a_i = \sum_{i=1}^{n} \|a\|^2 = \|A\|_F^2 \end{aligned} $$

定理

设 $A \in \mathbb{R}^{m \times n}$, $\text{rank}(A) = r$, $A = U \Sigma V^T$ 是 $A$ 的奇异值分解, 并设 $\mathcal{M}$ 是 $\mathbb{R}^{m \times n}$ 中所有秩不超过 $k$ 的矩阵的集合, $0 \lt k \lt r$.

若 $A'=U\Sigma'V^T$, 其中 $\Sigma'_{m \times n} = \begin{bmatrix} \Sigma_k & 0 \\ 0 & 0 \end{bmatrix}$, 这里 $\Sigma_k = \text{diag}(\sigma_1, \cdots, \sigma_k)$, 则:

$$ \|A-A'\|_F = \sqrt{\sum_{l=k+1}^{n} \sigma_l^2} = \min_{S\in \mathcal{M}} \|A-S\|_F $$

即截断奇异值分解 $A' = U\Sigma'V^T$ 是 $A$ 在 $\mathcal{M}$ 中的最优近似.

证明

一个显然的结论是, 由上一个定理, 设 $A=U\Sigma V^T$, 则:

$$ \|A\|_F = \|U\Sigma V^T\|_F = \|\Sigma\|_F = \sqrt{\sum_{l=1}^{n} \sigma_l^2} $$

取 $X$ 为 $A$ 的截断奇异值 $A'$, 则:

$$ \|A-X\|_F = \|A-A'\|_F = \sqrt{\sum_{l=k+1}^{n} \sigma_l^2} $$

下面只需要证明:

$$\|A-X\|_F \ge \sqrt{\sum_{l=k+1}^{n} \sigma_l^2}$$

再设 $X$ 的奇异值分解为 $X = Q\Omega P^T$, 其中:

$$ \Omega = \begin{bmatrix} \Omega_1 & 0 \\ 0 & 0 \end{bmatrix} $$

这里 $\Omega_1 = \text{diag}(\omega_1, \cdots, \omega_k)$.

令 $B=Q^TAP$, 则 $A=QBP^T$, 按照 $\Omega$ 的分块方法对 $B$ 进行分块:

$$ B = \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} $$

则:

$$ \begin{aligned} \|A-X\|_F^2 &= \|Q(B-\Omega)P^T\|_F^2 = \|B-\Omega\|_F^2 \\ &= \|B_{11}-\Omega_1\|_F^2 + \|B_{12}\|_F^2 + \|B_{21}\|_F^2 + \|B_{22}\|_F^2 \end{aligned} $$

既然 $X$ 使得 $\|A-X\|_F^2$ 最小, 我们考虑取 $Y=Q\Omega'P^T \in \mathcal{M}$, 其中 $\Omega' = \begin{bmatrix} B_{11} & B_{12} \\ 0 & 0 \end{bmatrix}$, 则由最小性可得:

$$ \|A-X\|_F^2 \le \|A-Y\|_F^2 = \|B_{21}\|_F^2 + \|B_{22}\|_F^2 $$

由此立得 $B_{12} = 0$, 且 $B_{11} = \Omega_1$, 同理 $B_{21}=0$. 从而我们得到:

$$ \|A-X\|_F = \|B_{22}\|_F $$

设 $B_{22}$ 的奇异值分解是 $B_{22} = U_1 \Lambda V_1^T$, 则:

$$ \|A-X\|_F = \|B_{22}\|_F = \|\Lambda\|_F $$

注意到:

$$ Q^T A P = B = \begin{bmatrix} \Omega_1 & 0 \\ 0 & B_{22} \end{bmatrix} $$

那么右下角也可以对角化, 准确来说设:

$$ U_2 = \begin{bmatrix} I_k & 0 \\ 0 & U_1 \end{bmatrix}, \quad V_2 = \begin{bmatrix} I_k & 0 \\ 0 & V_1 \end{bmatrix} $$

显见:

$$ U_2^T Q^T A P V_2 = U_2^T B V_2 = \begin{bmatrix} \Omega_1 & 0 \\ 0 & \Lambda \end{bmatrix} $$

即:

$$ A = QU_2 \begin{bmatrix} \Omega_1 & 0 \\ 0 & \Lambda \end{bmatrix} \left(PV_2\right)^T $$

这意味着 $\Lambda$ 的对角线元素是 $A$ 的奇异值, 故有

$$ \|A-X\|_F = \|\Lambda\|_F \ge \sqrt{\sum_{l=k+1}^n \sigma_l^2} $$

因此 $\|A-X\|_F = \sqrt{\sum_{l=k+1}^n \sigma_l^2} = \|A-A'\|_F$.

定义

设 $x = (x_1,x_2,\cdots, x_m)^T$ 是 $m$ 维随机向量, $\alpha \in \mathbb{R}^m$ 且 $\alpha^T \alpha = 1$, 则称:

$$ y=\alpha^T x $$

为 标准线性组合.

定义

设 $\mathbf{x}=(x_1,x_2,\cdots,x_m)^T$ 是均值为 $\mu$, 协方差矩阵为 $\Sigma$ 的 $m$ 维随机向量, $A$ 是半正定矩阵 $\Sigma$ 的对角化正交矩阵, 即 $A^T \Sigma A = \Lambda$. 则如下线性变换被称为 主成分变换:

$$\mathbf{y}=A^T(\mathbf{x}-\mu).$$

并称 $\mathbf{y}$ 的第 $i$ 个分量:

$$y_i=\alpha_i^T(\mathbf{x}-\mu)$$

为 $\mathbf{x}$ 的第 $i$ 主成分，这里 $\alpha_i$ 为 $A$ 的第 $i$ 个列向量.

定理

设 $\mathbf{x} \sim (\mu, \Sigma)$, 则 $\mathbf{y} = A^T (\mathbf{x} - \mu)$ 满足:

• $E[\mathbf{y}] = 0$.
• $\text{Var}(y_i) = \lambda_i, i = 1, 2, \cdots, m$.
• $\text{Cov}(y_i, y_j) = 0, i \neq j, i, j = 1, 2, \cdots, m$.

定理

不存在方差比 $\lambda_1$ 更大的标准线性组合 $y = \alpha^T \mathbf{x}$.

证明

考虑标准线性组合 $y=\alpha^T\mathbf{x}$, 其中 $\alpha \in \mathbf{R}^m$ 且 $\alpha^T\alpha=1$. 由于 $\alpha_1,\alpha_2,\cdots,\alpha_m$ 正好构成了 $\mathbf{R}^m$ 的一组标准正交基, 则存在 $c_1,c_2,\cdots,c_m\in\mathbb{R}$ 使得

$$\alpha=\sum_{i=1}^mc_i\alpha_i$$

对此线性组合来说，

$$\begin{aligned} \text{Var}(y)=\alpha^T\Sigma\alpha&=\left[\sum_{i=1}^mc_i\alpha_i^T\right]\Sigma\left[\sum_{i=1}^mc_i\alpha_i\right]\\ &=\sum_{i=1}^mc_i^2\lambda_i\alpha_i^T\alpha_i=\sum_{i=1}^mc_i^2\lambda_i.\end{aligned}$$

另一方面结合:

$$1=\alpha^T\alpha=\sum_{i=1}^mc_i^2\alpha_i^T\alpha_i=\sum_{i=1}^mc_i^2$$

问题显然是 $c_1 = 1, c_2 = c_3 = \cdots = c_m = 0$ 时取得最大值 $\lambda_1$. 因此:

$$\max_{c_1,\cdots,c_m}\text{Var}(y)=\lambda_1$$

对应的标准线性组合为:

$$y=\alpha_1^T\mathbf{x}$$

定理

如果标准线性组合 $y = \alpha^T \mathbf{x}$ 和 $\mathbf{x}$ 的前 $k$ 个主成分都不相关, 则 $y$ 的方差当 $y$ 是第 $k+1$ 个主成分时最大.

证明

证明：设 $y=\alpha^T\mathbf{x}$, 其中 $\alpha^T\alpha=1$. 且 $\alpha=\sum_i^mc_i\alpha_i$, 对此线性组合来说:

$$\text{Var}(y)=\sum_{i=1}^mc_i^2\lambda_i$$

对 $1\leq j \lt k$ 来说:

$$ \begin{aligned} \text{Cov}(y,y_j)&=\text{Cov}(\alpha^T\mathbf{x},\alpha_j^T\mathbf{x})=\left[\sum_{i=1}^mc_i\alpha_i^T\right]\Sigma\alpha_j\\ &=c_j\lambda_j\alpha_j^T\alpha_j=c_j\lambda_j=0 \end{aligned} $$

这意味着对$1\leq j \lt k$ 来说, $c_j^2\lambda_j=0$. 故:

$$\text{Var}(y)=\sum_{i=k+1}^mc_i^2\lambda_i$$

和前面证明类似, 我们可得:

$$\max_{c_1,\cdots,c_m}\text{Var}(y)=\lambda_{k+1}$$

对应的标准线性组合:

$$y=\alpha_{k+1}^T\mathbf{x}$$

正好是第 $k+1$ 主成分.

定义

$\mathbf{x}$ 的第 $k$ 个主成分 $y_k$ 的 方差贡献率 定义为:

$$ \eta_k = \frac{\lambda_k}{\sum_{i=1}^m \lambda_i} $$

$\mathbf{x}$ 的前 $k$ 个主成分 $y_1, y_2, \cdots, y_k$ 的 累计方差贡献率 定义为:

$$ \eta_{1 \to k} = \sum_{i=1}^k \lambda_i= \frac{\sum_{i=1}^k\lambda_k}{\sum_{i=1}^m \lambda_i} $$

定义

定义 因子负荷量 为第 $k$ 个主成分 $y_k$ 和原始变量 $x_i$ 的相关系数:

$$ \begin{aligned} \rho(y_k,x_i) &= \frac{\text{Cov}(y_k, x_i)}{\sqrt{\text{Var}(y_k) \cdot \text{Var}(x_i)}} = \frac{\text{Cov}\left(\sum_{j=1}^m \alpha_{ij}y_j, y_k\right)}{\sqrt{\lambda_k \sigma_{ii}}} \\ &= \frac{\alpha_{ik} \text{Var}(y_k) }{\sqrt{\lambda_k \sigma_{ii}}} = \frac{\sqrt{\lambda_k} \alpha_{ik}}{\sqrt{\sigma_{ii}}} \end{aligned} $$

定义

$\mathbf{x}$ 的前 $k$ 个主成分 $y_1, y_2, \cdots, y_k$ 对原有变量 $x_i$ 的 贡献率 定义为:

$$ \nu_{1 \to k} = \sum_{j=1}^k \rho^2(y_j, x_i) = \sum_{j=1}^k \frac{\lambda_j \alpha_{ij}^2}{\sigma_{ii}} $$

算法PCA

输入: 规范化后的样本数据矩阵 $\mathbf{X}_{m \times n}$

输出: 样本主成分矩阵 $\mathbf{Y}_{k \times n}$

1. 构造: $$\mathbf{X}' = \frac{1}{\sqrt{n-1}}\mathbf{X}^T$$
2. 求 $X'$ 的 $k$ 秩截断奇异值分解: $$\mathbf{X}' = U_k \Sigma_k V_k^T$$
3. 返回样本前 $k$ 主成分矩阵: $$\mathbf{Y} = V^T\mathbf{X}$$