Deep Learning——矩阵分解

矩阵分解简介

由于最近在看机器学习相关书籍，里面涉及到很多矩阵分解的知识点，上网翻阅相关知识点，发现机器学习书上和网上相关解释和推导非常简化，不易从根本上理解矩阵分解的知识，从而不能发现矩阵分解的本质。故我想以一个数学推导的角度（不是工科应用的角度），从根本的概念来推导这些矩阵分解的定理，从本质理解矩阵分解。

矩阵分解在数学，机器学习，工程学中的意义和目的有以下几点：一、矩阵求逆，总所周知，在矩阵求逆时，涉及到伴随矩阵与行列式的复杂计算，如果对矩阵进行适当分解，在求逆，就会省去这些运算。二、矩阵的存储，矩阵分解可以省很多存储空间，例如一个100x100的矩阵，需要10000个元素，而将其分解成100x20与20x100的两个矩阵时，只需要4000个元素既可以。三、矩阵的性质，矩阵分解后，更容易理解矩阵的性质，就如正整数可以分解成质数，原子可以分解成质子一样，更容易看到其性质。

对于矩阵的常用分解为：满秩分解、LU分解、LDU分解、特征分解、QR分解、奇异值分解、极分解。下面我将对其进行详细的推导论证。不过在论证之前，先梳理一下用到的基础知识。这样可以保证读者在看到陌生的概念时，不用翻阅其他资料。

矩阵分解用到的基础知识

一、线性映射、线性变换、以及他们与矩阵的关系

线性映射（ linear mapping）是从一个向量空间V到另一个向量空间W的映射且保持加法运算和数量乘法运算。
$\sigma$ (α+β)= $\sigma$ (α)+ $\sigma$ (β)
$\sigma$ (kα)=k $\sigma$ (α)

线性变换是一个特殊的线性映射，从向量空间V映射到自己的线性映射叫做线性变换。

任意线性映射都可找到一个矩阵与之对应，任意矩阵都可找到一个线性映射与之对应。任意方阵都可以找到一个线性变化与之对应，任意线性变化都可找到一个方阵与之对应。但需要注意的是，线性映射与矩阵的对应关系必须给定每个空间的基，线性映射和线性变化在不同基下的矩阵是不一样的。

对于任意矩阵A_mxn,可以找到n维空间V到m维空间W的一个线性映射 $\sigma$ , $\sigma$ 如下定义，对任意 $\alpha$ 属于V，有 $\sigma$ ( $\alpha$ )=A $\alpha$ (这是线性变换矩阵的坐标表示，下文还有一种表示方式，两者等价)。以下证明由此定义的 $\sigma$ 是V到W的线性映射。
$\alpha$ 是n维，A是mxn的，所以A $\alpha$ 是m维的，所以A $\alpha$ 属于W空间，又可以验证满足上面的加分和数乘运算，所以 $\sigma$ 是V到W的线性映射。

对于任意的n维空间V到m维空间W的线性映射 $\sigma$ ，都可以找到一个mxn的矩阵A与之对应，对应关系为：
对任意 $\alpha$ 属于V，有 $\sigma$ ( $\alpha$ )=A $\alpha$ ，其中A $\alpha$ 属于W。

定理1 ：

线性映射 $\sigma$ 在给定基下的矩阵表示A是唯一的。

证明：设线性映射 $\sigma$ 是n维线性空间V到m维线性空间W的线性映射， $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n是n维空间的一组基。 $\eta$ ₁， $\eta$ ₂，... $\eta$ _m是m维空间给定的一组基，
反证法，若线性映射 𝜎 在给定基下的矩阵表示A是不唯一，
设有两个分别为A和B，
使得，在同一组下有 $\sigma$ ( $\alpha$ )=A $\alpha$ 和 $\sigma$ ( $\alpha$ )=B $\alpha$ 对任意的 $\sigma$ 属于V成立。
由于 $\alpha$ 属于V，所以在基 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n下， $\alpha$ 的坐标为k₁，k₂，...k_n ,
所以同时又 $\sigma$ ( $\alpha$ )=A(k₁，k₂，...k_n)^T, $\sigma$ ( $\alpha$ )=B(k₁，k₂，...k_n)^T 而 $\sigma$ ( $\alpha$ )在W空间中，且W空间的基给定，所以在W空间给定基下的坐标是唯一的，所以
A(k₁，k₂，...k_n)^T=B(k₁，k₂，...k_n)^T
由于上式对V空间中的任意向量都成立。所以A=B，所以假设不成立，所以定理得证。

在上面的证明中，若 $\alpha$ ＝ $\varepsilon$ ₁，则 $\alpha$ 的坐标为(1,0,...0)^T_nx1 ,则A $\alpha$ =(a₁₁,a₂₁,...a_m1)^T_mx1 ,而(a₁₁,a₂₁,...a_m1)^T_mx1是向量A $\alpha$ 在W空间基 $\eta$ ₁， $\eta$ ₂，... $\eta$ _m下的坐标。所以有 $\sigma$ （ $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n）＝（ $\eta$ ₁， $\eta$ ₂，... $\eta$ _m）A(这是线性变换矩阵的另一种表示方式)

定理2 ：

设V的基为 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n，W的基为 $\eta$ ₁， $\eta$ ₂，... $\eta$ _m ，已给m×n矩阵A，则存在唯一的线性映射 $\sigma$ ，它在这两个基下的矩阵表示为A。

证明：反证法，假设存在两个不一样的线性变换 $\sigma$ ₁, $\sigma$ ₂。在给定两组基下的矩阵为A。
则有：
$\sigma$ ₁( $\alpha$ )=A $\alpha$
$\sigma$ ₂( $\alpha$ )=A $\alpha$
其中对于任意的 $\alpha$ 属于V都成立。
所以对任意的 $\alpha$ 属于V都有 $\sigma$ ₁( $\alpha$ )＝ $\sigma$ ₂( $\alpha$ )
所以 $\sigma$ ₁＝ $\sigma$ ₂
所以与假设矛盾，定理的证。

二、矩阵的等价

