【原】奇异值分解（SVD）及其应用

老马的程序人生 2020-08-17

展开全文

奇异值分解的定义

SVD（Singular Value Decomposition）可以理解为：将一个比较复杂的矩阵用更小更简单的3个子矩阵的相乘来表示，这3个小矩阵描述了大矩阵重要的特性。

定义：矩阵的奇异值分解是指将一个秩为的实矩阵分解为三个实矩阵乘积的形式：

其中是阶正交矩阵（的列向量称为左奇异向量），是阶正交矩阵（的列向量称为右奇异向量），是矩形对角矩阵，称为奇异值矩阵，对角线上的元素称为奇异值。

是一个的对角阵，的对角线元素是的前个奇异值（非负，降序）。

知识点：任意一个实矩阵可以由其外积展开式表示

其中为矩阵，是列向量和行向量的外积，为奇异值，通过矩阵的奇异值分解得到。

知识点：奇异值在矩阵中按照从大到小排列，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。我们可以用最大的个奇异值的矩阵和相乘来近似描述矩阵，从而实现了降维、减少数据存储、提升计算性能等效果。

奇异值分解的计算

设矩阵的奇异值分解为，则有

即对称矩阵和的特征分解可以由矩阵的奇异值分解矩阵表示。

证明：的特征值非负。

令是矩阵，那么是对称矩阵且可以正交对角化，让是的单位正交基且构成的特征向量，是对应的特征值，那么对，

所以的所有特征值都非负，如果必要，通过重新编号我们可以假设特征值的重新排列满足

的奇异值是的特征值的平方根，记为，且它们递减顺序排列。

可见，对进行奇异值分解需要求矩阵的特征值及其对应的标准正交的特征向量来构成正交矩阵的列，特征值的平方根得到奇异值也即得到奇异值矩阵。

证明：假设是包含特征向量的上的标准正交基，重新整理使得对应的特征值满足。若有个非零奇异值，则是的一个正交基，且。

当不等于时，。

所以，是一个正交基。由于向量的长度是的奇异值，且因为有个非零奇异值，为非零向量。所以线性无关，且属于。

对任意属于的，如，我们可以写出，且

这样，在中，这说明是的一个正交基，因此。

由于是的一个正交基，将每一个单位化得到一个标准正交基，此处

将扩充为的单位正交基。

取

由构造可知，和是正交矩阵，

即：，从而得到。

知识点：任意给定一个实矩阵，其奇异值分解一定存在，但并不唯一。

奇异值分解的实现

1. 手动实现

# 实现奇异值分解， 输入一个numpy矩阵，输出 U, sigma, V
import numpy as np


# 基于矩阵分解的结果，复原矩阵
def rebuildMatrix(U, sigma, V):
    a = np.dot(U, sigma)
    a = np.dot(a, np.transpose(V))
    return a


# 基于特征值的大小，对特征值以及特征向量进行倒序排列。
def sortByEigenValue(Eigenvalues, EigenVectors):
    index = np.argsort(-1 * Eigenvalues)
    Eigenvalues = Eigenvalues[index]
    EigenVectors = EigenVectors[:, index]
    return Eigenvalues, EigenVectors


# 对一个矩阵进行奇异值分解
def SVD(matrixA, NumOfLeft=None):
    # NumOfLeft是要保留的奇异值的个数，也就是中间那个方阵的宽度
    # 首先求transpose(A)*A
    matrixAT_matrixA = np.dot(np.transpose(matrixA), matrixA)
    # 然后求右奇异向量
    lambda_V, X_V = np.linalg.eig(matrixAT_matrixA)
    lambda_V, X_V = sortByEigenValue(lambda_V, X_V)
    # 求奇异值
    sigmas = lambda_V
    # python里很小的数有时候是负数
    sigmas = list(map(lambda x: np.sqrt(x) if x > 0 else 0, sigmas))

    sigmas = np.array(sigmas)
    sigmasMatrix = np.diag(sigmas)
    if NumOfLeft is None:
        # 大于0的特征值的个数
        rankOfSigmasMatrix = len(list(filter(lambda x: x > 0, sigmas)))
    else:
        rankOfSigmasMatrix = NumOfLeft

    # 特征值为0的奇异值就不要了
    sigmasMatrix = sigmasMatrix[0:rankOfSigmasMatrix, :]

    # 计算左奇异向量
    # 初始化一个左奇异向量矩阵，这里直接进行裁剪
    X_U = np.zeros((matrixA.shape[0], rankOfSigmasMatrix))
    for i in range(rankOfSigmasMatrix):
        X_U[:, i] = np.transpose(np.dot(matrixA, X_V[:, i]) / sigmas[i])

    # 对右奇异向量和奇异值矩阵进行裁剪
    X_V = X_V[:, 0:rankOfSigmasMatrix]
    sigmasMatrix = sigmasMatrix[0:rankOfSigmasMatrix, 0:rankOfSigmasMatrix]

    return X_U, sigmasMatrix, X_V

A = np.array([[4, 11, 14], [8, 7, -2]])
X_U, sigmasMatrix, X_V = SVD(A)
print(A)
# [[ 4 11 14]
#  [ 8  7 -2]]

print(X_U.shape)  # (2, 2)
print(sigmasMatrix.shape)  # (2, 2)
print(X_V.shape)  # (3, 2)
print(rebuildMatrix(X_U, sigmasMatrix, X_V))
# [[ 4. 11. 14.]
#  [ 8.  7. -2.]]

2. 使用numpy.linalg.svd函数

import numpy as np

A = np.array([[4, 11, 14], [8, 7, -2]])
print(A)
# [[ 4 11 14]
#  [ 8  7 -2]]

u, s, vh = np.linalg.svd(A, full_matrices=False)
print(u.shape)  # (2, 2)
print(s.shape)  # (2,)
print(vh.shape)  # (2, 3)

a = np.dot(u, np.diag(s))
a = np.dot(a, vh)
print(a)
# [[ 4. 11. 14.]
#  [ 8.  7. -2.]]