统计学习方法学习笔记：第十五章.奇异值分解

统计学习方法学习笔记：第十五章.奇异值分解

第十五章：奇异值分解（SVD:singular value decomposition）

定义与性质

将一个 非 零 的 color{red}{非零的} 非零的的 m × n color{red}{mtimes{n}} m×n的实矩阵A，表示为以下三个矩阵乘积的运算：

A = U Σ V T ， 这 里 是 完 全 奇 异 值 分 解 color{red}{A=USigma{V^T}，这里是完全奇异值分解} A=UΣVT，这里是完全奇异值分解

其中，U是m阶正交阵，V是n阶正交阵
满 足 U U T = E , V V T = E ， 对 应 着 坐 标 系 的 旋 转 或 反 射 变 换 color{red}{满足UU^T=E,VV^T=E，对应着坐标系的旋转或反射变换} 满足UUT=E,VVT=E，对应着坐标系的旋转或反射变换

Σ Sigma Σ是 m × n mtimes{n} m×n矩形对角矩阵（只有对角线上的元素非零）
满 足 Σ = d i a g ( σ 1 , σ 2 , ⋯ , σ p ) , σ 1 ≥ σ 2 ≥ ⋯ ≥ σ p ≥ 0 ; p = m i n ( m , n ) ， 对 应 着 坐 标 轴 的 缩 放 变 化 ， color{red}{满足Sigma=diag(sigma_1,sigma_2,cdots,sigma_p),sigma_1geqsigma_2geqcdotsgeqsigma_pgeq0;p=min(m,n)，对应着坐标轴的缩放变化，} 满足Σ=diag(σ1​,σ2​,⋯,σp​),σ1​≥σ2​≥⋯≥σp​≥0;p=min(m,n)，对应着坐标轴的缩放变化，

任 意 实 矩 阵 A 的 奇 异 值 分 解 均 存 在 color{red}{任意实矩阵A的奇异值分解均存在} 任意实矩阵A的奇异值分解均存在

紧奇异值分解与截断奇异值分解：

A = U k Σ k V k T color{red}{A=U_kSigma_kV_k^T} A=Uk​Σk​VkT​；
U k , V k 分 别 对 应 着 完 全 分 解 中 U , V 的 前 k 列 ， Σ k 由 Σ 的 前 k 个 对 角 线 元 素 构 成 color{red}{U_k,V_k分别对应着完全分解中U,V的前k列，Sigma_k由Sigma的前k个对角线元素构成} Uk​,Vk​分别对应着完全分解中U,V的前k列，Σk​由Σ的前k个对角线元素构成

假设矩阵 A 的秩为 r：

k = r ：紧奇异值分解是和原矩阵 等 秩 color{red}{等秩} 等秩的奇异值分解，对应着 无 损 压 缩 color{red}{无损压缩} 无损压缩

k < r ：上式分解中的等号要变成约等号，截断奇异值分解是比原矩阵 低 秩 color{red}{低秩} 低秩的奇异值分解，对应着 有 损 压 缩 color{red}{有损压缩} 有损压缩

主要性质：

1. V V V的列向量是 A T A A^TA ATA的特征向量， U U U的列向量是 A A T AA^T AAT的特征向量， Σ Sigma Σ的奇异值是 A T A A^TA ATA和 A A T AA^T AAT特征值的平方根
2. A v j = σ j u j , Av_j=sigma_ju_j, Avj​=σj​uj​, U 、 V U、V U、V的向量之间存在着对应关系，
3. 奇异值是唯一的，但是 U 、 V U、V U、V不唯一
4. A A A的秩等于正奇异值的个数（包括重复的）

奇异值的计算

求解对称矩阵 A T A A^TA ATA的特征值和特征向量，

