2018.11.28 星期三 晴 biolearn
奇異值分解 SVD（Singular Value Decomposition）是一種重要的矩陣分解方法，可以看做是特征分解在任意矩陣上的推廣，SVD是在機(jī)器學(xué)習(xí)領(lǐng)域廣泛應(yīng)用的算法。
特征值和特征向量
定義：設(shè) A 是 n 階矩陣，若數(shù) λ 和 n 維非零向量 x 滿足
那么，數(shù) λ 稱為方陣 A 的特征值，x 稱為 A 的對(duì)應(yīng)于特征值 λ 的特征向量
說(shuō)明：特征向量 x 不等于0，特征值問(wèn)題僅僅針對(duì)方陣；n 階方陣 A 的特征值，就是使得齊次線性方程組 (A-λE)x = 0 有非零解的 λ 值，即滿足方程 | A - λE| = 0 的 λ 都是方陣 A 的特征值
特征分解
對(duì)方陣 A 求取特征值和特征值對(duì)應(yīng)的特征向量可以將方陣 A 進(jìn)行特征分解為
證明：假設(shè)方陣 A 有 n 個(gè)線性無(wú)關(guān)的特征向量 v1, v2, v3, ... , vn，對(duì)應(yīng)的特征值為 λ1, λ2, λ3, ... , λn，令 V = ( v1, v2, v3, ... , vn)
在進(jìn)行特征分解時(shí)，一般將 V 的這 n 個(gè)特征向量標(biāo)準(zhǔn)化，即使得 V 中 n 個(gè)特征向量為標(biāo)準(zhǔn)正交基，滿足
所以方陣 A 的特征分解公式為
奇異值分解
矩陣的特征分解要求矩陣必須為方陣，那么對(duì)于不是方陣的矩陣而言則可以使用 SVD 進(jìn)行分解，假設(shè) A 是一個(gè) m * n 的矩陣，則存在一個(gè)分解使得
其中 U 為左奇異值矩陣，Λ 為矩陣 A 奇異值，除了主對(duì)角線上的元素以外全為0，V 為右奇異值矩陣
如何求這 SVD 分解后的三個(gè)矩陣？
雖然矩陣 A 不是方陣，但是 ATA 是一個(gè) n * n 的方陣，于是對(duì) ATA 這個(gè)方陣進(jìn)行特征值和特征向量計(jì)算則有
通過(guò) ATA 方陣計(jì)算得到的特征向量是一個(gè) n * n 維的矩陣，也就是 SVD 公式中的 V 矩陣
證明：
可以看到 ATA 的特征向量就是 SVD 中的 V 矩陣，同時(shí)可以得到特征值矩陣等于奇異值矩陣的平方，也就是說(shuō)特征值 λ 和奇異值 σ 存在如下關(guān)系
類似的，通過(guò)計(jì)算 AAT 方陣的特征值和特征向量可以得到 SVD 中的 U 矩陣
利用Python進(jìn)行SVD分解對(duì)圖像壓縮
在 Python 中進(jìn)行 SVD 分解非常簡(jiǎn)單，利用 Numpy 模塊中的 np.linalg.svd() 函數(shù)，比如u,sigma,v = np.linalg.svd(A)，其中 u，v 分別返回矩陣 A 的左右奇異向量，而 sigma 返回的是按從大到小的順序排列的奇異值，利用 Python 進(jìn)行 SVD 分解對(duì)圖形進(jìn)行壓縮，也就是讀取圖片的像素矩陣，然后對(duì)矩陣進(jìn)行 SVD 分解得到對(duì)應(yīng)的奇異值和奇異向量，然后對(duì)奇異值和奇異向量進(jìn)行篩選例如取前10%的數(shù)據(jù)，實(shí)現(xiàn)對(duì)圖像的壓縮
- 原圖
- 進(jìn)行 SVD 分解，選擇前 50 個(gè)奇異值
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 個(gè)奇異值的加和
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三原色組成，所以有三個(gè)矩陣
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個(gè)，2個(gè)，...，50個(gè)奇異值的結(jié)果
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))
- 將圖像進(jìn)行奇異值分解后的圖像
- 使用前50個(gè)奇異值的圖像
可以看到，使用前50個(gè)奇異值就能大致還原原圖像，也就是可以通過(guò)僅僅使用奇異值矩陣中前面一部分的值表示整體的情況，從而實(shí)現(xiàn)了特征的降維，這是因?yàn)樵谄娈愔稻仃囍衅娈愔禍p少的特別快，可以用最大的k個(gè)的奇異值和對(duì)應(yīng)的左右奇異向量來(lái)近似描述矩陣
