《多元统计分析》课程教学资源（课件讲稿）第十五讲 奇异值分解

第十五讲奇异值分解X = UDVTVT00XrxrnXrrxpnxpU:列基V:行基D:权/奇异值

第十五讲 奇异值分解 权 奇异值 行基 列基 /: : : D V U 𝑋 = 𝑈𝐷𝑉 ⊤ 𝑋 𝑛 × 𝑝 𝑈 𝑛 × 𝑟 𝑉 ⊤ 𝑟 × 𝑝 = 𝐷 𝑟 × 𝑟

奇异值分解（SVD)对任一n×p矩阵X，其列向量张成的空间（简称列空间）记作列空间C(X) = (Xt: t E RP)引理1.(1) C(X) = C(XXT), C(XT) = C(XTx).(2）XTX与XXT有相同的非O特征根，特征向量相互关联：若a是XTX的特征向量，则b=Xa是XXT的特征向量；若b是XXT的特征向量，则a=XTb是XTX的特征向量。证: (1) C(XXT) = (XXTt: tE RP) = (Xs: S = XTt E RP) c C(X)若xE C(XXT),XXTx= 0 =xTXXTx= 0= XTx= 0= XEC(X)I= C(XXT)+ C(X)+, C(X) C(XXT).(2).XTb = XTXa = aa = XXT(Xa) = (Xa)a注：XXT的特征向量刻画矩阵C(XXT）=C(X);XTX的特征向量刻画矩阵C(XTX)=C(XT）

2 引理1. (1) 𝐶 𝑋 = 𝐶 𝑋𝑋⊤ , 𝐶 𝑋 ⊤ = 𝐶 𝑋 ⊤𝑋 . 奇异值分解(SVD) 对任一𝑛 × 𝑝矩阵𝑋, 其列向量张成的空间（简称列空间）记作 𝐶 𝑋 = 𝑋𝐭: 𝐭 ∈ 𝑅 𝑝 证: 1 𝐶 𝑋𝑋⊤ = 𝑋𝑋⊤𝐭: 𝐭 ∈ 𝑅 𝑝 = 𝑋𝐬: 𝐬 = 𝑋 ⊤𝐭 ∈ 𝑅 𝑝 ⊂ 𝐶 𝑋 若𝐱 ∈ 𝐶 𝑋𝑋⊤ ⊥, 𝑋𝑋⊤𝐱 = 0 ⇒ 𝐱 ⊤𝑋𝑋⊤𝐱 = 0 ⇒ 𝑋 ⊤𝐱 = 0 ⇒ 𝐱 ∈ 𝐶 𝑋 ⊥ ⇒ 𝐶 𝑋𝑋⊤ ⊥ ⊂ 𝐶 𝑋 ⊥ , 𝐶 𝑋 ⊂ 𝐶 𝑋𝑋⊤ . 2 . 𝑋 ⊤𝐛 = 𝑋 ⊤𝑋𝐚 = 𝐚𝜆 ⇒ 𝑋𝑋⊤ 𝑋𝐚 = 𝑋𝐚 𝜆. 注： 𝑋𝑋⊤的特征向量刻画矩阵𝐶(𝑋𝑋⊤) = 𝐶(𝑋) ; 𝑋 ⊤𝑋的特征向量刻画矩阵𝐶(𝑋 ⊤𝑋) = 𝐶(𝑋 ⊤) . 列空间 2 𝑋 ⊤𝑋与𝑋𝑋⊤有相同的非0特征根，特征向量相互关联：若𝐚是 𝑋 ⊤𝑋的特征向量，则𝐛 = 𝑋𝐚是𝑋𝑋⊤的特征向量；若𝐛是𝑋𝑋⊤的特 征向量，则𝐚 = 𝑋 ⊤𝐛 是𝑋 ⊤𝑋的特征向量

定理1(奇异值分解，SVD).任一秩为r的n×p矩阵X可表示为奇异值分解X=UDrTxp =Jau,vt +..+/a,u,v,其中uTU=vTV=I,D=diag(/a….a,)的对角元称为奇异值,其中≥.≥,>0为xTx或XXT的r个正特征根，U=(u,u),V=(V1.,V,)的各列分别是XXT，XTx的特征向量。X=UDVTSVD:a,uivt +... +vauy.X=VTVTUD:X一VTDnxrrxrVTrxp/AnxpXUnxpU:列基V:行基D：权/奇异值ui..ur3

3 的各列分别是 ， 的特征向量。 其中 为 或 的 个正特征根， 其中 的对角元称为奇异值 定理 奇异值分解， 任一秩为 的 矩阵 可表示为 V XX X X X X XX r U U U V V I D X U D V r n p X r r r r r n r r r r p r r r T T T T T T T T T ( ,., ) . 0 ( ,., ), , diag( ,., ) , . 1( SVD). 1 1 1 1 1 1 1 v v u u u v u v                       权 奇异值 行基 列基 /: : : D V U SVD: 𝑋 = 𝑈𝐷𝑉 ⊤ 𝑋 𝑛 × 𝑝 𝑈 𝑛 × 𝑟 𝑉 ⊤ 𝑟 × 𝑝 = 𝐮1 ⋯ 𝐮𝑟 𝝀𝟏 𝜆𝑟 ⋱ 𝐯1 ⊤ ⋮ 𝐯𝑟 ⊤ 𝑋 𝑛 × 𝑝 𝑋 = 𝜆1𝐮1𝐯1 ⊤ + ⋯ + 𝜆𝑟𝐮𝑟𝐯𝑟 ⊤ 奇异值 分解 𝐷 𝑈 𝑉 𝐷 ⊤ 𝑟 × 𝑟

证明：考虑xTx的非o特征根入i，特征向量vi：XTXv=v;ai,i=1,,r.其中D2=diag(a..),特征方程：XTXV=VD2V = (vi,., Vr)两边左乘XXXtXV = XVd2令Y=XVY的列向量是XXT的特征向量YTY = VTXTXV= D2XXty = Yd2= D-1yTYD-1 = Ir令U=YD-1U的列向量是XXT正交单位特征方程：XXTU=UD2化特征向量。UTU=IrY =XV = UD右乘VTX = udVt.XVVT =- UDVTXVVT=XC(V) = C(XTX) = C(XT)= VVT = PV = PxT = XVVT = XPxT = X4

4 证明：考虑𝑋 ⊤𝑋的非0特征根𝜆𝑖 , 特征向量𝐯𝑖 : 𝑋 ⊤𝑋𝐯𝑖 = 𝐯𝑖𝜆𝑖 , 𝑖 = 1, . , 𝑟. 𝑌的列向量是𝑋𝑋⊤的特征向量 𝑌 ⊤𝑌 = 𝑉 ⊤𝑋 ⊤𝑋𝑉 = 𝐷 2 ⇒ 𝐷 −1𝑌 ⊤𝑌𝐷 −1 = 𝐼𝑟 令 𝑌 = 𝑋𝑉 令𝑈 = 𝑌𝐷 −1 其中𝐷 2 = diag 𝜆1, . , 𝜆𝑟 ， 𝑉 = 𝐯1, . , 𝐯𝑟 𝑋𝑋⊤𝑋𝑉 = 𝑋𝑉𝐷 2 两边左乘𝑋 𝑋𝑉𝑉 ⊤ = 𝑈𝐷𝑉 ⊤ 右乘𝑉 ⊤ 特征方程：𝑋 ⊤𝑋𝑉 = 𝑉𝐷 2 𝐶 𝑉 = 𝐶 𝑋 ⊤𝑋 = 𝐶 𝑋 ⊤ ⇒ 𝑉𝑉 ⊤ = 𝑃𝑉 = 𝑃𝑋 ⊤ ⇒ 𝑋𝑉𝑉 ⊤ = 𝑋𝑃𝑋 ⊤ = 𝑋 𝑋 = 𝑈𝐷𝑉 ⊤. 𝑋𝑉𝑉 ⊤ = 𝑋 𝑋𝑋⊤𝑌 = 𝑌𝐷 2 特征方程：𝑋𝑋⊤𝑈 = 𝑈𝐷 2 𝑌 = 𝑋𝑉 = 𝑈𝐷 𝑈的列向量是𝑋𝑋⊤正交单位 化特征向量。𝑈 ⊤𝑈 = 𝐼𝑟

口若X已经中心化，则SVD台PCASVD评注XTX=（n一1)S，Y=XV=UD是所有非0奇异值对应的主成分。X= UDVT = /aiuivI +..+/arurvT.口正交展开：口V、U分别是X的行、列特征：XXTU=UD2，XTXV=VD2口对偶方程：XV=UD，XTU=VD对U,V的特定一列u,v(对应的特征根)：Xv=uVa,，XTu=VaXueC(X)VEC(X)T虽然X不是方阵，没有特征向量，但V，u)可看作是X及其伴随X的“特征向量”不变量n

5  若𝑋已经中心化, 则 SVD ⇔ PCA 𝑋 ⊤𝑋 = 𝑛 − 1 𝑆，𝑌 = 𝑋𝑉 = 𝑈𝐷 是所有非0奇异值对应的主成分。  正交展开： 𝑋 = 𝑈𝐷𝑉 ⊤ = 𝜆1𝐮1𝐯1 ⊤ + ⋯ + 𝜆𝑟𝐮𝑟𝐯𝑟 ⊤.  𝑉、𝑈分别是𝑋的行、列特征： 𝑋𝑋⊤𝑈 = 𝑈𝐷 2 ，𝑋 ⊤𝑋𝑉 = 𝑉𝐷 2  对偶方程： 𝑋𝑉 = 𝑈𝐷，𝑋 ⊤𝑈 = 𝑉𝐷 ( ) T vC X uC(X ) X T X 虽然𝑋不是方阵，没有特征向量，但{𝐯，𝐮}可 看作是𝑋及其伴随𝑋 ⊤的“特征向量”/不变量 对𝑈, 𝑉的特定一列𝐮, 𝐯 (对应的特征根𝜆): X 𝐯 = 𝐮 𝜆， 𝑋 ⊤𝐮 = 𝐯 𝜆 SVD评注

00010例1.9020C001X:XX00+0P00XXT的特征根：=9，=4，，=1。X的奇异值：3,2,1X=UDVT001(0100其中U=D=diag(3,2,1)000006

6 , 0 0 0 9 0 0 4 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 4 0 0 1 0 0 0 , 0 0 0 0 0 0 0 3 0 0 2 0 0 1 0 0                     X  XX X X T ， T 例1. XX 的特征根：1  9，2  4，3 1。X的奇异值: 3,2,1 T diag(3,2,1) 1 0 0 0 1 0 0 0 1 0 0 0 , 0 0 0 1 0 0 0 1 0 0 0 1                 U V D X UDV 其中 ， T T 1 v

XXT或XTX的最大特征根2,=9对应的特征向量.u,=(0,0,1,0)T：X的第3行最重要，（XXT)3,最大.V,=(0,00,1)：X的第4列最重要，（XTX)44最大如下图，u,vT定位矩阵X的最重要的位置：(3,4)u类似地，第二大特征值4对应的u2=(0,1,0,0)T,V2=(0,0,1,0)Tu2Vz定位矩阵A的（2,3）位置，u，定位矩阵A的（1,2)