设V的一组基为 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n，W的一组基为 $\eta$ ₁， $\eta$ ₂，... $\eta$ _m ，V到W空间的线性映射 $\sigma$ 在两组基下的矩阵为A。V的另一组基为 $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^'，W的另一组基为 $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^',则V到W空间的线性映射 $\sigma$ 在两组基下的矩阵为B。
因为 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n与 $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^'是V的不同的两组基，所以存在过度矩阵P，有
( $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n)P ＝( $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^')
因为 $\eta$ ₁， $\eta$ ₂，... $\eta$ _m 与 $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^'是V的不同的两组基，所以存在过度矩阵Q，有
( $\eta$ ₁， $\eta$ ₂，... $\eta$ _m )Q ＝( $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^')
过度矩阵必可逆（下文有给出证明），
因为V到W空间的线性映射 $\sigma$ 在给定第一组基下的矩阵为A，所以有，对任意的 $\alpha$ 属于V，其在 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n基下的坐标表示为（k₁,k₂,....k_n）^T
有 $\sigma$ (（k₁,k₂,....k_n）^T)=A（k₁,k₂,....k_n）^T ，而A（k₁,k₂,....k_n）^T为映射到W空间的向量在基 $\eta$ ₁， $\eta$ ₂，... $\eta$ _m下的坐标表示。
同理因为V到W空间的线性映射 $\sigma$ 在给你第二组基下的矩阵为B，所以有，对上面同一向量 $\alpha$ 属于V，其在 $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^'基下的坐标表示为（l₁,l₂,....l_n）^T 有
$\sigma$ (（l₁,l₂,....l_n）^T =B（l₁,l₂,....l_n）^T ，B（l₁,l₂,....l_n）^T 为映射到W空间的向量在基 $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^'下的坐标表示。
而 $\alpha$ 在V中是同一向量，V到W空间的映射也为同一映射，所以映射到W空间的向量也为同一向量。所以有
( $\eta$ ₁， $\eta$ ₂，... $\eta$ _m)A（k₁,k₂,....k_n）^T=( $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^')B（l₁,l₂,....l_n）^T （1）
而又有
( $\eta$ ₁， $\eta$ ₂，... $\eta$ _m )＝( $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^')Q^-1 （2）
(k₁,k₂,....k_n)^T＝P(l₁,l₂,....l_n）^T （3）
所以将（2）（3）带入到（1）中得到
( $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^')Q^-1AP(l₁,l₂,....l_n）^T&=( $\eta$ ₁^'， $\eta$ ₂^'，... $\eta$ _m ^')B（l₁,l₂,....l_n）^T
所以 Q^-1AP=B 。

过度矩阵必可逆，因为( $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n)线性无关，所以基构成的矩阵秩为n可逆，( $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^')线性无关，所以基构成的矩阵秩为n可逆，所以P也可逆

如果对于两个矩阵A_mxn,B_mxn，存在可逆矩阵P_nxn和可逆矩阵Q_mxm满足以下式子
Q^-1AP=B
则称矩阵A与矩阵B等价。

三、矩阵的相似

上面推出等价关系是以线性映射为基础，当线性映射变为线性变换时，又可推导出什么结论。

c设 $\sigma$ 是空间V上的线性变换， $\sigma$ 在基 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n下的矩阵为A， $\sigma$ 在基 $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^'下的矩阵为B，
$\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n到 $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^'的过度矩阵为P。
即：
（ $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n）P＝（ $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^'）
所以有：
$\sigma$ ( $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n)=( $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n)A
和
$\sigma$ ( $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^')=( $\varepsilon$ ₁^'， $\varepsilon$ ₂^'，... $\varepsilon$ _n^')B
所以和上面推导等价关系一样的步骤可得到：
P^-1AP=B

所以推出相似的定义，如果对于两个方阵A_nxn，B_nxn,存在可逆矩阵P_nxn，有
P^-1AP=B
则称A与B相似。

四、初等矩阵和初等变换

在这里介绍一类简单的矩阵和变换，初等矩阵和初等变换。

所谓初等变换，有三种
1、用一非零的数字乘以矩阵的某一行（列）。
2、矩阵的一行（列）加到另一行（列）。
3、互换矩阵两行（列）的位置。

所谓初等矩阵，是指由单位矩阵经过一次矩阵初等变换得到的矩阵。
由初等矩阵的定义可以看出，初等矩阵只有三种形式：
1、P_i,j 单位矩阵的第i行和第j行互换。
2、P_i(k) 单位矩阵的第i行乘以非零k倍。
2、P_i,j(k) 单位矩阵的第i行乘以非零k倍加到第j行。

由上面初等矩阵的形式可以看出，初等矩阵都是可逆矩阵，初等变换都是可逆变换。
如果两个矩阵A，B，A通过初等变换可以得到B，那么A和B成为等价。
这里说的矩阵等价和上文说的矩阵等价是一样的，A=PB，P为一系列初等矩阵相乘得到，是可逆矩阵，设Q为P的逆，则可以写成 A=Q^-1BE，所以形式和上文一致。

五、置换矩阵

设P 是一个 m×n 的 (0,1) 矩阵，如 m≤n且 P*P^t=E，则称 P为一个 m×n的置换矩阵。其中P^t是P的转置矩阵，E是m阶单位方阵。

引理1

当 m≦n时，一个 m×n 的(0,1) 矩阵P为置换矩阵的充要条件是P的每一行恰有一个 1，每一列最多只有一个 1。当P是方阵时，每行和每列有且仅有一个1.

置换矩阵的性质：
1、置换矩阵为方阵时必是可逆矩阵
2、一个矩阵左成一个置换方阵，相当于对矩阵进行互换，一个矩阵右乘一个置换矩阵时，相当于对矩阵进列互换
3、置换方阵一定是正交矩阵。

主子式和顺序主子式

主子式：对于n阶矩阵A，取出标号相同的k行和k列的共有元素构成矩阵的行列式为矩阵A的k阶主子式，例如：取第一，第三，第五行与第一，第三，第五列的公有的值构成一个3阶矩阵，此三阶矩阵的行列式就是矩阵的三阶主子式。

顺序主子式：对于n阶矩阵A，取前k行和前k列构成矩阵的行列式为其k阶顺序主子式。

顺序主子式的相关性质：
1、一个n阶矩阵的所有顺序主子式大于零，当且仅当其构成的二次型为正定二次型，此矩阵称作正定矩阵。
2、一个n阶矩阵的所有顺序主子式小于零，当且仅当其构成的二次型为负定二次型，此矩阵称作负定矩阵。
3、一个n阶矩阵的所有顺序主子式大于等于零，当且仅当其构成的二次型为半正定二次型，此矩阵称作半正定矩阵。
4、一个n阶矩阵的所有顺序主子式不等与零，该矩阵可进行LU分解，且分解唯一。
由于矩阵分解这一块不涉及二次型知识，故不对前三天进行证明，第四条将在下面的矩阵LU分解中证明。

矩阵的满秩分解

定理3

对于任意给定非零矩阵A_mxn,都可以进行以下分解
A=FG
其中F为mxr矩阵，G为rxn矩阵，r为矩阵A的秩，F列满秩，G行满秩。此时A=FG 为矩阵A的满秩分解。

证明：对于任意给定的非零矩阵A_mxn，都可以经过一系列的初等行变换和初等列变换，变为如下形式的矩阵

$\left[ \begin{array} {cccc} E&0\\ 0&0\\ \end{array} \right]$

其中E为ｒ阶单位矩阵，ｒ为A的秩。既有如下等式成了

$A= P [ \begin{array} {cccc} E&0\\ 0&0\\ \end{array}] Q$

其中P为一系列mxm初等矩阵的乘积，Q为一系列nxn初等矩阵的乘积。因为初等矩阵为可逆矩阵，所以P,Q是可逆矩阵。

而
$\left[ \begin{array} {cccc} E&0\\ 0&0\\ \end{array} \right]=\left[ \begin{array} {cccc} E\\ 0\\ \end{array} \right]*\left[ \begin{array} {cccc} E&0\\ \end{array} \right]$

所以
$A= P\left[ \begin{array} {cccc} E\\ 0\\ \end{array} \right]*\left[ \begin{array} {cccc} E&0\\ \end{array} \right] Q$

因为P_mxm,Q_nxn是可逆矩阵，所以令

$F=P\left[ \begin{array} {cccc} E\\ 0\\ \end{array} \right]$

$G=\left[ \begin{array} {cccc} E&0\\ \end{array} \right] Q$

F为列满秩矩阵，G为行满秩矩阵，且秩都为r.定理得到证明

矩阵的LU分解

LU分解只对方阵而言，但并非任意的方阵都可进行LU分解。

定理4

对于任意的方阵A，存在置换矩阵P，使得PA=LU，其中L为单位下三角矩阵，U为上三角矩阵。当A的对角线上没有零元素时，A＝LU。

证明：对于任意方阵A，若A对角线上没有０元素，则存在一系列的初等矩阵P_i,j(k) ，其中i＞ｊ，使得这一系列的初等矩阵乘以A，将打A变成一个上三角矩阵。既
$PA＝U$
因为初等矩阵可逆，所以一系列初等矩阵乘积P也可逆，又因为ｉ＞ｊ，所以这一些列初等矩阵为单位下三角矩阵，所以P是可逆的单位下三角矩阵。记Ｌ＝P^-1,又因为单位下三角矩阵的逆矩阵还是单位下三角矩阵。所以A=LU,其中L为单位下三角矩阵，U为上三角矩阵。

对于对角线上有0元素的矩阵A，若０元素所在的列，存在一个元素不为领，则存在一个置换矩阵P，使得PA对角线上的元素全不为零，若０元素所在的列都为零，则在将A转化成上三角矩阵时，不处理该列，因为该列对角线下面的元素已经为0.所以当对角线上有0元素时，存在一个置换矩阵P，使得PA=LU，L为单位下三角矩阵，U为上三角矩阵，所以定理的证。

对于矩阵的LU分解，

定理5

设A为ｎ阶非奇异的实矩阵，A存在唯一分解式A＝LU的充要条件为A的n-1阶顺序主子式D_i $\neq$ 0,(i=1,2...n-1)，其中L为单位下三角矩阵，U为上三角矩阵

证明：必要性：因为A是非奇异矩阵，所有|A|=|L|* |U| $\neq$ 0,而|L|=1,|U|=u₁u₂...u_n,其中u_i为U的对角线上的第i个元素。所以u_i $\neq$ 0。

对于A的k阶顺序主子式对应的矩阵A_k,有A_k的任意元素a_i,j是原来A的a_i,j,因为A=LU，所以有
a_i,j=l_i,1u_1,j+l_i,2u_2,j+...+ l_i,nu_n,j
其中当r>i时，有l_i,r=0 ，当r>j时,有u_r,j=0.
所以上式可化简为：
a_i,j=l_i,1u_1,j+l_i,2u_2,j+...+ l_i,min(i,j)u_min(i,j),j

所以A_k=L_kU_k,L_k为L的k阶顺序主子式对应的矩阵，U_k为U的k阶顺序主子式对应的矩阵，所以有
|A_k|=|L_k||U_k|
而|L_k|=1，|U_k| =u₁u₂...u_k,又因为u_i $\neq$ 0,
所以 |A_k| $\neq$ 0，所以A的k阶顺序主子式不等于零。所以必要性得证。

充分性：分两步先证明可分解性，再证明唯一性。
（数学归纳法）当A为1阶非零常数a时，a=1*a,1是退化单位下三角，a 时退化上三角矩阵。满足充分性。

设A为k-1阶矩阵时，定理成立，既：对于k-1阶非奇异矩阵，若他的k-2顺序主子式不为零，则有唯一LU分解，A_k-1=L_k-1U_k-1

当A为k阶矩阵的时候，A可写为以下形式：
$A=\left[ \begin{array} {cccc} A_{k-1}&\alpha\\ \beta^{T}&a_{nn}\\ \end{array} \right]$

因为A的k-1阶顺序主子式不为零，所以A_k-1是可逆的，且其所有顺序主子式都不为零，有假设得到，A_k-1=L_k-1U_k-1

所以，有：
$A=\left[ \begin{array} {cccc} L_{k-1}U_{k-1}&\alpha\\ \beta^{T}&a_{kk}\\ \end{array} \right]$

其中，L_{k-1}与U_{k-1}可逆。
对于A矩阵左乘一个矩阵为
$\left[ \begin{array} {cccc} E_{k-1}&0\\ -\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}&1\\ \end{array} \right]A=\left[ \begin{array} {cccc} E_{k-1}&0\\ -\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}&1\\ \end{array} \right]\left[ \begin{array} {cccc} L_{k-1}U_{k-1}&\alpha\\ \beta^{T}&a_{kk}\\ \end{array} \right]=\left[ \begin{array} {cccc} L_{k-1}U_{k-1}&\alpha\\ 0&a_{kk}-\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}\alpha\\ \end{array} \right]=\left[ \begin{array} {cccc} L_{k-1}&0\\ 0&1\\ \end{array} \right]\left[ \begin{array} {cccc} U_{k-1}&L_{k-1}^{-1}\alpha\\ 0&a_{kk}-\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}\alpha\\ \end{array} \right]$

所以有
$A=\left[ \begin{array} {cccc} E_{k-1}&0\\ -\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}&1\\ \end{array} \right]^{-1}\left[ \begin{array} {cccc} L_{k-1}&0\\ 0&1\\ \end{array} \right]\left[ \begin{array} {cccc} U_{k-1}&L_{k-1}^{-1}\alpha\\ 0&a_{kk}-\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}\alpha\\ \end{array} \right]$

单位下三角矩阵的逆还是单位下三角矩阵，单位下三角矩阵乘以单位下三角矩阵还是单位下三角矩阵，所以设
$L_k=\left[ \begin{array} {cccc} E_{k-1}&0\\ -\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}&1\\ \end{array} \right]^{-1}\left[ \begin{array} {cccc} L_{k-1}&0\\ 0&1\\ \end{array} \right]$
$U_k=\left[ \begin{array} {cccc} U_{k-1}&L_{k-1}^{-1}\alpha\\ 0&a_{kk}-\beta^{T}U_{k-1}^{-1}L_{k-1}^{-1}\alpha\\ \end{array} \right]$