1. 求解 A T A A^TA ATA的特征值和特征向量
2. 求解 V V V
3. 求解对角阵 Σ Sigma Σ
4. 求解正交阵 U U U：通过 A v j = σ j u j Av_j=sigma_ju_j Avj​=σj​uj​求得 U U U的前r列（只有r个奇异值非零），然后求解 A T x = 0 A^Tx=0 ATx=0线性方程组（因为U的后m-r列构成零空间R(A^T)的一组标准正交基）

实 际 应 用 并 不 直 接 计 算 A T A , 有 许 多 其 他 的 求 解 奇 异 值 分 解 的 算 法 ； color{red}{实际应用并不直接计算A^TA,有许多其他的求解奇异值分解的算法；} 实际应用并不直接计算ATA,有许多其他的求解奇异值分解的算法；

矩阵的最优近似

弗罗贝尼乌斯范数：

∣ ∣ A ∣ ∣ = ( ∑ i = 1 m ∑ j = 1 n ( a i j ) 2 ) 1 2 = ( σ 1 2 + σ 2 2 + ⋯ + σ n 2 ) 1 2 color{red}{||A||=(displaystylesum_{i=1}^msum_{j=1}^n(a_{ij})^2)^frac{1}{2}}=(sigma_1^2+sigma_2^2+cdots+sigma_n^2)^frac{1}{2} ∣∣A∣∣=(i=1∑m​j=1∑n​(aij​)2)21​=(σ12​+σ22​+⋯+σn2​)21​

定理：在秩不超过 k k k的 m × n mtimes{n} m×n的矩阵的集合 M M M中，存在矩阵 A A A 的弗罗贝尼乌斯范数意义下的最优近似矩阵 X X X,使得：
∣ ∣ A − X ∣ ∣ F = min ⁡ S ∈ M ∣ ∣ A − S ∣ ∣ F = ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 color{red}{||A-X||_F=displaystylemin_{Sin{M}}||A-S||_F=(sigma_{k+1}^2+sigma_{k+2}^2+cdots+sigma_n^2)^frac{1}{2}} ∣∣A−X∣∣F​=S∈Mmin​∣∣A−S∣∣F​=(σk+12​+σk+22​+⋯+σn2​)21​

而 A ′ = U Σ ′ V T ， 就 是 这 样 一 个 最 优 矩 阵 color{red}{A'=USigma'V^T，就是这样一个最优矩阵} A′=UΣ′VT，就是这样一个最优矩阵， Σ ′ Sigma' Σ′为前k个奇异值构成的 m × n mtimes{n} m×n的对角矩阵;

矩阵的外积展开式：

A = ∑ k = 1 n σ k u k v k T = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n u n v n T color{red}{A=displaystylesum_{k=1}^nsigma_ku_kv_k^T=sigma_1u_1v_1^T+sigma_2u_2v_2^T+cdots+sigma_nu_nv_n^T} A=k=1∑n​σk​uk​vkT​=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn​un​vnT​,将矩阵 A A A分为矩阵的有序加权和； u k v k T u_kv_k^T uk​vkT​为一个 m × n mtimes{n} m×n矩阵，是两个向量的外积，

若矩阵 A k = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ k u k v k T color{red}{A_k=sigma_1u_1v_1^T+sigma_2u_2v_2^T+cdots+sigma_ku_kv_k^T} Ak​=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σk​uk​vkT​，则 A A A的秩为 k k k,且 A k A_k Ak​是秩为k的矩阵中在弗罗贝尼乌斯范数意义下 A A A的最优近似矩阵，矩阵 A k A_k Ak​就是矩阵 A A A的截断奇异值分解；

一 般 情 况 下 ， σ i 递 减 很 快 ， 所 以 即 使 k 取 很 小 值 ， A k 也 能 对 A 有 很 好 的 近 似 color{red}{一般情况下，sigma_i递减很快，所以即使k取很小值，A_k也能对A有很好的近似} 一般情况下，σi​递减很快，所以即使k取很小值，Ak​也能对A有很好的近似