第十六讲典则相关分析CCACCA动机: cov(uTx, vTy) = uTZxyv = max!ccaCCA结果: cov(x,y) = Zxy = cov(, n) =diagonal
第十六讲 典则相关分析CCA 1 CCA动机: cov( 𝐮 ⊤𝐱, 𝐯 ⊤𝐲) = 𝐮 ⊤ Σ𝐱𝐲𝐯 = max! CCA结果: cov 𝐱, 𝐲 = Σ𝐱𝐲 cca cov 𝛏, 𝛈 =diagonal
Recap奇异值分解(SVD，Singularvaluedecomposition）SVD定理l：任何秩为r的n×p矩阵X有奇异值分解X=UDVT,其中D=diag(…a,)，≥...≥,>0为Tx或xTx的非o特征根UTU=I,TV=I,其中Uxr=(u..u,),Vxr=(vi..v,）的列向量分别是XTX或XIX非O特征根对应的正交单位特征向量。有时，将U，V扩张成正交矩阵应用起来更方便：奇异值分解Xxn=UxDVT中，若将U,V补全为正交方阵U,V,D补UV正交阵情形D全为与X大小相同的矩阵D则奇异值分解可表示为IXP0Xmp=UmmDmxpPTpxp其中Uu,分别是n,p阶正交矩阵
2 或 非 特征根对应的正交单位特征向量。 其中 的列向量分别是 其中 为 或 的非 特征根 定理 ：任何秩为 的 矩阵 有奇异值分解 奇异值分解 ， ： 0 , , ( ,., ), ( ,., ) diag( ,., ), . 0 0 , , 1 (SVD Singular value decomposition) 1 1 1 1 X X X X U U I V V I U V D X X X X X UDV r n p X r r q r r p r r r r r r T T T T T T T u u v v 其中 分别是 阶正交矩阵。 全为与 大小相同的矩阵 ，则奇异值分解可表示为 奇异值分解 中，若将 补全为正交方阵 补 , ~ , ~ ~ ~ ~ 0 0 ~ 0 , ~ , ~ , U V n p X U D V D X D X U D V U V U V D p p n p n n n p n p n p n r r r T T 有时，将𝑈, 𝑉扩张成正交矩阵应用起来更方便： SVD 𝑈, 𝑉正交 阵情形 Recap
最小二乘奇异值分解的最优性：定理2：平方误差意义下，Xk=UkDkVT=k-1u;v是X的最优秩k逼近：min,IW-X =Xk-XI =Zr=k+1irank(w)=k其中Uk=(u1,.,uk),Vk=(v1,,Vk）分别是XXT，XTX前k个共同最大特征根对应的特征向量。注意当k≥r时，上述误差等于o，此时X=Xk=UkDkVT，这样我们从逼近的角度证明了SVD（定理15.2的证明过程实质上并没有应用定理15.1）SVD正X=UDVT="VA,uvi交对角化Ji=UTXV = D uTXvi =/ai, u,Xv; = 0, 1≤i±j≤r3
3 奇异值分解的最优性： 定理2：平方误差意义下，𝑋𝑘 = 𝑈𝑘𝐷𝑘𝑉𝑘 ⊤ = σ𝑖=1 𝑘 𝜆𝑖 𝐮𝑖𝐯𝑖 ⊤是 𝑋 的 最优秩 𝑘 逼近： min 𝑟𝑎𝑛𝑘 𝑊 =𝑘 𝑊 − 𝑋 𝐹 2 = 𝑋𝑘 − 𝑋 𝐹 2 = σ𝑖=𝑘+1 𝑟 𝜆𝑖 其中 𝑈𝑘 = 𝐮1, . , 𝐮𝑘 , 𝑉𝑘 = 𝐯1, . , 𝐯𝑘 分别是 𝑋𝑋⊤ ，𝑋 ⊤𝑋 前 𝑘 个 共同最大特征根对应的特征向量。 注意当 𝑘 ≥ 𝑟 时，上述误差等于0，此时 𝑋 = 𝑋𝑘 = 𝑈𝑘𝐷𝑘𝑉𝑘 ⊤，这 样我们从逼近的角度证明了SVD （定理15.2的证明过程实质上并 没有应用定理15.1） SVD⇔正 交对角化 𝑋 = 𝑈𝐷𝑉 ⊤ = 𝑖=1 𝑟 𝜆𝑖 𝐮𝑖𝐯𝑖 ⊤ ⇔ 𝑈 ⊤𝑋𝑉 = 𝐷 ⇔ 𝐮𝑖 ⊤𝑋𝐯𝑖 = 𝜆𝑖 , 𝐮𝑖 ⊤𝑋𝐯𝑗 = 0, 1 ≤ 𝑖 ≠ 𝑗 ≤ 𝑟 最小二乘
我们将在典则相关分析、配列、聚类中用到双线性函数uTAV双线性函数极大化的极大化问题，该问题与奇异值分解的最优性有关。定理3.假设矩阵Xnxp的秩为r，其奇异值分解为X=UDVT，其中U = (u1,., ur), V = (vi,.,vr), D = diag(a1,..,a),入1≥≥入r>0,考虑极大化max..uTxv(*)Ilul/={/v=1(1)当u=u1，V=Vi时(*)达到最大，最大值等于最大奇异值a1(2)对任何k≤r,限制ulu1,,uk-1,vvi,.,Vk-1,则在u=ukV=Vk时(*)达到最大,最大值等于/ak证明1：（1）由Cauchy-Schwartz不等式uTXV≤VuTuVVTXTXV=VVTXTXV≤/a当V=V1时后一个等号成立，当uαXv时前一个等号成立，此时，uαXviαu1.(2)证明类似。4
4 定理3. 假设矩阵 𝑋𝑛×𝑝 的秩为 𝑟，其奇异值分解为 𝑋 = 𝑈𝐷𝑉 ⊤, 其中 𝑈 = (𝐮1, . , 𝐮𝑟), 𝑉 = (𝐯1, . , 𝐯𝑟), 𝐷 = 𝑑𝑖𝑎𝑔 𝜆1, . , 𝜆𝑟 , 𝜆1 ≥ ⋯ ≥ 𝜆𝑟> 0, 考虑极大化 max 𝐮 = 𝐯 =1 𝐮 ⊤𝑋𝐯 (∗) (1) 当 𝐮 = 𝐮1， 𝐯 = 𝐯1时(*)达到最大，最大值等于最大奇异值 𝜆1； (2) 对任何 𝑘 ≤ 𝑟, 限制 𝐮 ⊥ 𝐮1, . , 𝐮𝑘−1, 𝐯 ⊥ 𝐯1, . , 𝐯𝑘−1, 则在 𝐮 = 𝐮𝑘， 𝐯 = 𝐯𝑘 时 (*)达到最大, 最大值等于 𝜆𝑘. 证明1： (1) 由Cauchy-Schwartz不等式 𝐮 ⊤𝑋𝐯 ≤ 𝐮⊤𝐮 𝐯 ⊤𝑋⊤𝑋𝐯 = 𝐯 ⊤𝑋⊤𝑋𝐯 ≤ 𝜆1 当 𝐯 = 𝐯1 时后一个等号成立，当 𝐮 ∝ 𝑋𝐯 时前一个等号成立， 此时， 𝐮 ∝ 𝑋𝐯1 ∝ 𝐮1. (2)证明类似。 双线性函 数极大化 我们将在典则相关分析、配列、聚类中用到双线性函数 𝐮 ⊤𝐴𝐯 的极大化问题，该问题与奇异值分解的最优性有关
证明2（拉格朗日乘子法）令n1m2(uTu - 1):f(u,v) = uTXv22令%= Xv- n2u = 0, %= XTu - n1V= 0, 即avauXv= n2u, Xtu = niv故u,v是奇异值分解中的一对特征向量，且uTXv=n1=n2最大为/a，故u=u，v=V1。证明3:A=UDVT，令a=UTu,b=T,因为UUT≤I,则a=uUUu≤uu=1|b所以uAv=uUDVv=a'Db=ablab,/,0若约束，，则U=(OU)TVv其中U,=(u.u),V,=(.k),则uAv=ab,,≤，等等。5
5 证明2（拉格朗日乘子法）令 𝑓 𝐮, 𝐯 = 𝐮 ⊤𝑋𝐯 − 𝜂1 2 𝐯 ⊤𝐯 − 1 − 𝜂2 2 (𝐮 ⊤𝐮 − 1)， 令 𝜕𝑓 𝜕𝐮 = 𝑋𝐯 − 𝜂2𝐮 = 0, 𝜕𝑓 𝜕𝐯 = 𝑋 ⊤𝐮 − 𝜂1𝐯 = 0, 即 𝑋𝐯 = 𝜂2𝐮，𝑋 ⊤𝐮 = 𝜂1𝐯 故 𝐮, 𝐯 是奇异值分解中的一对特征向量，且 𝐮 ⊤𝑋𝐯 = 𝜂1= 𝜂2 最大为 𝜆1，故 𝐮 = 𝐮1， 𝐯 = 𝐯1。 其中 则 ，等等。 若约束 ， ，则 ， ， 所以 证明 ： 令 因为 则 2 2 1 2 1 2 1 1 1 1 1 1 1 1 ( ,., ), ( ,., ), , 0 (0, ), | | || || 1 || || 1, 3 , , , , i i k i k k i i k i i i i k i i p U V A a bV U U V A UDV D a b a b UU A UDV U V UU I u u v v u v v u u v v u u v u v u v a b a u u u u b a u b v T T T T T T T T T T T T T T T T