所以有A_k=L_kU_k，而 A_k是非奇异的，所以令u_kk=a_kk- $\beta$ ^TU_k-1^-1L_k-1^-1 $\alpha$ ,u_kk $\neq$ 0

所以，定理充分性中的可分解性得证。

下面证明唯一性（反证法）
假设A纯在两种LU分解，则存在A=L₁U₁与A=L₂U₂同时成立。
所以有
L₁U₁=L₂U₂
所以
L₂^-1L₁=U₂U₁^-1
由于单位下三角矩阵的逆还是单位下三角矩阵，单位下三角矩阵乘以单位下三角矩阵还是单位下三角矩阵，而上三角矩阵乘以上三角矩阵还是上三角矩阵。
所以等式左边是单位下三角矩阵，等式右边是上三角矩阵，所以L₂^-1L₁=U₂U₁^-1 =E
所以L₁=L₂，U₁=U₂，这与假设矛盾，所以唯一性得到证明。

矩阵LU分解求解

上面给出了矩阵LU分解的相关理论和定理，下面给出矩阵LU分解的具体解法。

方法—、

对于给定的矩阵A（可进行LU分解）,构造以下矩阵
$\left[ \begin{array} {cccc} A&E\\ \end{array} \right]$
对此矩阵进行行变换，把A转化成上三角矩阵A₁,则由于进行了换变换，原来矩阵中的E变为了B。
所以上面矩阵变成
$\left[ \begin{array} {cccc} A_1&B\\ \end{array} \right]$
此时B就是矩阵LU分解中的L，A₁就是矩阵分解中的U。

方法二（Doolittle算法）、

类似待定系数法，若A可进行LU分解，设
$A=\left[ \begin{array} {cccc} 1&0&\cdots&\cdots&0\\ l_{21}&1&0&\cdots&0\\ \cdots&\cdots&\cdots\\ l_{n1}&\cdots&\cdots&\cdots&1\\ \end{array} \right]\left[ \begin{array} {cccc} u_{11}&u_{12}&\cdots&\cdots&u_{1n}\\ 0&u_{22}&u_{23}&\cdots&u_{2n}\\ \cdots&\cdots&\cdots\\ 0&\cdots&\cdots&\cdots&u_{nn}\\ \end{array} \right]$

则有
$\begin{cases} u_{1j}=a_{1j}& \text{j=1,2,3...n}\\ l_{i1}=a_{i1}/u_{11}& \text{i=2,3,4...n} \end{cases}$
和
$\begin{cases} u_{ij}=a_{ij}-\sum_{k=1}^{i-1}l_{ik}u_{kj} & \text{j=i,i+1...n}\\ l_{ij}=(a_{ij}-\sum_{k=1}^{j-1}l_{ik}u_{kj})/u_{jj}& \text{i=j+1,...n} \end{cases}$

求解上面方程，即可得到L和U的每一个元素。具体求解顺序为下图（紧凑格式）

紧凑格式.PNG

对于矩阵得LU分解其本质是高斯消元法。应用为一般解线性方程组上，例如 :

$AX=Y$
可以利用矩阵得LU分解得到以下公式：

$\begin{cases} UX=Z\\ LZ=Y \end{cases}$

公式中，L与U都是三角矩阵，所以大大减少了计算量。

矩阵得LDU分解

有了上面矩阵LU分解得介绍，可以很快的得到矩阵LDU分解相关的定理。

定理6

设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L，对角矩阵D＝diag(u₁,u₂,u₃.....u_n)和单位上三角矩阵U
使得
$A=LDU$
的充分必要条件是A的所有顺序主子式均非零，即D_k $\neq$ 0。并且有
$u_1=a_{11}, u_k=D_k/D_{k-1},k=2,3,...n$

再矩阵LU分解定理证明时，可以将U分解成DU，其中D=diag(u₁,u₂,u₃.....u_n)，U为单位上三角矩阵。所以这个定理的证明只需证明
$u_1=a_{11}, u_k=D_k/D_{k-1},k=2,3,...n$

证明：由上面LU的证明，可以看除，A=LU分解时，A的k阶顺序主子式就等于L的k阶主子式对应的矩阵乘以U的k阶主子式对应的矩阵。所以A的k阶主子式D_k=u₁u₂u₃...u_1k.所以上面公式得到证明

注意

由矩阵LU分解定理和矩阵LDU分解定理可知,并不是所有的非奇异矩阵都可进行LU与LDU分解.但此时一定存在一个置换矩阵P,使得PA可进行LU分解和LDU分解.其证明过程可参考上文定理4.

对于矩阵的LDU分解，当A是非奇异的是对称矩阵时，若A的各阶顺序主子式都不为零，那么有以下分解.
$A=LDL^{T}$
证明:因为A的各阶顺序主子式都不为零,所以A可唯一的分解为LDU.即A=LDU
又因为A是对称矩阵,所以有
$LDU=U^TDL^T$
因为U^T是单位下三角,L^T是单位上三角,且分解式唯一,所以L=U^T,U=L^T.所以以上公式成立.

矩阵的正交分解

正交矩阵

如果一个n阶实矩阵A，A的任意两列构成的向量正交且任意列向量的模为1，那么A成为正交矩阵．即满足A^TA=E.有这个公式得到,A^T=A^-1
进一步有AA^T=E ,所以推出A的任意行向量也正交.

所以判断一个A是否是正交矩阵,以下方法等价,A^T=A^-1 ,A^TA=E,AA^T=E
由此可以看出正交矩阵的行列式,只能等于1或者-1

正交矩阵的性质

谈论正交矩阵的性质等价与谈论正交变换的性质.由上文我们得到,线性变换在一组基下与一方阵一一对应.所以对于正交矩阵,可以找到一个线性变换,使这一线性变换在标准正交基下的矩阵是正交矩阵.所以研究正交矩阵和研究正交变换是等价的.

设 $\sigma$ 是一线性变换,这一线性变换在n维空间V标准正交基 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n下的矩阵为正交矩阵A,
对于空间V中任意两个向量 $\alpha$ , $\beta$ ,在标准正交基 $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n的坐标w为(k₁，k₂，...k_n)和(l₁，l₂，...l_n),经过 $\sigma$ 变换后,求变换后的内积为( $\sigma$ ( $\alpha$ ), $\sigma$ ( $\beta$ ))
$(\sigma(\alpha),\sigma(\alpha))=(A(k_1,k_2,...k_n)^T,A(l_1,l_2,...l_n)^T)= ((\gamma_1,\gamma_2,...\gamma_n)(k_1,k_2,...k_n)^T,(\gamma_1,\gamma_2,...\gamma_n)(l_1,l_2,...l_n)^T)=(k_1\gamma_1+k_2\gamma_2+...+k_n\gamma_n,l_1\gamma_1+l_2\gamma_2+...+l_n\gamma_n) =k_1l_1+k_2l_2+k_3l_3+...+k_nl_n=(\alpha,\beta)$
其中( $\gamma_1$ , $\gamma_2$ ,... $\gamma_n$ )是A的列向量组成的向量组.

所以可以得到,正交变换不但可以保证加法和数乘运算,还可以保证内积不变.

正交变换保证两个向量的内积不变,等价于,正交变化队医一个向量而言不改变其长度和不改变其和其他向量的夹角.

正交矩阵的行列式只能为1或者-1,所以对应的正交变换也有两种.当正交矩阵的行列式为1时,对应的正交变换为旋转变换,当正交矩阵的行列式为-1时,对应的正交变换为瑕旋转变换(旋转后再反射的线性变换).

另外,对于n维空间中的两组标准正交基: $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n与 $\gamma$ ₁， $\gamma$ ₂，... $\gamma$ _n,设其过度矩阵为P.则:
( $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n)=( $\gamma$ ₁， $\gamma$ ₂，... $\gamma$ _n)P,此时P是正交矩阵.

证明:由于( $\varepsilon$ ₁， $\varepsilon$ ₂，... $\varepsilon$ _n)=( $\gamma$ ₁， $\gamma$ ₂，... $\gamma$ _n)P
所以有 $\varepsilon$ _k=p_1k $\gamma$ ₁+p_2k $\gamma$ ₂+p_3k $\gamma$ ₃+...+p_nk $\gamma$ _n

