奇异值分解 SVD

一基本知识

  A是一个m*n的矩阵,那么A的SVD分解为\(A_{mn} = U_{mm}\Sigma _{mn}V^T_{nn}\),其中\(U^TU = I\),\(V^TV = I\),UV的列向量是矩阵\(A^TA\)的特征向量,V的列向量是矩阵\(AA^T\)的特征向量,\(\Sigma\)只在对角线上有非零元素,称为A的奇异值(Singular value),并按照降序排列,并且值为\(A^TA\)的特征值的算术平方根。SVD的分解不唯一。

  我们知道实对称阵必正交相似于对角矩阵。这里假设有这样的svd分解。

  则\(A^TA = V\Sigma^TU^TU\Sigma{V^T} = V\Sigma^T \Sigma{V^T}\) 即实对称矩阵,对角相似。V的列向量即特征向量。

  同理\(AA^T = U\Sigma V^TV\Sigma^TU^T = U\Sigma \Sigma^TU^T\),U的列向量为特征向量。

  由于对角化过程中选取特征值的不同,以及特征向量的正交化的过程,所以SVD的分解也是不唯一的。

  因为不可能所有的矩阵都是n阶方阵,所以对于一般性的矩阵,用SVD分解具有通用性。

二SVD的应用

  特征值评估了每个分量对综合的贡献。在SVD中,大多数情况下,前10%的奇异值占了全部奇异值之和的99%以上,我们可以取前r个分量近似描述举证。\(A_{mn} \approx U_{mr}\Sigma _{rr}V^T_{rn}\),从而可以把矩阵稀疏表示,减少存储的空间。可以用来图像降噪常认为小的特征值是噪声,所以取前r个分量可以达到降噪的效果。也可以用于图像的压缩,保留较大的特征值。

1.图像压缩

# -*- coding: utf-8 -*-
"""
Created on 2016/8/25
@author: zephyr
"""
from PIL import Image
import numpy as np def restore(sigma , u, v, k):
m = len(u)
n = len(v)
a = np.zeros((m,n))
for i in range(k+1):
ui = u[:,i].reshape(m,1)
vi = v[i].reshape(1,n)
a = a + sigma[i]*np.dot(ui,vi)
a[a < 0] = 0
a[a > 255] = 255
return np.rint(a).astype("uint8") if __name__ == "__main__":
A = Image.open('svdgun.jpg',"r")
a = np.array(A)
for k in range(100):
u, sigma, v = np.linalg.svd(a[:,:, 0])
R = restore(sigma,u,v,k)
u, sigma, v = np.linalg.svd(a[:,:, 1])
G = restore(sigma, u, v, k)
u, sigma, v = np.linalg.svd(a[:,:, 2])
B = restore(sigma, u, v, k)
I = np.stack((R,G,B),2)
Image.fromarray(I).save("svd_"+str(k)+".jpg")

奇异值分解 SVD

如图所示分别是取特征值1,2,5,27的时候图片压缩之后的效果,取到27的时候已经和原图基本差不多了。

2.SVD与PCA 

  PCA是数据降维的方法,PCA方法是对矩阵\(X_{np}\)进行线性变换,映射到一组新的特征\(T_{np}\)上,满足\(X_{np} = T_{np}W_{pp}\)并且在特征T中协方差按照从大到小的顺序排列。本质上是一基的变化,使得变化后的数据有着最大的方差,方差用来描述稳定性,模型越稳定越好,方差小好,对于数据来说,大的方差才能发现其中各自的特性,比如数据都一样,也就没有意义。

  PCA的全部工作简单点说,就是对原始的空间中顺序地找一组相互正交的坐标轴,第一个轴是使得方差最大的,第二个轴是在与第一个轴正交的平面中使得方差最大的,第三个轴是在与第1、2个轴正交的平面中方差最大的,这样假设在N维空间中,我们可以找到N个这样的坐标轴,我们取前r个去近似这个空间,这样就从一个N维的空间压缩到r维的空间了,但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。SVD得出的奇异向量也是从奇异值由大到小排列的,按PCA的观点来看,就是方差最大的坐标轴就是第一个奇异向量,方差次大的坐标轴就是第二个奇异向量。

  不妨用SVD来做PCA。

  根据SVD,有\(X_{np} = U_{nn}\Sigma_{np}V^T_{pp}\)。

  \(X^TX\)是对协方差的一个估计,也就是为什么我们做PCA的时候要使数据中心化,因为中心化之后,协方差矩阵与这里的\(X^TX\)只相差系数\(\frac{1}{n}\)。

  从而有\(X^TX = V{\Sigma^2}V^T = W^TT^2W \),如果\(W = V^T\),那么\(T^TT\)等于\(\Sigma^T\Sigma\)一样是从大到小排列。T也即所求。

  所以有\(X_{np} = \Sigma_{np}V_{pp}^T\),求PCA,可以通过SVD分解求解。PCA可以说是对SVD的一个包装。

  求PCA,可以先SVD分解,然后两边同右乘\(V\)或同左乘\(U^T\),可以分别进行列和行的压缩提取。上面说的是右乘\(V\)得\(X_{np}\),也可以类似的得到\(X_{pn}\)。不像\(X^TX\)求特征值,特征向量只能求得一个方向。

参考:http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html

上一篇:【线性代数】6-7:SVD分解(Singular Value Decomposition-SVD)


下一篇:数值分析之奇异值分解(SVD)篇