拉格朗日乘数法（选讲） 对于一般的矩阵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