其中p_ij为P的第i行第j列的元素.

所以
( $\varepsilon$ _i, $\varepsilon$ _j)=(p_1i $\gamma$ ₁+p_2i $\gamma$ ₂+p_3i $\gamma$ ₃+...+p_ni $\gamma$ _n ,p_1j $\gamma$ ₁+p_2j $\gamma$ ₂+p_3j $\gamma$ ₃+...+p_nj $\gamma$ _n) =p_1ip_1j+p_2ip_2j+p_3ip_3j+p_nip_nj=( $\eta$ _i, $\eta$ _j)

其中 $\eta$ _i为矩阵P的第i列组成的向量, $\eta$ _j为矩阵P的第j列组成的向量,而( $\varepsilon$ _i, $\varepsilon$ _j)当i=j时为1,i $\neq$ j时为0.
所以( $\eta$ _i, $\eta$ _j))当i=j时为1,i $\neq$ j时为0.
所以P是一个正交矩阵.

向量的正交化

对于一组线性无关的向量,其会构成一个线性空间V.在研究空间V时,标准正交基可以将此空间的问题大大简化,所以找到V的一组标准正交基,就成了研究空间V的关键问题.

此时估计有很多人会有一个疑问，为什么非要找标准正交基，自然基不就是一个标准正交基吗？为什么不用自然基

对于这一问题，一开始也困扰我，可以举个列子，来解释为什么不用自然基。

对于AX=0的解空间研究，设其解空间为k维，向量 $\chi$ ₁， $\chi$ ₂，... $\chi$ _k为k个线性无关的解向量。则 $\chi$ ₁， $\chi$ ₂，... $\chi$ _k为解空间的一组基。求这个解空间的标准正交基时，若直接用自然基，（1,0,0,...0）,（0,1,0,...0）,...（0,0,0,...1,...0）k个向量(注意这个地方是k个n维向量，因为解向量一定是n维向量)。显然这些向量不能被 $\chi$ ₁， $\chi$ ₂，... $\chi$ _k线性表示，所以不是AX=0的解，所有这个自然基并不在这个解空间中。所以不能用自然基。此时找的标准正交基必然可以被 $\chi$ ₁， $\chi$ ₂，... $\chi$ _k线性表示。这样才能确保找到的标准正交基是解空间的一组基。

这样就引出了施密特正交化算法（Schmidt orthogonalization），其具体算法如下：

设 $\alpha$ ₁, $\alpha$ ₂, $\alpha$ ₃,... $\alpha$ _n,是n维线性空间的一组基。
由这组基找到标准正交基的算法如下：
$\beta_1=\alpha_1 \\ \beta_2=\alpha_2-{(\alpha_2,\beta_1)\over (|\beta_1||\beta_1|)}\beta_1\\ \beta_3=\alpha_3-{(\alpha_3,\beta_2)\over (|\beta_2||\beta_2|)}\beta_2-{(\alpha_3,\beta_1)\over (|\beta_1||\beta_1|)}\beta_1\\ \cdots\\ \cdots\\ \beta_n=\alpha_n-{(\alpha_n,\beta_{n-1})\over (|\beta_{n-1}||\beta_{n-1}|)}\beta_{n-1}-\cdots{(\alpha_n,\beta_1)\over (|\beta_1||\beta_1|)}\beta_1\\$

由于 $\beta_1$ , $\beta_2$ ,... $\beta_n$ 的模不是1，故再将其除以各自的模长，得到 $\epsilon_1$ , $\epsilon_2$ ,... $\epsilon_n$ .这就是有原来的基生成的一组标准正交基。

其算法的几何图形如下：

斯密特正交化.png

矩阵的正交分解

由上面线性无关向量组的正交化可以看出，设Q=（ $\beta_1$ , $\beta_2$ ,... $\beta_n$ ）时，
$Q=(\alpha_1,\alpha_2,\alpha_3,...\alpha_n) \left[ \begin{array} {cccc} 1&-{(\alpha_2,\alpha_1)\over (|\alpha_1||\alpha_1|)}&\cdots&\cdots&*\\ 0&1&*&\cdots&*\\ \cdots&\cdots&\cdots&\cdots&*\\ 0&\cdots&\cdots&\cdots&1 \end{array} \right]$

设A=( $\alpha_1,\alpha_2,\alpha_3,...\alpha_n$ )

则有A=QR，其中R是上面公式中单位上三角矩阵的逆。单位上三角矩阵的逆还是单位上三角矩阵。所以由

$A=QR=Q\left[ \begin{array} {cccc} 1/|\beta_1|&0&\cdots&\cdots&0\\ 0&1/|\beta_2|&0&\cdots&0\\ \cdots&\cdots&\cdots&\cdots&0\\ 0&\cdots&\cdots&\cdots&1/|\beta_n| \end{array} \right] \left[ \begin{array} {cccc} |\beta_1|&0&\cdots&\cdots&0\\ 0&|\beta_2|&0&\cdots&0\\ \cdots&\cdots&\cdots&\cdots&0\\ 0&\cdots&\cdots&\cdots&1/|\beta_n| \end{array} \right]R=Q_1R_1$

其中， $Q_1$ 是正交矩阵， $R_1$ 是上三角矩阵。这就是矩阵的QR分解（正交分解）。其定理叙述如下：

定理7

设A是n阶非奇异矩阵，则存在正交矩阵Q和非奇异的上三角矩阵R，使得：
$A=QR$
且除去相差一个对角元绝对值等于1的对角矩阵因子分解外，分解式是唯一的。

上面的算法以给出可分解性，下面只需要证明唯一性即可。

反证法：假设A有以下两种不同的分解。A= $Q_1R_1$ 与A= $Q_2R_2$

那么有 $Q_1R_1$ = $Q_2R_2$ 。由于 $Q_1,R_1,Q_2,R_2$ 都是可逆的，所以有

$Q_2^{-1}Q_1 = R_2R_1^{-1}$

$Q_2^{-1},Q_1$ 连个都是正交矩阵，所以 $Q_2^{-1}Q_1$ 的转置等于 $Q_2^{-1}Q_1$ 的逆，所以 $Q_2^{-1}Q_1$ 也是正交矩阵。

所以 $R_2R_1^{-1}$ 是正交矩阵， $R_2R_1^{-1}$ 的逆等于其转置，而 $R_2R_1^{-1}$ 是上三角矩阵，上三角矩阵的逆是上三角矩阵，上三角矩阵的转置是下三角矩阵，如果一个上三角矩阵等于一个下三角矩阵，必然都是对角矩阵，所以R_2R_1^{{-1}是对角矩阵，所以Q_2}{-1}Q_1也是对角矩阵，而Q_2^{{-1}Q_1是正交矩阵，所以列向量的模等于1，所以Q_2}{-1}Q_1必然是一个对角线上只有 1或者-1的对角矩阵。

设 $Q_2^{-1}Q_1=B$ ， $R_2R_1^{-1}=B$ ,其中B是一个对角线上只有1或者-1的矩阵。那么 $Q_1=Q_2B$ , $R_2=BR_1$

所以定理得证。

Householder矩阵与Householder变换(初等反射变换)

定义：设 $\omega$ 是n维单位列向量，E为n阶单位矩阵，则

$H(\omega)=E-2\omega\omega^T$

称为Householder矩阵，或称作初等Householder矩阵。

与Householder矩阵对应的变换为Householder变换，既
$\sigma(\alpha)=H\alpha=(E-2\omega\omega^T)\alpha$

以下H代表Householder变换，主要研究Householder变换的性质，因为Householder矩阵的性质全部在Householder变换中

对于Householder变换，有一个强大的功能，既：Householder变换可将任意n维非零向量x，变换成任意n维相等模长的非零向量y.表述成定理如下

定理8

对于给定的任意两个n维非零向量想x、y，且 $||x||_2=||y||_2$

都纯在一个Householder变换H，使得y=Hx.

证明：（构造性证明）如下图所示，对任意给定的向量x,y。构造
$\omega={x-y \over|x-y|}$

则有
$H=E-2{x-y \over|x-y|}({x-y \over|x-y|})^T$

则有
$Hx=Ex-2{x-y \over|x-y|}({x-y \over|x-y|})^Tx$

则有
$Hx=x-2{x-y \over|x-y|}({x-y \over|x-y|})^Tx=x-2{(x-y)(x^T-y^T)x\over|x-y|^2} =x-{(x-y)(2x^Tx-2y^Tx)\over|x-y|^2}\\ =x-{(x-y)(x^Tx-y^Tx-x^Ty+y^Ty)\over|x-y|^2} =x-(x-y){ |x-y|^2\over|x-y|^2} =y$

所以定理得证。由下图可知，向量x,y是关于一个面对称。这个面的法向量就是 $\omega$

所以，HouseHolder变换是正交变化，且HouseHolder矩阵的行列式为-1.

由定理得知，对于任意单位向量 $\alpha$ ，都可经过Householder变换把 $\alpha=(x_1,x_2,...x_n)$ 变成 $e_1=(1,0,0...0)$

HouseHolder变换的性质

1、HouseHloder变换是对称变换。既： $H=H^T$
2、HouseHloder变换是正交变换。既： $H=H^{-1}$
3、HouseHolder变换是对合变化。既： $H^2=1$
4、HouseHolder变换的特征值为1,1,1,1,1...1,-1

Householder变换.png

定理9

设A是mXn(其中n<m)实数矩阵，且其n个列向量下行无关，则存在m阶正交矩阵Q，与n阶非奇异上三角矩阵R。有
$A=Q\left[ \begin{array} {cccc} R\\ 0\\ \end{array} \right]$

