降维：主成分分析（ Principal Component Analysis ，PCA） 通过维基百科可查到有两种方法可以进行PCA，EVD和SVD均可 https://en.wikipedia.org/wiki/Principal_component_analysis 一、本文介绍SVD进行PCA降维，上一篇已经介绍过了SVD，趁热打铁。 附：SVD理论介绍 http://blog.sciencenet.cn/blog-1966190-1118220.html 现有的数据 ， 通常先使 X 均值为零（一般是令特征列为零），再进行 SVD 分解可得： ， 其中 U 为 m 阶酉矩阵， V 为 n 阶酉矩阵。 构建主成分 ， 若选择奇异值前 l 个，则 ， 至此已经将X由 n 维数据变成了 l 维数据，降维过程结束。 可对P进行相关分析，即 分析发现P每列（即每个维度）均是不相关的，即正交的。 也可构建主分量 ， 这是另一种做法。 若选取主分量，即较大奇异值（k个， kr ）和对应的 V 中向量（右奇异向量），因为在 SVD 分解中奇异值已经是从大到小排好的顺序，只需选取主分量即可。构建主分量其实属于对 X 的正交变换，这种变换在信号处理中称为 KL 变换，可参考 KL 变换去噪的文献： Jones,I.F. and Levy,S.1987.Signal to Noise Ratio Enhancement in Multichannel Seismic Data via the Karhunen-Loeve Transform,Geophysical Prospecting,35,12-32 若选取主成分为： ， 再进行反变换即 ： ， 这就是经过变换后的数据，显然有信息丢失，可以用保留的奇异值来计算主成分贡献率，这是去噪的流程。 二、再来看特征值分解EVD如何进行PCA 一般概念 协方差矩阵 ：设 X 为 n 维数据，即 X n × n =(x 1 ,x 2 , …… ,x n ) T ， X 的自协方差矩阵定义为 上式中 i 和 j 取不同的值，则可得 n × n 的矩阵。 如果求两个数据的协方差矩阵，只需将式中的 X i 换成 Y i 即可。 相关矩阵 ：上式中最后一行第一项即是相关矩阵的定义，因而可知，只要将数据均值为0后，其协方差矩阵就是相关矩阵。 这部分内容是信号处理中的基础知识，可自己查看清华大学张贤达《现代信号处理》。 协方差矩阵的性质 （如果数据为复数）： 先对 的每列零均值化，计算的协方差矩阵 ， 因 ，故C是酉矩阵。 对C进行特征值分解，即求特征值和特征向量。 可化为 ，其中 ， V 是特征值对应的特征向量构成的矩阵， V 的每一列是特征向量。将特征向量按照特征值的大小排列（MatLab可能是从小到大排列的，注意调整），并进行模值归一化，取前 k 列特征向量，构建主成分 即可得到降维后的数据。 三、PCA 实战参考链接： https://blog.csdn.net/shizhixin/article/details/51181379 https://blog.csdn.net/google19890102/article/details/27969459
SVD 是奇异值分解 一、一般概念 酉矩阵 ：设 A Î C n × n ,C 可以是复矩阵，实矩阵，如果 A*A= I （单位阵）， 则称 A 为酉矩阵；当 A 是实矩阵时，就是我们常见的实正交矩阵。 Hermite 矩阵 ：如果 A*=A, 那么 A 是 Hermite 矩阵，若 A 是实矩阵，称 A 为对称矩阵。 正规矩阵 ：如果 A*A=AA* ，那么称 A 为正规矩阵。酉矩阵和 Hermite 矩阵均属于正规矩阵。 正定 ：对于一 Hermite 矩阵 A ，如果对任意非零向量 x Î C n ，都满足 x*Ax0 ，称 A 为正定阵，如果是大于等于 0 ，称 A 为半正定阵。正定矩阵的特征值一定为正。 二、奇异值分解（ Singular Value Decomposition ， SVD ） 奇异值 ：设 A Î C m × n ， A*A 的特征值的非负平方根称 A 的奇异值，由此定义可知奇异值必然大于等于 0 。 奇异值分解定理 ：设 ，则存在 m 阶酉矩阵 U 和 n 阶酉矩阵 V ，使得 U*AV= 其中 ， s 为奇异值， 上面等式两边可以同时乘以 U 、 V* ，由于 U 和 V 都是酉矩阵，那么必然为正规矩阵， ，此为我们常见的 SVD 分解表达式。 关于 SVD 分解的证明，需用到 Schur 分解，可参看北京大学徐树方《矩阵计算的理论与方法》。 三、SVD的意义和用途 由 SVD 分解定理可知，一般矩阵都是可以进行 SVD 分解的，而常见的特征值分解则需用保证矩阵是方阵，前者分解的奇异值都是大于零的，而特征值不一定。 无论是奇异值还是特征值，都是表征矩阵重要特征的具体指标，这里的特征不妨认为是模式，即事物赖以存在的形式。该值越大表示信息的显著特征，值越小可能是噪声特征。（引申与扩展：过拟合） 如果取 A 的奇异值中较大的数值，比如取前 k 个（ kr ），那么此时也能恢复 A ，但此时 A 的信息则有缺失。那么此时 U 和 V 的维度也减少了（注意维度默认是列数，也称为数据的特征，而行一般称为观测值），这就是降维的一般概念。 SVD 可用于机器学习中数据噪声的去除，保留数据的主要特征。由于 SVD 的结果多样，也不知道哪个是目标结果，所以无需训练算法，这是无监督学习的共性。 四、SVD 的实战练习可参考链接 ： 1. 手写体（ MATLAB ） https://blog.csdn.net/google19890102/article/details/27109235 http://www-users.math.umn.edu/~lerman/math5467/svd.pdf 2. 推荐算法提升（ SVD 竟然也可以，神奇）（ Python ） https://blog.csdn.net/sinat_17451213/article/details/51201682 http://www.sohu.com/a/127149396_464826 3. 图像压缩（ MATLAB ） https://blog.csdn.net/bluecol/article/details/45971423
矩阵的分解，实际上是通过坐标变换来揭示矩阵所表示的线性算子性质。 在过去，人们靠公式的推导来简化计算，线性代数主要用在理论分析和解方程，其重点是表达线性变换的特征，在不同坐标上矩阵表示的相似性和标准形式。在计算机时代，人们关心矩阵的线性运算特征，抽取矩阵的线性放大特性和近似，应用于海量的数据存储和计算。代表着线性算子的一般矩阵的分解，特别是 SVD 分解，便成为今日关注的重点。 8.1 满秩方阵的分解 满秩的方阵对应着一个坐标变换，它可以分解为几个初等变换的乘积。这个分解的目的，在于计算上通过这些初等变换的操作，来解方程和求逆。 我们知道，对线性方程组，调换组中方程的次序，在方程的两边同乘以非零的数，以及将一个方程乘数，两边同加在另一个方程上，都不改变方程组的解。 从线性空间角度来看，这不过是在值域空间做坐标变换。方程的解 x 是 b 在矩阵列向量的线性组合系数，改变了这些向量的坐标表示，当然不改变 b 与矩阵列向量的线性表示关系。 我们把上面三种对方程组的操作称为初等变换，即：（ 1 ）两行（列）互换： R i ↔ R j ，（ 2 ）把某行（列）乘以一非零常数： k R i → R i , 其中 k ≠ 0 ，（ 3 ）把第 i 行（列）加上第 j 行（列）的 k 倍： R i + k R j → R i 。初等矩阵即是将上述 3 种初等变换作用到单位矩阵的结果，分别记为 P ij ， D i (k) ， T ij (k)，对应于旋翻、缩放（k=-1为翻转）和剪切的变换 。初等变换对应于一个坐标变换，初等矩阵左乘矩阵 A ，则是对 A 行的变换，它相应于算子 A 的值域空间中的坐标变换。初等矩阵右乘矩阵 A ，则是对 A 进行列的变换，它相应于在算子 A 的定义域空间中坐标变换。 读者不难在头脑中想象到初等变换的矩阵形式，初等矩阵都是满秩的线性变换。从变换的含义马上得出它们的逆矩阵分别是 P ij ， D i (1/k) ， T ij (-k) 。 参考一下解方程中的高斯消去法，对于一个方阵 A ，它可以一系列行的初等变换，把它变成上三角阵 U ，即 P 1 P 2 …P s A=U ，因为这些是初等矩阵，很容易写出逆来相乘 P s -1 …P 2 -1 P 1 -1 =L ，显然 A = LU. 消去法没有换行时， P 都是下三角阵，则 L 是一个对角线都是 1 的下三角阵，这便是 LU 分解 。三角阵的线性方程可以用迭代法求解，这个分解用来解方程和求行列式。 不难想象 k 秩的矩阵 A ，可以等价于对角线上左上角开始有 k 个 1 ，其余都是 0 的矩阵。如果 A 是一个满秩的矩阵，它等价于单位矩阵。 对于 n 阶满秩方阵 A 求逆的计算，因为 A 的逆是一系列把它变成单位矩阵 I 的初等矩阵的乘积，把 n 阶单位矩阵拼在 A 的右边成为 nx2n 的增广矩阵（ A I ），然后对它进行初等行变换，直至左边的 nxn 那块是单位矩阵，右边那 nxn 部分就是 A 的逆。这个计算过程相当于 A -1 (A I)=(I A -1 ) 。 8.2 正交变换 一般线性空间中坐标变换，在欧几里德空间里，包含着坐标的拉伸、旋转、翻转、剪切等变换，坐标轴之间可能是倾斜。这对只关心加法和数乘代数性质的线性空间，并没有什么关系。因为这抽象线性空间，根本没有“拉伸”和“倾斜”等几何的概念。长度和角度概念由内积运算定义的，要讲究这些，必须在内积空间里来谈论。 保持内积不变的坐标变换，也就是向量的长度和夹角，在不同坐标系上的表示都保持不变。这种坐标变换称为正交变换，物理上称么正变换。它的矩阵在实数域是正交阵，在复数域是酉阵。这直接可以从对偶算子和内积等式推出〈 y, x) 〉 = 〈 Uy, Ux) 〉 = 〈 y,U* Ux) 〉→ U*U=I ，在实数域 U* = U T . 以后我们都只在实数域上讨论，对于复数域，将转置换成共轭转置就行。 内积空间坐标表示必须在标准正交基上，这样才能保证同构关系。正交变换是把这各向同性直角坐标系，刚性地整体旋转和翻转，所以表示的向量长度和夹角在变换后保持不变。 对于线性变换的方阵，坐标变换是同样作用在算子的输入和输出空间，因为在内积空间上坐标变换必须是正交变换，在线性空间上相似的矩阵，在内积空间上未必做得到。例如非对称的矩阵有可能与一个对角阵相似，但未必有正交的坐标变换做到这一点。在内积空间（通过正交变换）与对角阵相似，当且仅当它是正规矩阵，正规矩阵 A 有 A * A = AA*. 实数域上的对称阵和复数域上的厄米矩阵都是正规矩阵。 对于m*n 矩阵 A ， m ≥ n 可以分解成列向量的 m*n 单位正交集 Q 与一个 n*n 的上三角阵 R 相乘， A=QR ，这叫做 QR 分解 。这个分解可以看作依次按照 Gram-Schmidt 方法对 A 中的列向量做正交化， Q 就是单位正交化后的列向量， R 中的元素是正交化过程中的内积。矩阵Q表现旋转和翻转部分的映射，R体现了缩放和剪切的畸变。 怎么把线性无关的列向量变成单位正交的向量组？这在几何上很直观。取矩阵 A 的第一个列向量 把它标准化（归一化） ，其中的长度放在 R 阵的第一个对角线元素上 ，再取第二个列向量 ，减去它在 $ e_1 $ 的投影的向量 ，令 ，再把它标准化 便是两个标准正交的向量。已经有了 k-1 个标准正交向量，取第 k 个列向量 $A_{k}$ ，减去它在这些标准正交向量的投影向量 ，将这些投影分别放在 R 阵中 ，再把它标准化 ，如此下去。这个过程叫做 Gram － Schmidt 正交化。显然，标准正交的向量构成 Q 矩阵 ， R 是一个上三角阵， A=QR 。对于矩阵的列向量不是线性无关时， Q 阵略去 0 向量，最后添上与前面正交的标准向量。 在 MATLAB 和 Octave 中，用 qr 函数来计算行 QR 分解，指令为： =qr(A) ，分解为 m*m 的 Q 阵和 m*n 的 R 阵。 8.3 线性算子对核与像空间的分解 前面介绍过，表示线性算子的矩阵 A ，它的核 Ker(A) 是所有映射成零的向量集合，构成了 X 中的一个子空间；它的像 Im(A) 是所有映射得到向量的集合，构成了 Y 中的一个子空间。我们有线性代数的基本定理，表示为下图。 算子 A 将输入空间 X 和输出空间 Y ，分别分解为正交的两个子空间的直和。 X 的线性子空间 Im(A T ) 和 Y 的 Im(A) 有相同的维数 k ，说明 Im(A T ) 的基向量在算子映射下的像可以作为 Im(A) 的基向量，算子 A 局限这子空间中，在这两个基的矩阵表示是 k 阶单位向量。 在 Im(A T ) 子空间选取 k 个线性无关的向量 {V 1 ,V 2 , …,V k } ，在 Ker(A) 选取 n-k 个 {V k+1 , …,V n } ，共同构成 X 的一个基。令 U i = AV i , i=1, 2, …,k ，它们构成子空间 Im(A) 的基，在 Ker(A T ) 选取 m-k 个 {U k+1 , …,U n } ，共同构成 Y 的一个基。在这两个空间的基上，线性算子 $\\alpha$ 表示表示为主对角线上前 r 个是 1 ，其他全是 0 的“ k 秩准单位阵” D 。 秩数为 k 的线性算子在合适的基上都可以表示为“ k 秩准单位阵”，即 k 秩的矩阵 A 可以分解成 A = UDV -1 ， D 是与 A 的行列数秩数相同的“准单位阵”， V 和 U 分别是 X 和 Y 空间里新旧坐标的变换矩阵。注意到构造 V 和 U 时基时，除了要求前 k 个 U i = AV i , 外，其他的基向量是在指定的子空间内，任意选取线性无关的即可，所以除了 D 是由矩阵的秩唯一确定之外，有无数个不同 U 和 V 的分解。 8.4 奇异值分解 线性算子对核和像空间的分解只是简单地区分对算子的映射值“有影响”和“无影响”的两部分。许多的应用希望了解线性算子作用在不同方向的放大特性，这涉及到向量的长度和方向，必须在内积空间中考虑，它要求坐标变换不改变列向量表示的长度和夹角，即坐标变换必须是正交变换。 线性算子 A 把输入空间 X 分解成正交的 Im(A T ) 子空间和零空间 Ker(A) 的直和， A 把零空间中向量都映成了零向量， Im(A T ) 子空间中的向量与 A 像空间 Im(A) 的向量一一对应。所以对算子放大特性的研究，只需要考虑它对 Im(A T ) 子空间中向量的作用。想象一下线性算子 A 作用在 Im(A T ) 子空间中一个单位向量 v ， v 沿着各种可能的方向转动，它的像 Av 的长度和方向也随之变化，选取能够让它的像有最大长度 σ 1 的 v ，记为 V 1 ，这个像的单位向量记为 U 1 ，有 AV 1 = σ 1 U 1 ；然后在 Im(A T ) 中与 V 1 正交的子空间里，再次选取具有最大长度 σ 2 像的 V 2 ；如此可以进行 k 次，得到 k 个正交单位向量 {V 1 ,V 2 , …,V k } ，它们是一组 Im(A T ) 中标准正交基，有 AV i = σ i U i , ， i=1, 2, …,k ，放大率σ i 逐次减小，这便是线性算子 A 的放大特性。 X 空间中所有的向量可以分解成 Im(A T ) 和 Ker(A) 子空间中向量之和，后者被 A 映射为零向量。在零空间 Ker(A) 里补足 n-k 个单位正交向量 {V K+1 ,V K+2 , …,V n } ，以它们为基， A 在上面的放大率为 0 ，线性算子 A 在不同方向的放大率便直接反映在原空间坐标轴与对应像空间的坐标轴方向上。这些单位正交向量构成正交阵 V ，只要证明 U i 构成的矩阵 U 也是正交阵，就可以把它们看成是内积空间里的坐标变换，我们便能从奇异值分解中，得到线性算子对内积空间不同方向的放大特性。 奇异值分解（简称SVD）说：对于秩数为r的m*n矩阵A，可以分解成 A = UΣV T ，这里U是m阶正交阵，V是n阶正交阵，Σ是主对角线上是从大到小的正数σ 1 ,σ 2 , …, σ k ，其余都是0的m*n矩阵。这些正数称为矩阵A的奇异值。 正交阵 V 表示一个只包含旋转和翻转的坐标变换，它的列向量表示在 X 空间中那个相互正交的新坐标轴单位向量。奇异值分解表达出 A 在这新坐标轴方向上，依次表现出从最大 σ 1 到最小 σ k 的向量长度放大率，直至退化到 0 的算子作用。 U 表示在 Y 空间经过正交变换的新坐标系统，它的前 k 个列向量作为新坐标轴的单位向量，依此对应着那些经过放大作用后的向量方向。矩阵Σ表达算子这些从最大到最小放大率和秩。 从上述 AV i = σ i U i 关系和正交阵 V 构造，在 Ker(A T ) 中选取一组基向量补足列向量，让 U 矩阵满秩，我们知道不论 U 是什么都有分解式 A = U Σ V T 成立。现在证明 U 可以是正交阵。 AA T = (U Σ V T )(V Σ T U T ) = U( ΣΣ T )U T ， AA T 是对称阵，它可以通过正交变换对角化，而ΣΣ T 是对角阵，其对角线上的元素集合即特征值是由 AA T 唯一确定的，这意味着这里的 U 是那个特征向量组成的正交阵。 如何简单地计算 V 和放大系数σ i ？依上面相同的思路，注意到（ A T A ）是个半正定的对称方阵，它可对角化，有非负特征根在对角线上。通过解（ A T A ）的特征方程，求出特征根和单位特征向量，调整这些单位特征向量在矩阵中排列的顺序，使得对应的特征值从大到小，构造正交阵 V ，算子的放大系数便是这些特征根的正平方根。细节如下。 记 Im(A T ) 里的向量 {V 1 ,V 2 , …,V k } 与 Ker(A) 里 {V k+1 , …, V n } ，组成单位正交阵 V ，设 AV i = σ i U i , ， i=1, 2, …,k ，σ i 是个正数， AV i =0 ， i=k+1, …, n ，因为 U 的列向量也都是单位正交的，所以有 V -1 （ A T A ） V = (AV) T (AV) = U T diag( σ 1 2 , σ 2 2 , …, σ r 2 ,0, …,0)U = diag( σ 1 2 , σ 2 2 , …, σ r 2 ,0, …,0) ，这式子表示正交的坐标变换 V ，把对称阵 (A T A) 变成对角线上是σ 1 2 , σ 2 2 , …, σ r 2 , 0 的对角阵。 (A T A) 是半正定的对称阵，它的特征值是σ 1 2 , σ 2 2 , …, σ r 2 , 0 …,0 ，从大到小排列，它们对应着 V 中的列向量为特征向量。这告诉我们，可以通过 (A T A) 的特征值和特性向量得到这 r 个正数σ值和单位正交阵 V 和 U ，这时有 AV = U Σ，即 A = UΣV T 。 注意这个分解中的矩阵 U 和 V 有时不是唯一的，在 i k 时 V 中的列向量 V i 可以在 Ker(A) 子空间中任选一组正交的基向量， U 中的列向量 U i 可以在 Ker(A T ) 子空间中任选一组正交的基向量，当 A T A 有重根的特征值时，相应的列向量可以在它们的不变子空间中任选一组标准正交基向量，它们都构成让分解式成立的不同矩阵。但这些的不同都不影响它特征分析和应用。 谱分析在物理和应用数学上有着非常清晰物理含义，对称矩阵总是可以通过坐标的正交变换对角化，这意味着线性空间中的向量可以按不同的维度（频率）分解，可对角化的方阵只是对线性变换的谱分析。奇异值分解是谱分析思想在任意线性算子上的推广。 奇异值分解从子空间分划和坐标系旋转翻转的角度揭示算子的放大特性，这个分解式还未凸显出它最引人注目的用处。将这分解式展开： 秩数为 r 的矩阵通过奇异值分解，把它变成了 r 个秩数为 1 的矩阵之和： A= σ 1 U 1 V 1 T +σ 2 U 2 V 2 T + … +σ r U r V r T , 当 r 与 m 和 n 相比很小时，这在分析、计算及数据储存上带来很大的方便。因为奇异值是按大小顺序排列的正数，我们甚至可以截取这连加式的前几个作为近似和滤噪。这个性质在图像压缩，信号处理，统计上主成分分析（ PCA ）和机器学习上都有很好的应用。奇异值分解自从 1965 年有了计算机上有效的算法后，现在已经成为线性代数应用最广的分解式。 在包含着矩阵运算的计算机语言中，一般都有奇异值分解的函数，在 MATLAB 和 Octave ，可以用 svd 函数直接得出矩阵 A 的分解式 A = USV T 中的矩阵： = svd(A); （待续）
SVD 分解（奇异值分解），本应是本科生就掌握的方法，然而却经常被忽视。实际上，SVD分解不但很直观，而且极其有用。SVD分解提供了一种方法将一个矩阵拆分成简单的，并且有意义的几块。它的几何解释可以看做将一个空间进行旋转，尺度拉伸，再旋转三步过程。 首先来看一个对角矩阵， 几何上, 我们将一个矩阵理解为对于点 (x, y) 从一个平面到另一个平面的映射: 下图显示了这个映射的效果: 平面被横向拉伸了3倍，纵向没有变化。 对于另一个矩阵 它的效果是 这样一个变化并不是很好描述，然而当我们将坐标系旋转45度后，我们可以看出 这时，我们发现这个新的网格上发生的变化和网格在对角阵下发生变化的效果相似。 这是一个对称矩阵的例子，可以看出，对称矩阵经过旋转后，其作用就和对角阵类似了。数学上，对于一个对称矩阵 M , 我们可以找到一组正交向量 v i 从而 M v i 相当于 v i 上的标量乘积; 也就是 M v i = λ i v i λ i 是标量，也就是对应对角阵中对角线上的元素. 由于这个性质，我们称 v i 是 M 的特征向量; λ i 为特征值. 一个对称矩阵不同特征值对应的特征向量是正交的。 对于更广泛的情况，我们看看是否能从一个正交网格转换到另一个正交网格. 考虑一个非对称矩阵: 这个矩阵的效果形象的称为剃刀（ shear ）。 这个矩阵将网格在水平方向拉伸了，而垂直方向没有变化。如果我们将网格旋转大约58度，这两个网格就又会都变为正交的了。 奇异值分解： 考虑一个 2 *2 矩阵, 我们可以找到两组网格的对应关系。用向量表示，那就是当我们选择合适的单位正交向量 v 1 和 v 2 , M v 1 和 M v 2 也是正交的. 我们使用 u 1 和 u 2 代表 M v 1 和 M v 2 的方向. M v 1 和 M v 2 的长度表示为 σ 1 和 σ 2 ，也就是网格在每个方向的拉伸. 这两个拉伸值叫做M的 奇异值（sigular value） 和前面类似，我们可以 有 M v 1 = σ 1 u 1 M v 2 = σ 2 u 2 我们一直讨论的 v 1 和 v 2 是一对正交向量， 对于一般的向量 x ，我们有这样的投影关系 x = ( v 1 x ) v 1 + ( v 2 x ) v 2 也就是说 M x = ( v 1 x ) M v 1 + ( v 2 x ) M v 2 M x = ( v 1 x ) σ 1 u 1 + ( v 2 x ) σ 2 u 即 M x = u 1 σ 1 v 1 T x + u 2 σ 2 v 2 T x --- M = u 1 σ 1 v 1 T + u 2 σ 2 v 2 T 这个关系可以写成矩阵形式 M = U Σ V T U 的列是 u 1 和 u 2 , Σ σ 1 和 σ 2 构成的对角阵, V 的列是 v 1 和 v 2 . 即V描述了域中的一组正交基，U描述了相关域的另一组正交基，Σ 表述了U中的向量与V中向量的拉伸关系。 寻找奇异值分解 奇异值分解可以应用于任何矩阵，对于前面的例子，如果我们加上一个圆，那它会映射成一个椭圆，椭圆的长轴和短轴定义了新的域中的正交网格，可以被表示为 M v 1 and M v 2 。 换句话说，单位圆上的函数 | M x | 在 v 1 取得最大值，在 v 2 取得最小值. 这将单位圆上的函数优化问题简化了。可以证明，这个函数的极值点就出现在 M T M 的特征向量上，这个矩阵一定是对称的，所以不同特征值对应的特征向量 v i 是正交的. σ i = | M v i |就是奇异值, u i 是 M v i 方向的单位向量. M v i = σ i u i M v j = σ j u j . M v i M v j = v i T M T M v j = v i M T M v j = λ j v i v j = 0.也就是 M v i M v j = σ i σ j u i u j = 0因此, u i 和 u j 也是正交的。所以我们就把一组正交基 v i 变换到了另一组正交基 u i . 另一个例子 我们来看一个奇异矩阵（秩为1，或只有一个非零奇异值） 它的效果如下 在这个例子中，第二个奇异值为0，所以 M = u 1 σ 1 v 1 T . 也就是说，如果有奇异值为0，那么这个矩阵就有降维的效果。因为0奇异值对应的维度就不会出现在右边。这对于计算机科学中的数据压缩极其有用。例如我们想压缩下面的15 25 像素的黑白图像 我们可以看出这个图像中只有三种列，即 把图像表示成一个15 25 的矩阵，总共有 375 个元素. 然而当我们做了奇异值分解，会发现非零奇异值仅有3个， σ 1 = 14.72， σ 2 = 5.22， σ 3 = 3.31 因此，这个矩阵就可以被表示为 M = u 1 σ 1 v 1 T + u 2 σ 2 v 2 T + u 3 σ 3 v 3 T 也就是说我们用三个长度为15的向量 v i ，三个长度为25的向量 u i ，以及三个奇异值，总共123个数字表示了这个375个元素组成的矩阵。奇异值分解找到了矩阵中的冗余信息实现了降维。 可以看出，奇异值分解捕获了图像中的主要信息。因此，又假设上一个例子里引入了噪声， 当我们用同样的方法做奇异值分解，我们得到如下非零奇异值 σ 1 = 14.15，σ 2 = 4.67，σ 3 = 3.00，σ 4 = 0.21，σ 5 = 0.19，...，σ 15 = 0.05显然，前三个奇异值比其他的大很多，说明其中包括了绝大部分信息。如果我们只要前三个， M u 1 σ 1 v 1 T + u 2 σ 2 v 2 T + u 3 σ 3 v 3 T 我们就实现了图像的降噪。 Noisy image Improved image
PS：一直以来对SVD分解似懂非懂，此文为译文，原文以细致的分析+大量的可视化图形演示了SVD的几何意义。能在有限的篇幅把这个问题讲解的如此清晰，实属不易。原文举了一个简单的图像处理问题，简单形象，真心希望路过的各路朋友能从不同的角度阐述下自己对SVD实际意义的理解，比如 个性化推荐中应用了SVD，文本以及Web挖掘的时候也经常会用到SVD。 原文： We recommend a singular value decomposition 关于线性变换部分的一些知识可以猛戳这里 奇异值分解(SVD) --- 线性变换几何意义 奇异值分解 ( The singular value decomposition ) 该部分是从几何层面上去理解二维的SVD：对于任意的 2 x 2 矩阵，通过SVD可以将一个相互垂直的网格(orthogonal grid)变换到另外一个相互垂直的网格。 我们可以通过向量的方式来描述这个事实: 首先，选择两个相互正交的单位向量 v 1 和 v 2 , 向量 M v 1 和 M v 2 正交。 u 1 和 u 2 分别表示 M v 1 和 M v 2 的单位向量， σ 1 * u 1 = M v 1 和 σ 2 * u 2 = M v 2 。 σ 1 和 σ 2 分别表示这不同方向向量上的模，也称作为矩阵 M 的奇异值。 这样我们就有了如下关系式 M v 1 = σ 1 u 1 M v 2 = σ 2 u 2 我们现在可以简单描述下经过 M 线性变换后的向量 x 的表达形式。由于向量 v 1 和 v 2 是正交的单位向量，我们可以得到如下式子： x = ( v 1 x ) v 1 + ( v 2 x ) v 2 这就意味着： M x = ( v 1 x ) M v 1 + ( v 2 x ) M v 2 M x = ( v 1 x ) σ 1 u 1 + ( v 2 x ) σ 2 u 2 向量内积可以用向量的转置来表示，如下所示 v x = v T x 最终的式子为 M x = u 1 σ 1 v 1 T x + u 2 σ 2 v 2 T x M = u 1 σ 1 v 1 T + u 2 σ 2 v 2 T 上述的式子经常表示成 M = U Σ V T u 矩阵的列向量分别是 u 1 , u 2 ， Σ 是一个对角矩阵，对角元素分别是对应的 σ 1 和 σ 2 ， V 矩阵的列向量分别是 v 1 , v 2 。上角标 T 表示矩阵 V 的转置。 这就表明任意的矩阵 M 是可以分解成三个矩阵。 V 表示了原始域的标准正交基， u 表示经过 M 变换后的co-domain的标准正交基， Σ 表示了 V 中的向量与 u 中相对应向量之间的关系。(V describes an orthonormal basis in the domain, and U describes an orthonormal basis in the co-domain, and Σ describes how much the vectors in V are stretched to give the vectors in U.) 如何获得奇异值分解？ ( How do we find the singular decomposition? ) 事实上我们可以找到任何矩阵的奇异值分解，那么我们是如何做到的呢？假设在原始域中有一个单位圆，如下图所示。经过 M 矩阵变换以后在co-domain中单位圆会变成一个椭圆，它的长轴( M v 1 )和短轴( M v 2 )分别对应转换后的两个标准正交向量，也是在椭圆范围内最长和最短的两个向量。 换句话说，定义在单位圆上的函数 | M x | 分别在 v 1 和 v 2 方向上取得最大和最小值。这样我们就把寻找矩阵的奇异值分解过程缩小到了优化函数 | M x | 上了。结果发现（具体的推到过程这里就不详细介绍了）这个函数取得最优值的向量分别是矩阵 MT M 的特征向量。由于MTM是对称矩阵，因此不同特征值对应的特征向量都是互相正交的，我们用vi 表示MTM的所有特征向量。奇异值 σ i = | M v i | ， 向量 u i 为 M v i 方向上的单位向量。但为什么 u i 也是正交的呢？ 推倒如下： σ i 和 σ j 分别是不同两个奇异值 M v i = σ i u i M v j = σ j u j . 我们先看下 M v i M v j ，并假设它们分别对应的奇异值都不为零。一方面这个表达的值为0，推到如下 M v i M v j = v i T M T M v j = v i M T M v j = λ j v i v j = 0 另一方面，我们有 M v i M v j = σ i σ j u i u j = 0 因此， u i 和 u j 是正交的。但实际上，这并非是求解奇异值的方法，效率会非常低。这里也主要不是讨论如何求解奇异值，为了演示方便，采用的都是二阶矩阵。 应用实例(Another example) 现在我们来看几个实例。 实例一 经过这个矩阵变换后的效果如下图所示 在这个例子中，第二个奇异值为 0，因此经过变换后只有一个方向上有表达。 M = u 1 σ 1 v 1 T . 换句话说，如果某些奇异值非常小的话，其相对应的几项就可以不同出现在矩阵 M 的分解式中。因此，我们可以看到矩阵 M 的秩的大小等于非零奇异值的个数。 实例二 我们来看一个奇异值分解在数据表达上的应用。假设我们有如下的一张 15 x 25 的图像数据。 如图所示，该图像主要由下面三部分构成。 我们将图像表示成 15 x 25 的矩阵，矩阵的元素对应着图像的不同像素，如果像素是白色的话，就取 1，黑色的就取 0. 我们得到了一个具有375个元素的矩阵，如下图所示 如果我们对矩阵M进行奇异值分解以后，得到奇异值分别是 σ 1 = 14.72 σ 2 = 5.22 σ 3 = 3.31 矩阵M就可以表示成 M = u 1 σ 1 v 1 T + u 2 σ 2 v 2 T + u 3 σ 3 v 3 T v i 具有15个元素， u i 具有25个元素， σ i 对应不同的奇异值。如上图所示，我们就可以用123个元素来表示具有375个元素的图像数据了。 实例三 减噪(noise reduction) 前面的例子的奇异值都不为零，或者都还算比较大，下面我们来探索一下拥有零或者非常小的奇异值的情况。通常来讲，大的奇异值对应的部分会包含更多的信息。比如，我们有一张扫描的，带有噪声的图像，如下图所示 我们采用跟实例二相同的处理方式处理该扫描图像。得到图像矩阵的奇异值： σ 1 = 14.15 σ 2 = 4.67 σ 3 = 3.00 σ 4 = 0.21 σ 5 = 0.19 ... σ 15 = 0.05 很明显，前面三个奇异值远远比后面的奇异值要大，这样矩阵 M 的分解方式就可以如下： M u 1 σ 1 v 1 T + u 2 σ 2 v 2 T + u 3 σ 3 v 3 T 经过奇异值分解后，我们得到了一张降噪后的图像。 实例四 数据分析(data analysis) 我们搜集的数据中总是存在噪声：无论采用的设备多精密，方法有多好，总是会存在一些误差的。如果你们还记得上文提到的，大的奇异值对应了矩阵中的主要信息的话，运用SVD进行数据分析，提取其中的主要部分的话，还是相当合理的。 作为例子，假如我们搜集的数据如下所示： 我们将数据用矩阵的形式表示： 经过奇异值分解后，得到 σ 1 = 6.04 σ 2 = 0.22 由于第一个奇异值远比第二个要大，数据中有包含一些噪声，第二个奇异值在原始矩阵分解相对应的部分可以忽略。经过SVD分解后，保留了主要样本点如图所示 就保留主要样本数据来看，该过程跟PCA( principal component analysis)技术有一些联系，PCA也使用了SVD去检测数据间依赖和冗余信息. 总结 (Summary) 这篇文章非常的清晰的讲解了SVD的几何意义，不仅从数学的角度，还联系了几个应用实例形象的论述了SVD是如何发现数据中主要信息的。在netflix prize中许多团队都运用了矩阵分解的技术，该技术就来源于SVD的分解思想，矩阵分解算是SVD的变形，但思想还是一致的。之前算是能够运用矩阵分解技术于个性化推荐系统中，但理解起来不够直观，阅读原文后醍醐灌顶，我想就从SVD能够发现数据中的主要信息的思路，就几个方面去思考下如何利用数据中所蕴含的潜在关系去探索个性化推荐系统。也希望路过的各位大侠不吝分享呀。 References: Gilbert Strang, Linear Algebra and Its Applications . Brooks Cole William H. Press et al , Numercial Recipes in C: The Art of Scientific Computing . Cambridge University Press. Dan Kalman, A Singularly Valuable Decomposition: The SVD of a Matrix, The College Mathematics Journal 27 (1996), 2-23. If You Liked This, You're Sure to Love That , The New York Times , November 21, 2008.
PS：一直以来对SVD分解似懂非懂，此文为译文，原文以细致的分析+大量的可视化图形演示了SVD的几何意义。能在有限的篇幅把这个问题讲解的如此清晰，实属不易。原文举了一个简单的图像处理问题，简单形象，真心希望路过的各路朋友能从不同的角度阐述下自己对SVD实际意义的理解，比如 个性化推荐中应用了SVD，文本以及Web挖掘的时候也经常会用到SVD。 原文： We recommend a singular value decomposition 简介 SVD实际上是数学专业内容，但它现在已经渗入到不同的领域中。SVD的过程不是很好理解，因为它不够直观，但它对矩阵分解的效果却非常好。比如，Netflix（一个提供在线电影租赁的公司）曾经就悬赏100万美金，如果谁能提高它的电影推荐系统评分预测准确率提高10%的话。令人惊讶的是，这个目标充满了挑战，来自世界各地的团队运用了各种不同的技术。最终的获胜队伍BellKor's Pragmatic Chaos采用的核心算法就是基于SVD。 SVD提供了一种非常便捷的矩阵分解方式，能够发现数据中十分有意思的潜在模式。在这篇文章中，我们将会提供对SVD几何上的理解和一些简单的应用实例。 线性变换的几何意义 ( The geometry of linear transformations ) 让我们来看一些简单的线性变换例子，以 2 X 2 的线性变换矩阵为例，首先来看一个较为特殊的，对角矩阵： 从几何上讲， M 是将二维平面上的点(x,y)经过线性变换到另外一个点的变换矩阵，如下图所示 变换的效果如下图所示，变换后的平面仅仅是沿 X 水平方面进行了拉伸3倍，垂直方向是并没有发生变化。 现在看下矩阵 这个矩阵产生的变换效果如下图所示 这种变换效果看起来非常的奇怪，在实际环境下很难描述出来变换的规律 ( 这里应该是指无法清晰辨识出旋转的角度，拉伸的倍数之类的信息)。还是基于上面的对称矩阵，假设我们把左边的平面旋转45度角，然后再进行矩阵 M 的线性变换，效果如下图所示： 看起来是不是有点熟悉？ 对的，经过 M 线性变换后，跟前面的对角矩阵的功能是相同的，都是将网格沿着一个方向拉伸了3倍。 这里的 M 是一个特例，因为它是对称的。非特殊的就是我们在实际应用中经常遇见一些 非对称的，非方阵的矩阵。如上图所示，如果我们有一个 2 X 2 的对称矩阵 M 的话，我们先将网格平面旋转一定的角度， M 的变换效果就是在两个维度上进行拉伸变换了。 用更加数学的方式进行表示的话，给定一个对称矩阵 M ，我们可以找到一些相互正交 V i ，满足 M V i 就是沿着 V i 方向的拉伸变换，公式如下： M v i = λ i v i 这里的 λ i 是拉伸尺度(scalar)。从几何上看， M 对向量 V i 进行了拉伸，映射变换。 V i 称作矩阵 M 的特征向量(eigenvector)， λ i 称作为矩阵 M 特征值(eigenvalue)。这里有一个非常重要的定理，对称矩阵 M 的特征向量是相互正交的。 如果我们用这些特征向量对网格平面进行线性变换的话，再通过 M 矩阵对网格平面进行线性换的效果跟对 M 矩阵的特征向量进行线性变换的效果是一样的。 对于更为普通的矩阵而言，我们该怎么做才能让一个原来就是相互垂直的网格平面(orthogonal grid), 线性变换成另外一个网格平面同样垂直呢？ PS： 这里的垂直如图所示，就是两根交错的线条是垂直的。 经过上述矩阵变换以后的效果如图 从图中可以看出，并没有达到我们想要的效果。我们把网格平面旋转 30 度角的话，然后再进行同样的线性变换以后的效果，如下图所示 让我们来看下网格平面旋转60度角的时候的效果。 嗯嗯，这个看起来挺不错的样子。如果在精确一点的话，应该把网格平面旋转 58.28 度才能达到理想的效果。
机器学习相关——SVD分解 前面写了个简单的线性代数系列文章，目的就是让大家在接触SVD分解前，先了解回忆一下线性代数的基本知识，有助于大家理解SVD分解。不至于一下被大量的线性代数操作搞晕。这次终于开始正题——SVD的介绍了。 所谓SVD，就是要把矩阵进行如下转换： A = USV T the columns of U are the eigenvectors of the AA T matrix and the columns of V are the eigenvectors of the A T A matrix. V T is the transpose of V and S is a diagonal matrix. By definition the nondiagonal elements of diagonal matrices are zero. The diagonal elements of S are a special kind of values of the original matrix. These are termed the singular values of A . 1The Frobenius Norm 一个矩阵所有元素的平方和再开方称为这个矩阵的Frobenius Norm。特殊情况下，行矩阵的Frobenius Norm为该向量的长度 2 计算A转置 A*At At*A 3 计算S 在SVD中，将AAt的特征值从大到小排列，并开方，得到的就是奇异值。 比如上图中，特征值为40，10.因此奇异值为6.32,3.16。矩阵的奇异值有如下特性： a 矩阵的奇异值乘积等于矩阵行列式的值 6.32*3.16 = 20 = |A| b 矩阵A的 Frobenius Norm等于奇异值的平方和的开方 总结一下计算S的步骤：1 计算 A T 和 A T A；2 计算 A T A 的特征值，排序并开方。 由此可以得到S，下面来看如何计算 U，V T 4 计算V和 V T 利用 A T A 的特征值来计算特征向量 既然刚才提到V就是特征向量的组合，那么 5 计算U A = USV T AV = USV T V = US AVS -1 = USS -1 U = AVS -1 6 计算SVD 可以看出，SVD可以对矩阵进行分解重建。 7 降维的SVD 如果我们只保留前k个最大的奇异值，前k列个U，前k行个V，相当于将数据中占比不大的噪音进行过滤，这样既可以有效地对数据进行泛化，又起到了降维减少运算量的目的。是不是很奇妙？ 8 实际用途 我们实际的工作中，经常会用到这种降维方法。包括现在非常火的推荐问题，以及LSI问题都对SVD有着广泛的应用。 举个最常用的例子， 在文本挖掘中：A就是 t (term) 行 d (document) 列的矩阵，每列是一篇文章，每行是一个单词，每个单元格的当前单词在当前文章里的出现次数。 U 是一个 t行 r列 的矩阵， V 是一个 r行 d 列 的矩阵， S 是一个 r行 r列的对角矩阵。这里 r 的大小是 A的秩。那么U和V中分别是A的奇异向量，而S是A的奇异值。AA'的正交单位特征向量组成U，特征值组成S'S，A'A的正交单位特征向量组成V，特征值（与AA'相同）组成SS'。 希望大家细细体会，多多交流，一起进步。 分类: 机器学习与算法 标签: 机器学习 绿色通道： 好文要顶 关注我 收藏该文 与我联系 ~大器晚成~ 关注 - 3 粉丝 - 48 +加关注 2 0 (请您对文章做出评价) « 博主前一篇： 线性代数——特征值与特征向量 » 博主后一篇： 使用awk进行文本处理 posted @ 2012-01-19 10:57 ~大器晚成~ 阅读(1277) 评论( 0 ) 编辑 收藏
标签: svd
