主成分分析(PcA) Scatter plot on two principal axes Scatter plot on three principal axes 7 65 0.5 55 -05 用PCA降到2维 用PCA降到3维
主成分分析（PCA） 用PCA降到2维 用PCA降到3维
奇异值分解(sVD) PCA中对散布矩阵S的本征值分解计算量较大,如 特征向量维度较高,直接对S进行本征值分解十分 困难。 例如对图像的PCA分析: ·图像:100×100 散布矩阵:10000×10000 S=∑(xk-mxk-m) 10000×10000的矩阵本征值分解? Se=e|空间复杂度和时间复杂度均无法接受!
奇异值分解（SVD） • PCA中对散布矩阵S的本征值分解计算量较大，如 特征向量维度较高，直接对S进行本征值分解十分 困难。 • 例如对图像的PCA分析： • 图像： • 散布矩阵： • 的矩阵本征值分解？ 100 100 1 ( )( ) n t k k k= S x m x m = − − 10000 10000 Se e = 10000 10000 空间复杂度和时间复杂度均无法接受！
奇异值分解(sVD) 解决方案:不直接对S进行本征值分解,而利用 SVD对一个较小的矩阵进行本征值分解 SVD定理 设A是一个秩为n的d×n矩阵,则存在两个正交矩阵 u∈ UU=I l]∈R VV=I 以及对角阵A=dag,2,]∈R≥122…≥4 满足A=UAV7 其中:4(=1,2,…,m)为矩阵AA和AA的非零本征值,u,和v分 别为AA和AA对应于λ的本征向量 该分解称为矩阵A的奇异值分解( Singular Value Decomposition,svD),为A的奇异值
奇异值分解（SVD） • 解决方案：不直接对S进行本征值分解，而利用 SVD对一个较小的矩阵进行本征值分解 • SVD定理 • 设A是一个秩为n的 矩阵，则存在两个正交矩阵 以及对角阵 满足 其中： 为矩阵 和 的非零本征值， 和 分 别为 和 对应于 的本征向量。 该分解称为矩阵A的奇异值分解（Singular Value Decomposition，SVD）， 为A的奇异值。 d n 1 2 [ , , , ] d n T n U u u u U U I = = 1 2 [ , , , ] n n T d V v v v V V I = = 1 2 1 2 [ , , , ] n n n n diag Λ = 1 2 T A U= Λ V ( 1, 2, , ) i i n = T AA T A A ui i v T AA T A A i i
奇异值分解(sVD) 推论 A=UAVTL> U=AVA2 利用sVD简化S的本征值分解 散布矩阵S=∑(x4-m(xk-my=AA∈R k=1 其中,A={x-mx2-m,,xn-m]∈R R=AA∈Rm 若d>n,则对R进行本征值分解要比直接对S进行本征 值分解快。例如,对绝大多数图像训练集来讲,图像的像素 数要远远大于训练集中的样本个数,即d>n
奇异值分解（SVD） • 推论 • 利用SVD简化S的本征值分解 散布矩阵 其中， 令 若 ，则对R进行本征值分解要比直接对S进行本征 值分解快。 1 2 T A U= Λ V 1 2 − U AV = Λ 1 ( )( ) n t T d d k k k = S x m x m AA = − − = 1 2 [ , , ] d n n A x m x m x m = − − − T n n R A A = d n 例如，对绝大多数图像训练集来讲，图像的像素 数要远远大于训练集中的样本个数，即d n
奇异值分解(sVD) 对R进行本征值分解 本征值:λ(=1,2,…,n) 本征向量:w ·根据U=AA2,得出S=AA7的本征向量为 Av d×a矩阵的 n×n矩阵的 本征值分解 本征值分解
奇异值分解（SVD） • 对R进行本征值分解 • 本征值： • 本征向量： • 根据 ，得出 的本征向量为 ( 1, 2, , ) i i n = i v 1 2 − U AV = Λ T S AA = 1 i i i u Av = 矩阵的 本征值分解 d d 矩阵的 本征值分解 n n