7 : (3 4) (0,0,0,1) 4 , ( ) (0,0,1,0) 3 ( ) 9 1 1 1 44 1 33 1 如下图， 定位矩阵 的最重要的位置 ， ： 的第 列最重要 最大 ： 的第 行最重要， 最大 或 的最大特征根 对应的特征向量 X X X X X XX XX X X T T T T T T T u v v u       T 1 v T v1 u1 定位矩阵 的（ ，）位置， 定位矩阵 的（，） 类似地，第二大特征值 对应的 2 3 1 2 4 (0,1,0,0) , (0,0,1,0) , 2 2 3 3 2 2 A A T T T T u v u v u  v 

C0-000-1阶逼近：3u,vi000000002002阶逼近：3uvT+2uzv0030000001002:X3阶即为原数据：3uv,+2u,v+u,000500008

8        0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 3 1 1 T 阶逼近： u v         0 0 0 0 0 0 0 3 0 0 2 0 0 0 0 0 2 3 1 1 2 2 2 T T 阶逼近： u v u v  X          0 0 0 0 0 0 0 3 0 0 2 0 0 1 0 0 3 3 1 1 2 2 2 3 3 T T T 阶即为原数据： u v u v u v

矩阵分解和低秩逼近矩阵分解（matrixfactorization）将矩阵分解成两个或多个矩阵分解矩阵的乘积，在新的基下重新表示矩阵的行或列向量：X= CRT，C：列基，R：行基rank(X)≤knxpnxkkxpRTX二X矩阵分解有任意多种，我们可以构造如下：假设X=(x1,.,x),rank(X)≤k，假设c1,.,ck是c(X)的一组基（有穴余），C=（C1,,Ck），则存在t;ERk使得xi=Cti，X = (X1,..Xp) = (Ct,..,.Ctp) = C(t,..,tp) ≤ CRT其中RT=(t1,,tp)是k×p矩阵,R的列向量是X行空间的基。当k<rank(X）时，CRT是X的秩k逼近(lowrankapproximation）9

9 矩阵分解(matrix factorization)将矩阵分解成两个或多个 矩阵的乘积，在新的基下重新表示矩阵的行或列向量： 𝑋 = 𝐶 𝑅 ⊤ ， 𝐶：列基， 𝑅：行基 矩阵分解和低秩逼近  𝑛 × 𝑝 𝑛 × 𝑘 𝑘 × 𝑝 𝑋 𝐶 𝑅 ⊤ = 矩阵分解 矩阵分解有任意多种，我们可以构造如下： 假设𝑋 = 𝐱1, . , 𝐱𝑝 , 𝑟𝑎𝑛𝑘(𝑋) ≤ 𝑘, 假设𝐜1, . , 𝐜𝑘是𝐶(𝑋)的一组 基（有冗余），C = (𝐜1, . , 𝐜𝑘), 则存在𝐭𝑖 ∈ 𝑅 𝑘使得𝐱𝑖 = 𝐶𝐭𝑖, 𝑋 = 𝐱1, . , 𝐱𝑝 = 𝐶𝐭1, . , 𝐶𝐭𝑝 = 𝐶 𝐭1, . ,𝐭𝑝 ≜ 𝐶𝑅 ⊤ 其中𝑅 ⊤ = 𝐭1, . ,𝐭𝑝 是𝑘 × 𝑝矩阵,𝑅的列向量是𝑋行空间的基。 𝑟𝑎𝑛𝑘(𝑋) ≤ 𝑘 当 𝑘 < rank(𝑋) 时, 𝐶𝑅 ⊤是𝑋的秩𝑘逼近(low rank approximation)

由上页讨论知，矩阵分解X=CRT将X的列向量表示成C的列基X=CRT列向量的组合，同理，X的行向量表示为R的行向量的线性行基组合，因此我们称C的列为列空间的基（虽然它们可能有穴余），R的列为行空间的基。例1（PCA）假设Xnxp已中心化，样本协方差矩阵S=XTX/(n一1)的谱分解S=VAVT，主成分矩阵Y=XV，则有矩阵分解（主成分变换的反变换）：X =YVT注意到Y是列正交的，即YTY=VTXTXV=n－1)AD2,因此矩阵分解X三YVT的行基和列基都是正交基-这很难得，我们有理由相信该分解一定具有某些优良性质。令U=YD-1,则UTU=Ip, X = YVT = UDVT这正是中心化矩阵X的SVD,U或者Y=UD的列向量是列空间C(X)的正交基，V或者VD的列向量是行空间C（XT)的正交基。我们后面将看到SVD/PCA在LS意义上具有优良逼近性质。10

