奇异值(singular values) 通知：第5次作业将于今天稍后发布 对于一般的m×n实数矩阵A,可以有奇异值分解： A=USVT A的形状：m×n U的形状：mm S的形状：mxn V的形状：nxn UTU=Im VTV=In 观察： AAT USSTUT ATA=VSTSVT AAT和ATA都是实数对称阵，可做特征值分解！ 2
奇异值 (singular values) 通知：第5次作业将于今天稍后发布 对于一般的�×�实数矩阵�，可以有奇异值分解： � = � � �� � 的形状：�×� �的形状：�×� �的形状：�×� �的形状：�×� ��� = ��, ��� = �� 观察： ��� = ������ ��� = ������ ���和���都是实数对称阵，可做特征值分解！ 2
SVD 定理：AAT和ATA有着相同的非零特征值。 证明：考虑AAT的特征值≠0和特征向量u:AATu=λu ATA(ATu)=AT(AATu)=AT(Au)=A(ATu) 可见，只要ATu≠0，则ATu为ATA的一个特征向量，特征值也是。不 妨假设ATu=0,则AATu=A(ATu)=0,与≠0矛盾。 类似地，考虑ATA的特征值)≠0和特征向量v:ATAv=λv,也有 AAT(Av)=A(ATAv)=A(Av)=A(Av). 同理有Av≠0，因此Av为AAT的一个特征向量，特征值也是λ。 3
SVD 定理：���和���有着相同的非零特征值。 证明：考虑���的特征值� ≠ �和特征向量�： ���� = �� ��� ��� = �� ���� = �� �� = �(���) 可见，只要��� ≠ �，则���为 ���的一个特征向量，特征值也是�。不 妨假设��� = �，则���u = � ��� = �，与 � ≠ �矛盾。 类似地，考虑���的特征值� ≠ �和特征向量�： ���� = ��，也有 ��� �� = � ���� = � �� = � �� . 同理有 �� ≠ �，因此��为 ���的一个特征向量，特征值也是�。 3
SVD AAT和ATA有着相同的非零特征值 把它们记作{)}，另外对AAT和ATA进行谱分解，可得到正规正交的向量 {u,{v}作为它们的特征向量： AATui Aiui ATAvi=Aivi 把{u,组合成矩阵U,v组合成矩阵V,则有UrU=Im,VTV=In 回顾之前的证明： 若u为AAT的一个特征向量，则ATu为ATA的一个特征向量，且有着 相同的特征值； 若v为ATA的一个特征向量，则Av为AAT的一个特征向量，且有着 相同的特征值 4
SVD ���和���有着相同的非零特征值 把它们记作 �! ，另外对���和���进行谱分解，可得到正规正交的向量 �� , �� 作为它们的特征向量： ����� = ���� ����� = ���� 把 �� ,组合成矩阵�， �� 组合成矩阵�，则有��� = ��, ��� = �� 回顾之前的证明： • 若�为���的一个特征向量，则���为���的一个特征向量，且有着 相同的特征值； • 若�为���的一个特征向量，则��为���的一个特征向量，且有着 相同的特征值 4
SVD 回顾之前的证明： ·若u为AAT的一个特征向量，则ATu为ATA的一个特征向量，且有着相同的特征值： 。 若v为ATA的一个特征向量，则Av为AAT的一个特征向量，且有着相同的特征值 AATui Aiui ATAvi=Aivi ATui=ivi Av:=V几iu 不失一般性地假设m>n,则有 UrAV=diag(,,V几n) →A=USVI S的对角线元素被称作奇异值(singular values)),通常记作o1≥o2≥…≥on≥0 从几何上看，矩阵A的作用为：Rn上的旋转变换、伸缩变换和Rm上的旋转变换 5
SVD 回顾之前的证明： • 若�为���的一个特征向量，则���为���的一个特征向量，且有着相同的特征值； • 若�为���的一个特征向量，则��为���的一个特征向量，且有着相同的特征值 ����� = ���� ����� = ���� ���� = �� �� ��� = �� �� 不失一般性地假设� > �，则有 ���� = ���� ��, … , �� ⇒ � = � � �� �的对角线元素被称作奇异值(singular values)，通常记作�$ ≥ �% ≥ ⋯ ≥ �& ≥ 0 从几何上看，矩阵�的作用为： ℝ�上的旋转变换、伸缩变换和ℝ�上的旋转变换 5
SVDRayleigh quotient 回顾特征值的min-max刻画，记Rg(x)= xTBx 对于对称的矩阵B,R(x)在特征值处取到极值 回顾lAl2=maX A业，cond2(A)=IIAIl2·‖A-1l2 x≠0lx2 对于对称正定的矩阵A, IAl2=入max(A) cond2(A)=Amax(A)/Amin(A) 对于一般的矩阵呢？ lAll2 =amax (ATA)=Omax(A) condz(A)=VAmax(ATA) Omax(A) √min(ATA) Omin(A) 6
SVD与Rayleigh quotient 回顾特征值的min-max刻画，记�� � ≔ ��� � ��� 对于对称的矩阵�， �� � 在特征值处取到极值 回顾 � ! ≔ max +,- .+ ( + ( ， ����/ � ≔ � / ⋅ �01 / 对于对称正定的矩阵�， � ! = �23+(�) ����/ � = �23+(�)/�245(�) 对于一般的矩阵呢？ � / = �23+ �6� = �23+ � ����/ � = �23+ �6� �245 �6� = �23+ � �245 � 6
拉格朗日乘数法（选讲） 对于一般的矩阵A,max IlAxll2什么时候取到极值？ ‖xl2=1 除了通过特征值的min-max刻画，还可以通过拉格朗日乘数 法，把带约束的最优化问题转化为不带约束的： L(A):=supx xTATAx-A(xTx-1) 对x求梯度也可得ATAx=λx 因此也可得到，max‖Axl2=V几max(ATA) x2=1 7
拉格朗日乘数法(选讲) 对于一般的矩阵 �， max ; +<= �� 5什么时候取到极值？ 除了通过特征值的min-max刻画，还可以通过拉格朗日乘数 法，把带约束的最优化问题转化为不带约束的： � � ≔ ���� ����� � − �(��� − �) 对�求梯度也可得��� � = �� 因此也可得到 max 7 "89 �� / = �:;7 �<� 7
SVDSow rank factorization min(m,n) A= oju 考虑如下的近似A==1ouv吲 Eckart-Young?定理：A是所有列空间的维度最多为r的矩阵中，能同时最小化 A-A2和IA-A,的矩阵 Many applications: Principal component analysis Data visualization Genomes can encode geography Eigenfaces Recommender systems 。 Latent semantic analysis 8
SVD与low rank factorization � = = �%� ���(�,�) ������ � 考虑如下的近似�7 ≔ ∑�#� � ������ � Eckart-Young定理 ： �?是所有列空间的维度最多为 �的矩阵中，能同时最小化 �? − � � 和 �7 − � �的矩阵 Many applications: • Principal component analysis – Data visualization – Genomes can encode geography – Eigenfaces • Recommender systems • Latent semantic analysis 8
嫩编 SVD与伪逆pseudoinverse (选讲) min(m,n) A= ojuv{ =1 A=s*Ur=∑是w i:0≠0 如果A可逆，则A+=A-1 如果A是overdetermined,则A+b为Ax=b的最小二乘解 如果A是underdetermined,则A+b为Ax=b中2范数最小 的最小二乘解 9
SVD与伪逆pseudoinverse （选讲） � = # �$� ���(�,�) ������ � �+ = ��+�� = & �:��0� � �� ���� � 如果�可逆，则�, = �-� 如果�是overdetermined，则�+�为 �� = �的最小二乘解 如果�是underdetermined，则�,�为 �� = �中2范数最小 的最小二乘解 9
Random walk on graphs 给定图G=(V,E) 图上的随机游走： 。 从一个给定的顶点出发 ·接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 ·不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？（混合时间，mixing time) 4. 从点s出发，多久才会到达点t?(hitting time) 5. 多久才会遍历每个顶点至少一次？（遍历时间，cover time) 10
Random walk on graphs 给定图� = (�, �) 图上的随机游走: • 从一个给定的顶点出发 • 接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 • 不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？(混合时间，mixing time) 4. 从点s出发，多久才会到达点t? (hitting time) 5. 多久才会遍历每个顶点至少一次？(遍历时间，cover time) 10
Random walk on graphs 这个随机过程的“长期表现”是怎么样的呢？ 1.重复t步之后，当前顶点是某个顶点u的概率是多少？ 2.是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？（混合时间，mixing time) 4. 从点s出发，多久才会到达点t?(hitting time) 5. 多久才会遍历每个顶点至少一次？（遍历时间，cover time) 前3个问题可以通过纯概率的方法(coupling)来研究；我们将讨 论如何利用与幂迭代的联系，通过马尔可夫链(Markov chains)转 移矩阵的特征值来研究。 后2个问题我们将留到之后讨论“图与电阻电路网络”的时候 11
Random walk on graphs 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？(混合时间，mixing time) 4. 从点s出发，多久才会到达点t? (hitting time) 5. 多久才会遍历每个顶点至少一次？(遍历时间，cover time) 前3个问题可以通过纯概率的方法(coupling)来研究；我们将讨 论如何利用与幂迭代的联系，通过马尔可夫链(Markov chains)转 移矩阵的特征值来研究。 后2个问题我们将留到之后讨论“图与电阻电路网络”的时候 11