证明：定理的证明用HouseHolder变换。

因为A的所有列线性无关，设 $A＝［\alpha_1,\alpha_2,\alpha_3...\alpha_n］$

由上面关于Householder变换的定理可知，存在一个Householder矩阵H₁,使得
$H_1\alpha_1=(|\alpha_1|,0,0,...,0)$

所以H₁A第一列除了第一个元素外其余全为零。

设 $H_1A=[\beta_1,\beta_2,\beta_3,...,\beta_n]$

其中 $\beta_1$ 除第一个元素非零外，其余全为零。

对于第二个列向量 $\beta_2$ ，也存在一个Householder矩阵 $H_2$ ,有
$H_2\beta_2=(p_1,p_2,0,...,0)$

也就是说对任意的列向量，都存在一个householder矩阵，使尾部变成零。但是需要证明的一点是，后面的householder矩阵不改变前面已经变换的列向量。

所以，只要能找到不改变前面列零和非零的householder矩阵即可。

如果H是householder矩阵，那么
$\left[ \begin{array} {cccc} E&0\\ 0&H\\ \end{array} \right]$
也是householder矩阵。

由于 $H=E-2\omega\omega^T$

所以 $\left[ \begin{array} {cccc} E&0\\ 0&H\\ \end{array} \right]=E-2uu^T$

其中 $u=\left[ \begin{array} {cccc} 0\\ .\\ .\\ 0\\ \omega\\ \end{array} \right]$

所以 $\left[ \begin{array} {cccc} E&0\\ 0&H\\ \end{array} \right]$

也是个householder矩阵，（定理的最后，只能将矩阵A上三角化，而不能对角化，原因就在这个地方，这样构造出来的householder矩阵不能保证只有对角线上元素非零，只能保证对角线下方的元素为零。）
所以，可以找到一系列的houserholder矩阵 $H_1,H_2,...H_n$ ，使得
$H_n...H_2H_1A=\left[ \begin{array} {cccc} R\\ 0\\ \end{array} \right]$

设Q＝H_n...H_2H_1，所以Q是正交矩阵，而R是上三角矩阵，又因为A是列满秩，所以R也是满秩的，所以定理得到证明。

矩阵的特征分解(普分解)

正规矩阵

对于n阶实矩阵A,如果 $AA^T=A^TA$ 则称A是正规矩阵。

所以可以轻松得到，对称矩阵，正交矩阵，对角矩阵都是正规矩阵。

定理10(Schur定理)(矩阵的Schur三角分解)

对于任意n阶实矩阵A，都正交相似于一个上三角矩阵，既存在正交矩阵U，有 $U^TAU=U^{-1}AU=R$

其中R是一个上三角矩阵，且其R对角线上的元素为A的特征值。

证明：（使用数学归纳法证明）。

当n=1时，定理成立，假设当A的阶数为n-1也成立，当A的阶数为n时，

对于n阶实矩阵A，设A的一个特征向量为 $\xi_1$

对于 $\xi_1$ 存在householder矩阵 $H_1$ ,有 $H_1\xi_1=|\xi_1|e_1$
其中 $e_1$ 为A的一个单位特征向量。

则 $(H_1AH_1^T)H_1\xi_1=H_1(AH_1^TH_1\xi_1)=H_1(\lambda_1\xi_1)=\lambda_1H_1\xi_1=\lambda_1|\xi_1|e_1$
其中 $\lambda_1$

所以 $H_1AH_1^Te_1= e_1$

设 $A^{(1)}=H_1AH_1^T$

则 $A^{(1)}$ 必然有如下形式
$A^{(1)}＝\left[ \begin{array} {cccc} \lambda_1&\beta\\ 0&A_1\\ \end{array} \right]$

其中 $\lambda_1$ 为 $A_1$ 的特征值。而 $A_1$ 是n-1阶矩阵，由归纳法的假设得到 $A_1$ 有定理中的分解。而由特征值和特征向量的定义得到， $A_1$ 的特征值就是 $A^{(1)}$ 的特征值。所以当A为n阶矩阵时定理也成立。所以定理得证。

Schur定理告诉我们任意n阶实矩阵A都正交相似于一个上三角矩阵，且这个上三角矩阵对角线上的元素为原矩阵的特征值。既：
$UAU^T=R$

如果A是正规矩阵，则有以下结论：

定理11（对于以上的所有定理虽然都是在实数域讨论，但同样适用于复数域，所以未进行区分，而这个定理如果不区分实数和复数的话，就会被搞晕，所以一定要注意）

对于任意的n阶矩阵A,存在一个酉矩阵U，使得 $UAU^H=\Lambda$
其中 $\Lambda$ 为对角矩阵的充分必要条件是A为正规矩阵。

此定理中U为酉矩阵，不能修改为正交矩阵，因为正交矩阵也是正规矩阵，由定理得，一个正交矩阵正交相似与一个对角矩阵，所以这个正交矩阵是对称矩阵，并不是所有的正交矩阵都是对称矩阵，所以要想让正规矩阵对角化，必须在复数域上，酉相似对角化

证明：必要性证明

由条件知， $A=U^H\Lambda U$ 和 $A^H=U^H\Lambda^H U$

所以 $AA^H=U^H\Lambda UU^H\Lambda ^HU=A^HA$

所以必要性得到证明。

充分性证明

若A为正规矩阵，则 $A^HA=AA^H$ 。又因为Schur定理，对于n阶矩阵A，存在酉矩阵U使得
$U^HAU=R$
其中R为上三角矩阵。

所以 $A=URU^H$ 且 $A^H=UR^HU^H$

所以 $AA^H=URU^HUR^HU^H＝URR^HU^H$ 和 $A^HA=UR^HU^HURUH=UR^HRU^H$

所以 $R^HR=RR^H$

而R是一个上三角矩阵，所以 $R^H$ 是一个下三角矩阵，所以，设
$R=\left[ \begin{array} {cccc} r_{11}&r_{12}&\cdots&\cdots&r_{1n}\\ 0&r_{22}&r_{23}&\cdots &r_{2n}\\ \cdots&\cdots&\cdots\\ 0&\cdots&\cdots&\cdots&r_{nn}\\ \end{array} \right]$

所以：
$R^H=\left[ \begin{array} {cccc} \overline{r_{11}}&0&\cdots&\cdots&0\\ \overline{r_{12}}&\overline{r_{22}}&0&\cdots &0\\ \cdots&\cdots&\cdots\\ \overline{r_{1n}}&\cdots&\cdots&\cdots&\overline{r_{nn}}\\ \end{array} \right]$

由 $R^HR=RR^H$ 中对应元素相等，得到，R是一个对角矩阵，注意此时对角线上不一定是实数，所以定理得证。

定理12（特征分解定理）

对于n阶实对称矩阵A，存在一个酉矩阵U，使得 $U^HAU=\Lambda$
其中 $\Lambda＝diag(\lambda_1,\lambda_2,...\lambda_n)$ , $\lambda_i$ 为A的实特征值。

证明：因为实对称矩阵是正规矩阵，由上面的定理，可知必存在酉矩阵U，使得 $U^HAU=\Lambda$

只需证明， $\Lambda$ 是个实数矩阵，其对角线上为A的特征值。

对于上式等式两边同时取转置共轭，有 $U^HA^HU=\Lambda^H$

因为A是实对称矩阵，所以， $\Lambda=\Lambda^H$

所以 $\Lambda$ 为实对角矩阵。

又 $AU=U\Lambda$

设 $U=[u_1,u_2,...u_n]$ 则有 $A[u_1,u_2,...u_n]=[\lambda_1u_1,\lambda_2u_2,...\lambda_nu_n]$

所以可以看出，U的列向量为属于对应特征值的特征向量。所以定理得证。

所以对于任意n阶实对称矩阵A，有以下分解 $A=Q\Lambda Q^T$

称这个分解为特征分解或谱分解。因为Q的列向量为A的特征向量。 $\Lambda$ 对角线上的值为A 的特征值。

奇异值分解

矩阵的奇异值分解较上面几种分解是一种重要的分解。下面讨论的一些结论在复数域上，但在实数域上也成立。

什么是奇异值

对于任意复数域上的mxn矩阵A，存在非负实数 $\sigma$ ，非零向量 $\mu$ 与非零向量 $\nu$ ，有
$A\mu＝\sigma\nu ,A^H\nu＝\sigma\mu$

则称 $\sigma$ 为矩阵A的奇异值。 $\mu$ 称为矩阵A的属于 $\sigma$ 的右奇异向量， $\nu$ 称为矩阵A的属于 $\sigma$ 的左奇异向量，

在理解奇异值到底有什么用之前，先证明关于奇异值的几个结论。

1、 $A^HA与AA^H$ 有一样的非零特征值。

2、 $A^HA与AA^H$ 的特征值一定是非负实数。

3、 $rank(A)=rank(A^HA)=rank(AA^H)$

第一个结论的证明，用矩阵的特征方程可证， $A^HA与AA^H$ 的特征方程分别为 $｜\lambda E-A^HA｜＝0$ 与 $｜\lambda E-AA^H｜=0$ ，各自特征方程的解就是矩阵的特征值。

因为 $｜\lambda E-B_{mxn}A_{nxm}｜＝\lambda^{m-n}｜\lambda E-A_{nxm}B_{mxn}｜$

所以 $A^HA与AA^H$ 有一样的非零特征值。

