【线性代数】1.9SVD分解应用_综合

记 $U=(u1,?,ur,ur+1,?,um)\boldsymbol U=\left(u_1,\cdots,u_r,u_{r+1},\cdots,u_m\right)$ ， $V=(v1,?,vr,vr+1,?,vn)\boldsymbol V=\left(v_1,\cdots,v_r,v_{r+1},\cdots,v_n\right)$ ，SVD分解可以写成
$A=σ1u1v1T+σ2u2v2T+?+σrurvrT(?)\boldsymbol{A}=\sigma _1u_1v_{1}^{T}+\sigma _2u_2v_{2}^{T}+\cdots +\sigma _ru_rv_{r}^{T}\left( * \right)$

1.图像压缩

?? $(?)$ 式中， $A$ 为 $m×nm\times n$ 矩阵，如果A为衣服图像数据，每个像素点需要一个float（4个字节）存储，那么存储这幅图像需要 $m×n×4m\times n\times 4$ 个字节。
?? $u_iv_{i}^{T}$ 为 $m×nm\times n$ 矩阵，每个 $u_i$ 为 $m×1m\times 1$ 矩阵、 $v_i$ 为 $1×n1\times n$ 矩阵，则存储 $u_iv_{i}^{T}$ 需要 $(m+n)×4(m+n)\times 4$ 个字节。由矩阵 $Σ=(σ1,σ2,?,σr)\varSigma =\left( \sigma _1,\sigma _2,\cdots ,\sigma _r \right)$ ，其中元素关系： $σ1≥σ2≥?≥σr>0\sigma _1\ge \sigma _2\ge \cdots \ge \sigma _r>0$ ，所以SVD分解得到的各项
$σ1u1v1T>σ2u2v2T>?>σrurvrT\sigma _1u_1v_{1}^{T}>\sigma _2u_2v_{2}^{T}>\cdots >\sigma _ru_rv_{r}^{T}$ ??利用SVD分解可以对图像进行压缩，图像矩阵 $A$ 可用 $σiurviT\sigma _iu_rv_{i}^{T}$ 的前 $k$ 项( $k?rk\ll r$ )，则图像储存需要 $(m+n+1)×4×k?4mn(m+n+1)\times 4\times k \ll 4mn$ ，这样就可以对图像进行压缩。采用这种方式存储图像，损失函数为：
$err(k)=1?∑i=1kσi2∑i=1rσi2e_{rr}^{\left( k \right)}=1-\frac{\sum_{i=1}^k{\sigma _{i}^{2}}}{\sum_{i=1}^r{\sigma _{i}^{2}}}$ $k$ 越大，损失越小，更能充分接近真实的图像。例：如下图
【线性代数】1.9SVD分解应用
传统网络图片传输与现代传输的原理

2.矩阵乘法加速

$A$ 为 $200×100200\times 100$ ， $A$ 采取SVD分解
$A=σ1u1v1T+σ2u2v2T+?+σrurvrT\boldsymbol{A}=\sigma _1u_1v_{1}^{T}+\sigma _2u_2v_{2}^{T}+\cdots +\sigma _ru_rv_{r}^{T}$ 取前25项近似表示 $A$
$A≈σ1u1v1T+σ2u2v2T+?+σ25u25v25T=[u1u2?u25][σ1σ2?σ25][v1Tv2T?v25T]=U200×25Λ25×25V25×100\boldsymbol{A}\approx \sigma _1u_1v_{1}^{T}+\sigma _2u_2v_{2}^{T}+\cdots +\sigma _{25}u_{25}v_{25}^{T}=\left[ \begin{matrix} u_1& u_2& \cdots& u_{25}\\ \end{matrix} \right] \left[ \begin{matrix} \sigma _1& & & \\ & \sigma _2& & \\ & & \ddots& \\ & & & \sigma _{25}\\ \end{matrix} \right] \left[ \begin{array}{l} v_{1}^{T}\\ v_{2}^{T}\\ \vdots\\ v_{25}^{T}\\ \end{array} \right] =U_{200\times 25}\varLambda _{25\times 25}V_{25\times 100}$
将上式右侧进行处理，将前两项矩阵 $U$ 和 $Λ\varLambda$ 看作一个矩阵，得到 $U200×25Λ25×25V25×100=M200×25N25×100U_{200\times 25}\varLambda _{25\times 25}V_{25\times 100}=M_{200\times 25}N_{25\times 100}$ 。
??在计算矩阵 $A x = M N x$ 时， $M N$ 是 $200×100200\times 100$ 的矩阵，计算 $M N x$ 需要 $200×100=20000200\times 100=20000$ 次.如果考虑先计算 $N x$ ，需要 $25×100=250025\times 100=2500$ 次，得到 $25×125\times 1$ 的矩阵 $Q$ ，再计算 $M Q$ ，需要 $200×25=5000200\times 25=5000$ 次，总共需要7500次，这样就达到了加速矩阵计算的目的。

3.作业

1.学习Numpy中SVD分解的函数.
函数：np.linalg.svd(a,full_matrices=1,compute_uv=1)
参数：
? a是一个形如(M,N)矩阵
? full_matrices的取值是为0或者1，默认值为1，这时u的大小为(M,M)，v的大小为(N,N) . 否则u的大小为(M,K)， v的大小为(K,N) ，K=min(M,N).
? compute_uv的取值是为0或者1，默认值为1，表示计算u,s,v. 为0的时候只计算s.
返回值：
? 总共有三个返回值u,s,v
? u大小为(M,M)，s大小为(M,N)，v大小为(N,N)
? A = usv
有几点需要注意的地方：

python中的svd分解得到的VT就是V的转置，这一点与matlab中不一样，matlab中svd后得到的是V，如果要还原的话还需要将V转置一次，而Python中不需要。
Python中svd后得到的sigma是一个行向量， Python中为了节省空间只保留了A的奇异值，所以我们需要将它还原为奇异值矩阵。同时需要注意的是，比如一个55大小的矩阵的奇异值只有两个，但是他的奇异值矩阵应该是55的，所以后面的我们需要手动补零，并不能直接使用diag将sigma对角化。

In [1]: import numpy as npIn [2]: from numpy import linalg as laIn [3]: S = np.zeros([5,5])In [4]: A = np.random.randint(1,25,[5, 5])In [5]: u, sigma, vt=la.svd(A)In [6]: print(A)
[[18 15 18  6 21][15 11 23 12  6][22  5 23 16 21][10 12  5 15 24][22 20 14 10 18]]In [7]: for i in range(5):...:     S[i][i] = sigma[i]...:In [8]: tmp = np.dot(u,S)In [9]: print(np.dot(tmp,vt))
[[18. 15. 18.  6. 21.][15. 11. 23. 12.  6.][22.  5. 23. 16. 21.][10. 12.  5. 15. 24.][22. 20. 14. 10. 18.]]

2、列举2个SVD分解的作用
??在图像处理领域，奇异值不仅可以应用在数据压缩上，还可以对图像去噪。如果一副图像包含噪声，我们有理由相信那些较小的奇异值就是由于噪声引起的。当我们强行令这些较小的奇异值为0时，就可以去除图片中的噪声。
??使用SVD做推荐系统也可以看成是主成分分析的过程，找到用户-电影矩阵中最大的r个奇异值，进行分解构成r行的矩阵U(代表用户)和r列的矩阵V(代表电影)，这个就是各个用户对电影打分的主要的影响因素，依据这个就可以对于用户的打分进行预测。