10 由上页讨论知，矩阵分解𝑋 = 𝐶 𝑅 ⊤将𝑋的列向量表示成𝐶的 列向量的组合，同理，𝑋的行向量表示为𝑅 ⊤的行向量的线性 组合，因此我们称𝐶的列为列空间的基（虽然它们可能有冗 余），𝑅的列为行空间的基。 列基 𝑋 = 𝐶 𝑅 ⊤ 行基 例1（PCA）假设𝑋𝑛×𝑝已中心化, 样本协方差矩阵 𝑆 = 𝑋 ⊤𝑋/(𝑛 − 1)的谱分解𝑆 = 𝑉Λ𝑉 ⊤ , 主成分矩阵𝑌 = 𝑋𝑉, 则有矩阵分解（主 成分变换的反变换）： 𝑋 = 𝑌𝑉 ⊤ 注意到𝑌是列正交的，即 𝑌 ⊤𝑌 = 𝑉 ⊤ 𝑋 ⊤𝑋𝑉 = 𝑛 − 1 Λ ≜ 𝐷 2 , 因 此矩阵分解𝑋 = 𝑌𝑉 ⊤的行基和列基都是正交基 – 这很难得，我 们有理由相信该分解一定具有某些优良性质。 令𝑈 = 𝑌𝐷 −1 , 则 𝑈 ⊤𝑈 = 𝐼𝑝, ⇒ 𝑋 = 𝑌𝑉 ⊤ = 𝑈𝐷𝑉 ⊤, 这正是中心化矩阵𝑋的SVD, 𝑈或者𝑌 = 𝑈𝐷的列向量是列空间𝐶(𝑋) 的正交基，𝑉或者𝑉𝐷的列向量是行空间𝐶( 𝑋 ⊤)的正交基。 我们后面将看到SVD/PCA在LS意义上具有优良逼近性质