第二个结论的证明，设 $\lambda$ 是矩阵 $A^HA$ 的特征值， $\mu$ 是对应的特征向量。所以有
$A^HA\mu=\lambda \mu$
因为 $\mu$ 是对应的特征向量，所以非零，上式两遍左乘一个 $\mu^H$ ,得到
$\mu^HA^HA\mu=\mu^H\lambda \mu$
所以
$(A\mu)^H(A\mu)=\lambda \mu^H\mu$

上式中等式右边必然是个非负实数， $\mu^H \mu$ 也必然是个非负实数，所以 $\lambda$ 必然为非负实数。

第三个结论的证明， $rank(A^HA)=rank(AA^H)$ 由第一个结论可以轻松证明，只要证明 $rank(A^HA)=rank(A)$
用方程解空间的维度证明。只要证明Ax=0的解空间和 $A^HAx=0$ 的解空间一样，即可说明 $rank(A^HA)=rank(A)$ ，若非零向量 $\xi$ 是Ax=0的解，那么 $\xi$
一定是 $A^HAx=0$ 的解。若非零向量 $\xi$ 是 $A^HAx=0$ 的解，则
$A^HA\xi=0$
$\xi^HA^HA\xi=0$
$(A\xi)^HA\xi=0$

所以 $A\xi=0$
所以 $\xi$ 是Ax=0的解，所以两者的解空间一样，所以 $rank(A^HA)=rank(A)$

如何求得奇异值

根据奇异值的概念，对于矩阵A，设 $\sigma$ 是其奇异值， $\mu$ 为右奇异向量， $\nu$ 为左奇异向量。那么有
$A\mu=\sigma \nu$ 和 $A^H\nu=\sigma \mu$

所以 $A^HA\mu=\sigma A^H\nu=\sigma （\sigma \mu）=\sigma ^2\mu$

所以若 $\sigma$ 是A的奇异值，等价于 $\sigma^2$ 是 $A^HA$ 的特征值，因为上面结论1， $A^HA$ 与 $AA^H$ 有一样的非零特征值，所以 $\sigma^2$ 也是 $AA^H$ 的特征值

所以若要求A的奇异值，只需求得 $A^HA$ 的特征值，因为上面结论2， $A^HA$ 的特征值非负，对 $A^HA$ 的特征值求正平方根，即为A的奇异值。需要注意的是A的奇异值的个数等于min{m,n}.

同时，我们还得到， $\mu$ 是与矩阵 $A^HA$ 对应的变换在 $\sigma^2$ 下的特征向量，同理， $\nu$ 是与矩阵 $AA^H$ 对应的变换在 $\sigma^2$ 下的特征向量

定理13

若一个矩阵是正规矩阵，则其奇异值等于特征值的模。

证明：对于正规矩阵有个非常优良的性质，就是可以酉相似对角化，既存在酉矩阵U，对于正规矩阵A，有
$A=U^Hdiag(\lambda_1,\lambda_2,...\lambda_n)U$

所以 $A^HA=U^Hdiag(\lambda_1^2,\lambda_2^2,...\lambda_n^2)U$

定理14 (奇异值分解定理)

对于任意mxn阶矩阵A，必定存在以下分解
$A=V\Sigma U^H$

其中U是mxm阶酉矩阵，V是nxn阶酉矩阵， $\Sigma$ 是mxn阶级对角矩阵可写为
$\Sigma=\left[ \begin{array} {cccc} \Sigma_1&0\\ 0&0\\ \end{array} \right]$

$\Sigma_1=diag(\sigma_1,\sigma_2,...\sigma_r)$ r为A的秩， $\sigma_i$ 为A的第i大的非零奇异值。

证明:

对于任意矩阵A，有 $A^HA$ 是埃尔米特矩阵，所以是正规矩阵，所以存在酉矩阵U，和对角矩阵 $\Lambda$ ,使得
$A^HA=U\Lambda U^H$
其中 $\Lambda$ 对角线上为 $A^HA$ 的特征值,U的列向量为对应的特征向量

所以 $A^HAU=U\Lambda$

两边同时左乘一个 $U^H$

有
$U^HA^HAU=U\Lambda$

所以
$(AU)^HAU=U^HU\Lambda =\Lambda=\left[ \begin{array} {cccc} \Lambda_r&0\\ 0&0\\ \end{array} \right]$
其中 $\Lambda_r=diag(\lambda_1,\lambda_2,...\lambda_n)$ r为A的秩， $\sigma_i$ 为A的第i大的非零特征值。

设 $V=[V_1,V_2],U=[U_1,U_2]$ 其中V_1,U_1的阶数为rank(A).

所以
$\left[ \begin{array} {cccc} \Lambda_r&0\\ 0&0\\ \end{array} \right]=\Lambda=\left[ \begin{array} {cccc} U_1^H\\ U_2^H\\ \end{array} \right]A^HA\left[ \begin{array} {cccc} U_1,U_2 \end{array} \right]=\left[ \begin{array} {cccc} U_1^HA^HAU_1&U_1^HA^HAU_2\\ U_2^HA^HAU_1&U_2^HA^HAU_2\\ \end{array} \right]$

所以 $U_1^HA^HAU_1=\Lambda_r, U_1^HA^HAU_2=0, U_2^HA^HAU_1=0, U_2^HA^HAU_2=0$

由于 $U_2^HA^HAU_2=0可得到，AU_2=0此公式记作(*).U_1^HA^HAU_1=\Lambda_r此公式记作（**）$

逆向证明，如果定理成立，有
$A=V \Sigma U^H$

必须有
$\Sigma=V^HA U$

设 $V=[V_1,V_2],U=[U_1,U_2]$

则必须有
$\Sigma=V^HA U$
$\Sigma=\left[ \begin{array} {cccc} V_1^H\\ V_2^H\\ \end{array} \right]A\left[ \begin{array} {cccc} U_1,U_2 \end{array} \right]$

则必须有
$\Sigma=V^HA U$
$\Sigma=\left[ \begin{array} {cccc} V_1^HAU_1&V_1^HAU_2\\ V_2^HAU_1&V_2^HAU_2\\ \end{array} \right]$

则必须有 $V_1^HAU_1=\Sigma_r$ , $V_1^HAU_2=0$ , $V_2^HAU_1=0$ , $V_2^HAU_2=0$ ,其中 $\Sigma_r=diag(\sigma_1,\sigma_2,...\sigma_r)$ r为A的秩， $\sigma_i$ 为A的第i大的非零奇异值。

取 $V_1=AU_1\Sigma_r^{-1}$ ,

则 $V_1^HV_1=(AU_1\Sigma_r^{-1})^H(AU_1\Sigma_r^{-1})=(\Sigma_r^{-1})^HU_1^HA^HAU_1\Sigma_r^{-1}= (\Sigma_r^{-1})^H\Lambda \Sigma_r^{-1}$ (由上面的（**）式得到)

因为 $\Lambda$ 是实数，所有 $V_1^HV_1$ =E

所以 $V_1$ 的所有列正交。所有 $V_1=AU_1\Sigma_r^{-1}$ 既是合理的也是能取到的。

而此时 $V_2^HAU_1=V_2^HV_1\Sigma_r$

此时在 $V_1$ 列向量形成的空间的正交补空间中取m-r个单位正交向量形成 $V_1$ .

那么 $V=[V_1,V_2]$ 必然是酉矩阵，且 $V_2^HV_1=0$

所以 $V_2^HAU_1=V_2^HV_1\Sigma_r=0$

由公式（*）得到 $V_2^HAU_2=0,V_1^HAU_2=0$

所有当U和V的取法为上面时，下面公式成立

$\Sigma= \left[ \begin{array} {cccc} \Sigma_r&0\\ 0&0\\ \end{array} \right]=\left[ \begin{array} {cccc} V_1^HAU_1&V_1^HAU_2\\ V_2^HAU_1&V_2^HAU_2\\ \end{array} \right]$

所以反推回去， $A=V \Sigma U^H$ 成立。

其中U，V为酉矩阵， $\Sigma=diag(\sigma_1,\sigma_2,...\sigma_r,0,0,0..0)$ r为A的秩， $\sigma_i$ 为A的第i大的非零奇异值。

所以奇异值分解定理得到证明

奇异值分解的几个结论

1、U的列向量是 $A^HA$ 的属于对应特征值的特征向量。
2、V的列向量是 $AA^H$ 的属于对应特征值的特征向量。
3、U的列向量是A的属于对应奇异值的右奇异向量。
4、V的列向量是A的属于对应奇异值的左奇异向量。

证明：第一条，由上面定理的证明过程可以看到，U是使得 $U^HA^HAU=\Lambda$ 的酉矩阵，所以U的列向量是 $A^HA$ 的属于对应特征值的特征向量。
对于第二条，因为 $A=V \Sigma U^H$

所以 $AV^H=\Sigma U^H$ ,所以 $VA^H=U \Sigma^H$
所以 $V^HAA^HV=(A^HV)^HA^HV= (U \Sigma^H)^H(U \Sigma^H)=\Sigma^2=\Lambda$

所以V的列向量是 $AA^H$ 的对应特征值的特征向量。

对于第三条和第4条，因为 $A=V \Sigma U^H$

所以有 $AU=V\Sigma$ 和 $A^HV=U\Sigma$

所以第三条和第四条成立

奇异值分解的性质

奇异值分解在机器学习中是极其重要的分解，因为它具有很多优良的性质，一定程度上揭示了矩阵的一些本质。下面我们就来讨论一下这些性质。矩阵的特征值更能反映矩阵的本质，但为什么不对特征值进行讨论，因为只有方阵才有特征值，且并不是所有的方阵都能进行特征分解。

