奇异值分解原理及Python实例

2018-11-28  本文已影响0人  biolearn

2018.11.28 星期三 晴 biolearn

奇异值分解 SVD（Singular Value Decomposition）是一种重要的矩阵分解方法，可以看做是特征分解在任意矩阵上的推广，SVD是在机器学习领域广泛应用的算法。

特征值和特征向量

定义：设 A 是 n 阶矩阵，若数 λ 和 n 维非零向量 x 满足
Ax= λ x
那么，数 λ 称为方阵 A 的特征值，x 称为 A 的对应于特征值 λ 的特征向量

说明：特征向量 x 不等于0，特征值问题仅仅针对方阵；n 阶方阵 A 的特征值，就是使得齐次线性方程组 (A-λE)x = 0 有非零解的 λ 值，即满足方程 | A - λE| = 0 的 λ 都是方阵 A 的特征值

特征分解

对方阵 A 求取特征值和特征值对应的特征向量可以将方阵 A 进行特征分解为
A=VΛV^{-1}
证明：假设方阵 A 有 n 个线性无关的特征向量 v1, v2, v3, ... , vn，对应的特征值为 λ1, λ2, λ3, ... , λn，令 V = ( v1, v2, v3, ... , vn)
AV=A(v_1,v_2,v_3,...,v_n)\\=(Av_1,Av_2,Av_3,...,Av_n)\\\\=(λ_1v_1,λ_2v_2,λ_3v_3,...,λ_nv_n)\\\\ =(v_1,v_2,v_3,...,v_n)\left[ \begin{matrix} λ_1 & 0 & \cdots& 0 \\ 0 & λ_2 & \cdots& 0\\ \vdots & \vdots & \cdots& \vdots\\ 0 & 0 &\cdots& λ_n \end{matrix} \right]\\\\ =VΛ
在进行特征分解时，一般将 V 的这 n 个特征向量标准化，即使得 V 中 n 个特征向量为标准正交基，满足
V^TV=I\\ 即\,\,\, V^T=V^{-1}
所以方阵 A 的特征分解公式为
A=VΛV^{-1}=VΛV^T

奇异值分解

矩阵的特征分解要求矩阵必须为方阵，那么对于不是方阵的矩阵而言则可以使用 SVD 进行分解，假设 A 是一个 m * n 的矩阵，则存在一个分解使得
A_{m\times n}=U_{m\times m}Λ_{m\times n}V^T_{n\times n}
其中 U 为左奇异值矩阵，Λ 为矩阵 A 奇异值，除了主对角线上的元素以外全为0，V 为右奇异值矩阵

如何求这 SVD 分解后的三个矩阵？

虽然矩阵 A 不是方阵，但是 ATA 是一个 n * n 的方阵，于是对 ATA 这个方阵进行特征值和特征向量计算则有
(A^TA)v_i=λ_iv_i\\\\ (A^TA)=VΛV^T
通过 ATA 方阵计算得到的特征向量是一个 n * n 维的矩阵，也就是 SVD 公式中的 V 矩阵

证明：
A^TA=(UΛV^T)^T(UΛV^T)=VΛ^TU^TUΛT^T=VΛ^2V^T
可以看到 ATA 的特征向量就是 SVD 中的 V 矩阵，同时可以得到特征值矩阵等于奇异值矩阵的平方，也就是说特征值 λ 和奇异值 σ 存在如下关系
\sigma_i=\sqrt\lambda_i
类似的，通过计算 AAT 方阵的特征值和特征向量可以得到 SVD 中的 U 矩阵

利用Python进行SVD分解对图像压缩

在 Python 中进行 SVD 分解非常简单，利用 Numpy 模块中的 np.linalg.svd() 函数，比如u,sigma,v = np.linalg.svd(A)，其中 u，v 分别返回矩阵 A 的左右奇异向量，而 sigma 返回的是按从大到小的顺序排列的奇异值，利用 Python 进行 SVD 分解对图形进行压缩，也就是读取图片的像素矩阵，然后对矩阵进行 SVD 分解得到对应的奇异值和奇异向量，然后对奇异值和奇异向量进行筛选例如取前10%的数据，实现对图像的压缩

import numpy as np
import os
from PIL import Image

def restore(sigma, u, v, K):  # 奇异值、左特征向量、右特征向量
    m = len(u)
    n = len(v[0])
    a = np.zeros((m, n))
    for k in range(K):
        uk = u[:, k].reshape(m, 1)
        vk = v[k].reshape(1, n)
        a += sigma[k] * np.dot(uk, vk)   # 前 k 个奇异值的加和
    a = a.clip(0, 255)
    return np.rint(a).astype('uint8')

if __name__ == "__main__":
    A = Image.open(".\\Pokonyan.jpg", 'r')
    output_path = r'.\SVD_Out'
    a = np.array(A)
    print('type(a) = ', type(a))
    print('原始图片大小：', a.shape)

   # 图片有RGB三原色组成，所以有三个矩阵
    u_r, sigma_r, v_r = np.linalg.svd(a[:, :, 0])    # 奇异值分解
    u_g, sigma_g, v_g = np.linalg.svd(a[:, :, 1])
    u_b, sigma_b, v_b = np.linalg.svd(a[:, :, 2])
    
   # 仅使用前1个，2个，...，50个奇异值的结果
    K = 50 
    for k in range(1, K+1):
        R = restore(sigma_r, u_r, v_r, k)
        G = restore(sigma_g, u_g, v_g, k)
        B = restore(sigma_b, u_b, v_b, k)
        I = np.stack((R, G, B), axis=2)   # 将矩阵叠合在一起，生成图像
        Image.fromarray(I).save('%s\\svd_%d.jpg' % (output_path, k))

可以看到，使用前50个奇异值就能大致还原原图像，也就是可以通过仅仅使用奇异值矩阵中前面一部分的值表示整体的情况，从而实现了特征的降维，这是因为在奇异值矩阵中奇异值减少的特别快，可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵

上一篇下一篇

猜你喜欢

热点阅读