CS205A HW4

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾作业4。

Problem 1

(a)假设

那么原问题可以化为如下形式:

构造拉格朗日乘子:

关于$(\Delta J)_{ij}$求偏导并令其为$0$得到

所以

带回$\Delta J.\Delta \vec x =\vec d$可得

因此

回顾各项的定义,我们得到

(b)带入验证即可:

(c)原始的迭代形式为:

由(b)可得

其中

Problem 2

(a)使用奇异值分解:

因为$m=n$,所以$\Sigma$为对角阵,即

因此

计算trace可得

(b)证明一般情形,如果$A\in \mathbb R^{n\times m},B\in \mathbb R^{m\times n}​$,那么

注意到

注意到

所以

(c)由SVD分解可得

那么

并且

利用定义可得

当且仅当

时等号成立,即

(d)对于满足条件$C^TC=I$的$C$,我们有

所以

(e)令

那么我们需要最小化

由$L_1$正则化的特性,我们的结果会使得$A’$某些项为$0$,不妨设非零项的下标为

由SVD可得

所以得到$A_0$的低秩近似。

Problem 3

(a)回顾割线法的定义:

注意到

如果$x_k =x’$,那么

如果$x_{k-1}=x’$,那么

(b)假设$A$的奇异值为

回顾SVD的推导,我们知道

现在假设增加一行$\vec \alpha^T​$,那么

因此

因此$\tilde A$的最小奇异值和最大奇异值均不小于$A$的最小奇异值和最大奇异值。

Problem 4

(a)将$\frac 1 a$视为

的零点,然后利用牛顿迭代法迭代即可,注意

所以

(b)

(c)由(b)可得

要使得计算结果达到$d$位$2$进制小数,我们有

本文标题:CS205A HW4

文章作者:Doraemonzzz

发布时间:2019年04月10日 - 16:37:00

最后更新:2019年04月10日 - 16:37:31

原始链接:http://doraemonzzz.com/2019/04/10/CS205A HW4/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。