为进行奇异值的性质分析，我们先做一下两点准备。

1、矩阵特征分解和奇异值分解的另一种表示方式

对于任意的埃尔米特矩阵，有特征分解 $A=U\Lambda U^H$ ,其中 $U=[u_1,u_2,u_3...u_n]$ ,为U矩阵， $\Lambda=diag(\lambda_1,\lambda_2,\lambda_3,...\lambda_n),其中\lambda_1>=\lambda_2>=\lambda_3>=...\lambda_n$

所以A可写为
$A =[u_1,u_2,...u_n]\Lambda \left[ \begin{array} {cccc} u_1^H\\ u_2^H\\ ...\\ u_n^H\\ \end{array} \right]=\lambda_1u_1u_1^H+\lambda_2u_2u_2^H+\lambda_3u_3u_3^H+...+\lambda_nu_nu_n^H$

对于任意的矩阵，并不是都有有特征分解，为了得到上式的表达式，我们进行奇异值分解，这也就是奇异值分解由来的原因，由奇异值分解定理，有 $A=V\Sigma U^H$ ,

$A =\sigma_1v_1u_1^H+\sigma_2v_2u_2^H+\sigma_3v_3u_3^H+...+\sigma_rv_ru_r^H$ 其中r为A 的秩。

2、向量的L2范数和矩阵的F-范数

一个向量（矩阵）的大小可以用向量（矩阵）的范数来表示，从而一个向量（矩阵）与另一个向量（矩阵）所含的信息量的差--既两个向量（矩阵）的距离，可以用这两个向量（矩阵）的差向量（矩阵）的范数表示.如果这个范数越大，说明这两个向量（矩阵）的差异越大，从而认定两个向量（矩阵）所含信息量差异越大。
在机器学习中和接下来讨论奇异值分解的性质时，最常用的是向量的L2范数，矩阵的F范数。下面对其详细介绍

定义：向量（矩阵）的范数是一个将向量（矩阵）映射到一个非负实数的函数，其满足一下三个性质：
（1）非负性，F(x)=0 <=> x=0
（2）齐次性，F(kx)=|k|F(x)
（3）三角不等式，F(x+y)<=F(x)+F(y)

其中x为向量（矩阵）。

·向量的L2范数

设 $x=(x_1,x_2,...x_n)$ ,则x的2范数如下表示

$||x||_2=\sqrt{\Sigma_{i=1}^nx_i^2}$

向量的L2范数用处非常广，在误差分析，正则化，最小二乘法中均有用到。有向量内积的定义得到，L2范数还有以下表示：
$||x||_2=\sqrt{\Sigma_{i=1}^nx_i^2}=(x,x)=x^Tx$

·矩阵的F范数

与向量的L2范数相对应，在矩阵中，F范数定义为下面形式：
$||X||_F=\sqrt{\Sigma_{i=1}^m\Sigma_{j=1}^nx_{i,j}^2}$

矩阵的F范数还有以下表示方式：
$||X||_F=\sqrt{tra(X^TX)}$

有上面范数的基础，即可讨论下面奇异值分解的性质:

1、奇异值的酉（正交）不变性。

对任意酉矩阵（正交矩阵）P，矩阵A的奇异值和PA的奇异值，AP的奇异值都是一样的。
证明：

对任意矩阵PA,由奇异值分解定理得到，存在酉矩阵U和V有以下分解(奇异值从大到小排列)。
$PA=V^H\Sigma U$

所以
$A=P^HV^H\Sigma U$

而两个酉矩阵想乘还是酉矩阵，所以奇异值的定义得到， $\Sigma$ 也是Ade奇异值形成的矩阵，所以性质得到证明。

这一性质说明了，镜面变换和旋转变换都不改变一个矩阵的奇异值。

2、比例不变性。

A的奇异值是 $\sigma$ ,则kA的奇异值为 $|k|\sigma$

3、矩阵降维

对于mxn阶矩阵A,当 $rank(A)<\frac{mn}{1+m+n}$ 时，在计算机存储时，会减小存储空间。

证明：对任意的mxn阶矩阵A，若不进行分解，需要存储mxn个数字，而当进行奇异值分解时，A可以分解成mxm阶矩阵U，mxn阶矩阵 $\Sigma$ ,nxn阶矩阵V

既
$A=[u_1,u_2,...u_m] \left[ \begin{array} {cccc} \Sigma_r&0\\ 0&0\\ \end{array} \right][v_1,v_2,...v_n]^H$

所以：
$A=[u_1,u_2,...u_r] \Sigma_r[v_1,v_2,...v_r]^H=U_1\Sigma_rV_1^H$

所以 $U_1$ 是mxr阶矩阵， $V_1$ 是rxn阶矩阵, $\Sigma_r$ 是r阶对角方阵。所以此时存储A需要存储(m+n+1)r个元素。所以当 $rank(A)<\frac{mn}{1+m+n}$ 时，在计算机存储时，会减小存储空间。

4、寻找秩为k的一个矩阵，作为A的最佳逼近。

对于给定的一个矩阵A,如果需要找到一个秩为k(k<rank(A))的矩阵，去逼近这个矩阵A.奇异值分解给出了方法。为什么要找到一个秩比原矩阵小的矩阵，去逼近原矩阵，因为，这是有实际意义的，在图像处理中，一张图像，可以看成是一个矩阵，寻找这个图像的特征（此特征非矩阵的特征值和特征向量，而是机器学习里面图像的特征，例如图像的颜色，形状之类的，虽然这些最终会体现在矩阵的特征里，但是还是要区分开，不要混淆。）时要去除噪音，去燥的过程就是找一个比原矩阵秩小的矩阵，使找到的这个矩阵是原矩阵的最佳逼近。这一过程也就是PCA的原理，PCA下面一节介绍，在这里只证明这个性质。

谈到逼近，必然要定义一个范数，因为只有在范数下逼近才有意义，在机器学习中，图像处理，音频处理，都使用矩阵的F范数，所以这里所说的最佳逼近是F范数下的最佳逼近。

定义：所谓F范数下的最佳逼近为满足下面表达式的矩阵C
$arg\,\min_{rank(C)=k}\{||A-C||_F \quad |C\in R^{mxn}_k\}$

定理15（矩阵的低秩逼近定理）

给定一个秩为r的矩阵A,则
$A=U \Sigma V^T$
欲求其最优k秩近似矩阵 $\widetilde{A}$ ,k⩽r, 该问题可形式化为

$\min \limits_{\widetilde{A} \in \mathbb{R}^{m \times n}}\| \textbf{A} - \widetilde{\textbf{A}}\|_F , s.t. \ rank(\widetilde{\textbf{A}}) = k .$

对矩阵A进行奇异值分解后，将矩阵 $\Sigma$ 中的 r − k 个最小的奇异值置零获得矩阵 $\Sigma_k$ , 仅保留最大的k个奇异值, 则

$A_k=U_k \Sigma_k V^T_k$

就是上面最优化问题的的最优解，其中Uk和Vk分别是式U和V中前k列组成的矩阵. （Eckart-Young-Mirsky定理）

所以由这个定理我们就得到了矩阵的低秩逼近矩阵，这个应用在图像压缩中用处非常大，稍后介绍。这个定理的证明在此就不给出了，感兴趣的话，详见论文

Eckart-Young-Mirsky矩阵逼近定理。

在矩阵的低秩最佳逼近中，对于mxn阶秩为r的矩阵A，有
$||A||_F^2=\sigma_1^2+\sigma_2^2+...\sigma_r^2$

其中 $\sigma_1>\sigma_2>...\sigma_r$

而秩为k的最佳逼近矩阵
$||\widetilde{A}||_F^2=\sigma_1^2+\sigma_2^2+...\sigma_k^2$

所以矩阵A到矩阵 $\widetilde{A}$ 丢失的信息量比例为
$\frac{\sigma_{k+1}^2+\sigma_{k+2}^2+...\sigma_r^2}{\sigma_1^2+\sigma_2^2+...\sigma_r^2}$

网上很多奇异值分解降维应用的原理都是用这个公式推导矩阵低秩逼近定理，但是我认为这个并不能证明，在数学上不能严格证明矩阵的低秩逼近定理，要想严格的证明矩阵的低秩逼近定理必须参考Eckart-Young-Mirsky论文给出的方法。也就是说理解SVD在降维中的理论，必须用论文Eckart-Young-Mirsky矩阵逼近定理证明，网上给出的证明都是从结论出发，用结论验证结论。

奇异值分解的应用

1、在图像压缩中的应用

由前文奇异值分解的第3、4个性质，我可以对一张图片进行压缩，一张图片可以看成是一个矩阵，对这个矩阵进行奇异值分解，取秩为k的矩阵进行逼近，这个秩序为k的矩阵就是原图像压缩后的图像。

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
def rebuild_img(u, sigma, v, p): #p表示奇异值的百分比
    m = len(u)
    n = len(v)
    a = np.zeros((m, n))
    
    count = (int)(sum(sigma))
    curSum = 0
    k = 0
    while curSum <= count * p:
        uk = u[:, k].reshape(m, 1)
        vk = v[k].reshape(1, n)
        a += sigma[k] * np.dot(uk, vk)
        curSum += sigma[k]
        k += 1
    a[a < 0] = 0
    a[a > 255] = 255
    #按照最近距离取整数，并设置参数类型为uint8
    return np.rint(a).astype("uint8")
    
