20.SVD分解及其应用

20.1 奇异值的概念

设存在复数矩阵\(A_{mn}\)，且\(R(A)=r\)

则对矩阵\((A^H\cdot A)_{nn}\)的特征值进行分析如下：

设存在n阶行向量\(x\)，则可将\((A^H\cdot A)_{nn}\)转换为二次型，可得：

\[\qquad \quad x\cdot A^H \cdot A \cdot x^H \]

\[=(Ax)^H\cdot Ax \]

\[=||Ax||^2 \geq0 \]

由二次型相关定理可得：

\[\tag{1} 二次型(x\cdot A^H \cdot A \cdot x^H) \geq0 \Leftrightarrow (A^H\cdot A)_{nn}的特征值\lambda_i \geq 0 (i=1,2,3,..,n) \]

设矩阵A的特征向量为p，且p中元素不重复，令\(x=py\)，则由二次型与对角化相关性质可得：

\[x\cdot A^H \cdot A \cdot x^H =y \Lambda y^H （\Lambda 为A的对角阵） \]

由矩阵的秩相关性质可得：

\[\tag{2} R(y\Lambda y^H)=R(\Lambda)=R(A)=r \]

由式(1)式(2)可得，矩阵A的特征值为：：

\[\tag{3} \lambda_1 \geq \lambda_2 \geq \lambda_3 \geq … \geq \lambda_r = \lambda_{r+1}=\lambda_{r+2}=…=\lambda_n \]

奇异值的定义如下：

\[设存在\sigma_i=\sqrt{\lambda_i} （i=1,2,3,…,n） \]

\[\tag{4} 则称\sigma_i为矩阵A的奇异值。若A=O，则\sigma_i均为0（i=1,2,3,…,n） \]

20.2 酉矩阵及其应用

20.2.1 酉矩阵相关概念

酉矩阵的定义如下：

设存在复数可逆矩阵\(U\)，若\(U\)满足：

\[\tag{5} U\cdot U^H=E(即U为正交阵) \]

则称\(U\)为\(酉矩阵\)

\(通过奇异值和酉矩阵对m \times n的矩阵进行表示：\)

设：存在复数矩阵\(A_{mn}\)，矩阵A满足：\(R(A)=r，且A的非零奇异值为\sigma_i（i=1,2,3,…,r）\)

存在酉矩阵\(U_{mr}\)、酉矩阵\(V_{nr}\)，其中：

\[酉矩阵U_{mr}=[u_1,u_2,u_3,…,u_r] \]

\[酉矩阵V_{nr} =[v_1,v_2,v_3,…,v_r] \]

设A的非零奇异值所形成的对角阵为：

\[\Sigma_{rr}= \begin{bmatrix} \sigma_1\\ &\sigma_2\\ &&\sigma_3\\ &&……\\ &&&\sigma_r \end{bmatrix} \]

则由SVD算法可得：

\[\tag{6} U^H \cdot A \cdot V= \begin{bmatrix} \Sigma&O\\ O&O \end{bmatrix} \]

则矩阵\(A\)可表示为：

\[A=U \cdot U^H \cdot A \cdot V \cdot V^H = U \cdot \Sigma \cdot V^H \]

\[= {[u_1,u_2,u_3,…,u_r]}_{mr} \cdot {\begin{bmatrix} \sigma_1\\ &\sigma_2\\ &&\sigma_3\\ &&……\\ &&&\sigma_r \end{bmatrix}}_{rr} \cdot {\begin{bmatrix} v_1\\ v_2\\ v_3\\ …\\ v_r\\ \end{bmatrix}}_{rn} \]

\[\tag{7} =u_1\sigma_1v_1+u_2\sigma_2v_2+u_3\sigma_3v_3+…+u_r\sigma_rv_r \]

20.2.2 酉矩阵应用1：SVD图像压缩算法

由20.2.1相关内容，可对\(A_{mn}\)进行SVD压缩，具体如下：

对\(A_{mn}进行完整存储\)：

由式(7)，若采用SVD图像压缩算法，对\(A_{mn}\)进行完整存储，共需存储的元素个数为\((m+n+1)\cdot r\)个，即：

\[u_i共需存储：m \cdot r 个 \]

\[v_j共需存储： n \cdot r 个 \]

\[\sigma_i共需存储：r个 \]

则完整存储的压缩效率为：

\[\frac{(m+n+1)\cdot r}{m \cdot n} \]

\(对A_{mn}进行部分存储：\)

由式(7)，若采用SVD图像压缩算法，对\(A\)进行部分存储

即：保留式(7)中的前k项，舍去后r-k项，则有：

\[u_i共需存储：m \cdot k 个 \]

\[v_j共需存储： n \cdot k 个 \]

\[\sigma_i共需存储：k个 \]

则部分存储的压缩效率为：

\[\frac{(m+n+1)\cdot k}{m \cdot n} \]

部分存储的误差率为：

\[1-\frac{\Sigma_{j=1}^k \sigma_j}{\Sigma_{i=1}^r \sigma_i} \]

20.2.3 酉矩阵应用2：深度学习加速

深度学习算法中，矩阵相乘计算的次数对算法执行效率的影响较大

由20.2.1相关内容，可通过矩阵\(A_{mn}\)执行深度学习相关算法，以下对其算法执行效率进行分析：

设存在矩阵\(X_{n \times 1}\)，则有：

一般情况下的矩阵相乘计算次数：

\[A_{m \times n} \cdot X_{n \times 1} \]

\[上式的矩阵相乘计算次数为：m\times n 次 \]

采用SVD加速后的矩阵相乘计算次数：

\[A_{m \times n} \cdot X_{n \times 1} \]

\[=U_{m \times r} \cdot \Sigma_{r \times r} \cdot V^H_{r\times n} \cdot X_{n \times 1} \]

\[\tag{8} =(U \cdot \Sigma)_{m \times r} \cdot V^H_{r\times n} \cdot X_{n \times 1} \]

\[\tag{9} =(U \cdot \Sigma)_{m \times r} \cdot (V^H \cdot X)_{r \times 1} \]

\[\tag{10} =[(U \cdot \Sigma) \cdot (V^H \cdot X)]_{m \times 1} \]

由上可得：

\[(8)式中，U \cdot \Sigma产生r次乘法计算 \]

\[(9)式中，V^H \cdot X产生r\cdot n次乘法计算 \]

\[(10)式中，(U \cdot \Sigma) \cdot (V^H \cdot X)产生r\cdot m次乘法计算 \]

则产生的总乘法次数为：

\[r\cdot (m+n+1) 次 \]

来源链接：https://www.cnblogs.com/efancn/p/18760127