SVD奇异值分解——矩阵压缩

• 基本概念
• • 应用
• 算法核心
• • 酉矩阵
• 分解过程
• • 推导过程
  • 结论
• 实例数据
• 代码演示
• • 效果展示

• SVD
   奇异值分解。将矩阵进行压缩。大幅度减少内存消耗，提高运行速度。

 数据降维、推荐算法、自然语言处理

A = U ∑ V t A=Usum V^t A=U∑Vt

对于任意矩阵A，我们总能够将其分解位三个矩阵 U 、 ∑ 、 V t U、sum、V^t U、∑、Vt

• U为酉矩阵
• ∑ sum ∑为对角阵
• V t V^t Vt为酉矩阵

• 满足 A T = A − 1 A^T=A^{-1} AT=A−1

将原始矩阵分解为三个矩阵

• A = U ∑ V t A=Usum V^t A=U∑Vt
• A t = ( U ∑ V t ) T = V ( U ∑ ) T = V ∑ t U T A^t=(Usum V^t)^T=V(Usum)^T=Vsum^tU^T At=(U∑Vt)T=V(U∑)T=V∑tUT

1. A A T = U ∑ V t V ∑ T U T = U ∑ 2 U T AA^T=Usum V^tVsum^TU^T=Usum^2U^T AAT=U∑VtV∑TUT=U∑2UT
2. A T A = V ∑ T U T U ∑ V t = V ∑ 2 V T A^TA=Vsum^TU^TUsum V^t=Vsum^2V^T ATA=V∑TUTU∑Vt=V∑2VT

import numpy as np
from PIL import Image
import matplotlib.pyplot as plt


def pic_compress(k, pic_array):
    global u, sigma, vt, sig, new_pic

    u, sigma, vt = np.linalg.svd(pic_array)
    sig = np.eye(k) * sigma[: k]
    new_pic = np.dot(np.dot(u[:, :k], sig), vt[:k, :])  # 还原图像
    size = u.shape[0] * k + sig.shape[0] * sig.shape[1] + k * vt.shape[1]  # 压缩后大小
    return new_pic, size


filename = "timg.jpg"
ori_img = np.array(Image.open(filename))
new_img, size = pic_compress(100, ori_img)
print("original size:" + str(ori_img.shape[0] * ori_img.shape[1]))
print("compress size:" + str(size))
fig, ax = plt.subplots(1, 2)
ax[0].imshow(ori_img, cmap='gray')
ax[0].set_title("before compress")
ax[1].imshow(new_img, cmap='gray')
ax[1].set_title("after compress")
plt.show()

original size:1365760