if __name__ == '__main__':
    img = Image.open('Hydrangeas.jpg', 'r')
    a = np.array(img)
    plt.figure(figsize = (16, 8))
    i=0
    for p in np.arange(0.1, 1, 0.2):
       
        u, sigma, v = np.linalg.svd(a[:, :, 0])
        R = rebuild_img(u, sigma, v, p)
        
        u, sigma, v = np.linalg.svd(a[:, :, 1])
        G = rebuild_img(u, sigma, v, p)
        
        u, sigma, v = np.linalg.svd(a[:, :, 2])
        B = rebuild_img(u, sigma, v, p)
        
        I = np.stack((R, G, B), 2)
        plt.subplot(2, 3, i+1), plt.imshow(I), plt.axis('off'), plt.title("p =" + str(np.around(p*100, decimals=1))+"%")
        i=i+1
        #保存图片在img文件夹下
        #Image.fromarray(I).save("svd_" + str(p * 100) + ".jpg")

output_349_0.png

上面程序给出，当奇异值舍弃的顺序由小到大，保留的奇异值的个数越多，图片被压缩的比例越小，图像越清晰。上面的例子可以看出保留的奇异值比例在50%的时候还能辨别是一个花。这就是奇异值分解在图像压缩中的应用。

2、在图像恢复中的应用

在图像恢复中的应用，主要是缺失矩阵（稀疏矩阵）的数据补全。下面举的例子是基于协同过滤算法去实现的。协同过滤算法的讲解详见“奇异值分解在协同过滤推荐算法中的应用”。

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

'''以下是三种计算相似度的算法，分别是欧式距离、皮尔逊相关系数和余弦相似度,
注意三种计算方式的参数inA和inB都是列向量'''
#这段代码在机器学习实战书中P259
#（注意传入的inA,inB都是列向量，行向量会报错）

def ecludSim(inA, inB):
    return 1.0 / (1.0 + la.norm(inA - inB))  # 范数的计算方法linalg.norm()，这里的1/(1+距离)表示将相似度的范围放在0与1之间


def pearsSim(inA, inB):
    if len(inA) < 3: return 1.0
    return 0.5 + 0.5 * corrcoef(inA, inB, rowvar=0)[0][
        1]  # 皮尔逊相关系数的计算方法corrcoef()，参数rowvar=0表示对列求相似度，这里的0.5+0.5*corrcoef()是为了将范围归一化放到0和1之间


def cosSim(inA, inB):
    num = float(inA.T * inB)
    denom = np.linalg.norm(inA) * np.linalg.norm(inB)
    return 0.5 + 0.5 * (num / denom)  # 将相似度归一到0与1之间


def rebuild_img(u, sigma, v, p): #p表示奇异值的百分比
    m = len(u)
    n = len(v)
    a = np.zeros((m, n))
    
    count = (int)(sum(sigma))
    curSum = 0
    k = 0
    while curSum <= count * p:
        uk = u[:, k].reshape(m, 1)
        vk = v[k].reshape(1, n)
        a += sigma[k] * np.dot(uk, vk)
        curSum += sigma[k]
        k += 1
    a[a < 0] = 0
    a[a > 255] = 255
    #按照最近距离取整数，并设置参数类型为uint8
    return np.rint(a).astype("uint8")
def loadExData():
    # 利用SVD提高推荐效果，菜肴矩阵
    """
    行：用户
    列：电影
    值：用户对电影的评级，0表示未评分
    """
    return mat([[1, 0, 7],
           [9, 6, 4],
           [5, 7, 0],
           [0, 7, 1]])

# 基于物品相似度的推荐引擎
def standEst(dataMat, user, simMeas, item):
    """standEst(计算某用户未评分电影中，以对该电影和其他物品评分的电影的物品相似度，然后进行综合评分)

    Args:
        dataMat         训练数据集
        user            用户编号
        simMeas         相似度计算方法
        item            未评分的物品编号
    Returns:
        ratSimTotal/simTotal     评分（0～10之间的值）
    """
    # 得到数据集中的物品数目
    n = np.shape(dataMat)[1]
    # 初始化两个评分值
    simTotal = 0.0
    ratSimTotal = 0.0
    # 遍历行中的每个物品（对用户评过分的物品进行遍历，并将它与其他物品进行比较）
    for j in range(n):
        userRating = dataMat[user, j]
        # 如果某个物品的评分值为0，则跳过这个物品
        if userRating == 0:
            continue
        # 寻找两个用户都评级的物品
        # 变量 overLap 给出的是两个物品当中已经被评分的那个元素的索引ID
        # logical_and 计算x1和x2元素的真值。
        overLap = np.nonzero(np.logical_and(dataMat[:, item].A < 255, dataMat[:, j].A < 255))[0]
        # 如果相似度为0，则两着没有任何重合元素，终止本次循环
        if len(overLap) == 0:
            similarity = 0
        # 如果存在重合的物品，则基于这些重合物重新计算相似度。
        else:
            similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])
        # print 'the %d and %d similarity is : %f'(iten,j,similarity)
        # 相似度会不断累加，每次计算时还考虑相似度和当前用户评分的乘积
        # similarity  用户相似度，   userRating 用户评分
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    # 通过除以所有的评分总和，对上述相似度评分的乘积进行归一化，使得最后评分在0~5之间，这些评分用来对预测值进行排序
    else:
        return ratSimTotal/simTotal
# recommend()函数，就是推荐引擎，它默认调用standEst()函数，产生了最高的N个推荐结果。
# 如果不指定N的大小，则默认值为3。该函数另外的参数还包括相似度计算方法和估计方法
def recommend(dataMat, simMeas=cosSim, estMethod=standEst):
    retMat=dataMat.copy()
    n=np.shape(dataMat)[0]
    
    for user in range(0,n):
        # 寻找未评级的物品
        # 对给定的用户建立一个未评分的物品列表
        unratedItems = np.nonzero(dataMat[user, :].A == 255)[1]
        # 如果不存在未评分物品，那么就退出函数
        if len(unratedItems) == 0:
            continue
        # 在未评分物品上进行循环
        for item in unratedItems:
            estimatedScore = estMethod(dataMat, user, simMeas, item)
            retMat[user,item]=estimatedScore
            # 按照估计得分，对该列表进行排序并返回。列表逆排序，第一个值就是最大值
    return retMat  
if __name__ == '__main__':
    img = Image.open('old_1.jpg', 'r')
    
    a = np.array(img)
    p=0.99
    plt.figure(figsize = (16, 8))
    u, sigma, v = np.linalg.svd(a[:, :, 0])
    R = rebuild_img(u, sigma, v, p)
        
    u, sigma, v = np.linalg.svd(a[:, :, 1])
    G = rebuild_img(u, sigma, v, p)
        
    u, sigma, v = np.linalg.svd(a[:, :, 2])
    B = rebuild_img(u, sigma, v, p)
        
    I = np.stack((R, G, B), 2)

    plt.subplot(2, 3, 1), plt.imshow(I), plt.axis('off'), plt.title("p =" + str(np.around(p*100, decimals=1))+"%")
    
    
    R_new=recommend(np.mat(R))
    G_new=recommend(np.mat(G))
    B_new=recommend(np.mat(B))
    I_new = np.stack((np.array(R_new), np.array(G_new), np.array(B_new)), 2)
    plt.subplot(2, 3, 2), plt.imshow(I_new), plt.axis('off'), plt.title("p =" + str(np.around(p*100, decimals=1))+"%")

3、在特征脸方面的应用

4、在谱聚类中的应用

5、从视频中删除背景

6、在推荐算法中的应用

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,496评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,407评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,632评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,180评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,198评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,165评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,052评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,910评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,324评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,542评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,711评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,424评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,017评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,668评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,823评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,722评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,611评论 2赞 353

Deep Learning——矩阵分解

目录

矩阵分解简介

矩阵分解用到的基础知识

一、线性映射、线性变换、以及他们与矩阵的关系

定理1 ：

定理2 ：

二、矩阵的等价

三、矩阵的相似

四、初等矩阵和初等变换

五、置换矩阵

引理1

主子式和顺序主子式

矩阵的满秩分解

定理3

矩阵的LU分解

定理4

定理5

矩阵LU分解求解

方法—、

方法二（Doolittle算法）、

矩阵得LDU分解

定理6

注意

矩阵的正交分解

正交矩阵

正交矩阵的性质

向量的正交化

矩阵的正交分解

定理7

Householder矩阵与Householder变换(初等反射变换)

定理8

HouseHolder变换的性质

定理9

矩阵的特征分解(普分解)

正规矩阵

定理10(Schur定理)(矩阵的Schur三角分解)

定理11（<font color="#660000">对于以上的所有定理虽然都是在实数域讨论，但同样适用于复数域，所以未进行区分，而这个定理如果不区分实数和复数的话，就会被搞晕，所以一定要注意</font>）

定理12（特征分解定理）

奇异值分解

什么是奇异值

如何求得奇异值

定理13

定理14 (奇异值分解定理)

奇异值分解的几个结论

奇异值分解的性质

1、矩阵特征分解和奇异值分解的另一种表示方式

2、向量的L2范数和矩阵的F-范数

1、奇异值的酉（正交）不变性。

2、比例不变性。

3、矩阵降维

4、寻找秩为k的一个矩阵，作为A的最佳逼近。

定理15（矩阵的低秩逼近定理）

奇异值分解的应用

1、在图像压缩中的应用

2、在图像恢复中的应用

3、在特征脸方面的应用

4、在谱聚类中的应用

5、从视频中删除背景

6、在推荐算法中的应用

推荐阅读更多精彩内容