diff options
| -rw-r--r-- | lecture_1.typ | 51 |
1 files changed, 44 insertions, 7 deletions
diff --git a/lecture_1.typ b/lecture_1.typ index dcade12..b46df53 100644 --- a/lecture_1.typ +++ b/lecture_1.typ @@ -26,7 +26,8 @@ #let colourmaths(x, color) = text(fill: color)[$#x$] -// author: eric1102 - may slightly interfere with maths blocks +// author: eric1102 - https://sitandr.github.io/typst-examples-book/book/typstonomicon/math_display.html +// may slightly interfere with maths blocks #show math.equation: it => { if it.body.fields().at("size", default: none) != "display" { return math.display(it) @@ -181,13 +182,49 @@ $ *Claim*: $norm(M)_"op" = sigma_1$, and $v_1$ is a vector that attains the maximum. \ _Proof_: Let $v in RR^m : norm(v) = 1$. We will write $v = sum_(i = 1)^(m)alpha_i v_i$. So: $ - M dot v & = sum_(i = 1)^(m)alpha_i (M dot v_i) \ - & = sum_(i = 1)^(k) alpha_i dot sigma_i u_i \ - 1 = norm(v)^2 & = sum_(i = 1)^(m)alpha_i^2 \ - norm(M v) & = sum_(i = 1)^(k) alpha_i^2 dot sigma_i^2 \ - & <= sigma_1^2 dot sum_(i = 1)^(k)alpha_i^2 \ - & <= sigma_1^2 + M dot v & = sum_(i = 1)^(m)alpha_i (M dot v_i) \ + & = sum_(i = 1)^(k) alpha_i dot sigma_i u_i \ + 1 = norm(v)^2 & = sum_(i = 1)^(m)alpha_i^2 \ + norm(M v) & = sum_(i = 1)^(k) alpha_i^2 dot sigma_i^2 \ + & <= sigma_1^2 dot sum_(i = 1)^(k)alpha_i^2 \ + & <= sigma_1^2 $ We showed that $norm(M v) <= sigma_1$, and this may be attained by taking $v = v_1$: $M v_1 = sigma_1 u_1 => norm(M v_1) = sigma_1$. +*Reminder*: $v bot v' => lr(chevron.l v, v' chevron.r) = 0$ \ +*Exercise*: $max{norm(M v) : v in RR^m, norm(v) = 1, v bot v_1} = sigma_2$, $v_2$ attains the maximum. + +#pagebreak() + +=== SVD Proof + +Our strategy is that we will construct an orthonormal basis $v_1, dots, v_m$ for $RR^m$, such that $M v_1, dots, M v_m$ +are orthogonal: $lr(chevron.l M v_i, M v_j chevron.r) = 0$. The idea is that +$ + u_1 = (M v_1) / (norm(M v_1)), wide u_2 = (M v_2) / norm(M v_2), wide dots +$ +as long as $M v_i != 0$, and complete it to an orthonormal basis. In particular, $sigma_i := norm(M v_i)$. + +_Proof_: We will construct recursively: ++ Let $v_1$ be a unit vector that maximises $ {norm(M v) : v in RR^(m), norm(v) = 1} $ ++ Given $v_1, dots, v_(i - 1)$, we will let $v_i$ be a unit vector that maximises $ {norm(M v) : v in RR^m, norm(v) = 1, + v bot v_1, dots, v_(i - 1)} $ +We will now prove that $forall i < j #h(0.5em) lr(chevron.l M v_i, M v_j chevron.r) = 0$. Consider $f : RR -> RR, +#h(0.5em) f(t) = norm(M (v_i + t v_j))^2$. ++ We will observe that $t = 0$ is a local maximum of $f(t)$ since $x_t = (v_i + t v_j) / norm(v_i + t v_j)$ is a unit + vector orthogonal to $v_1, dots, v_(i - 1)$. Therefore $norm(M x_t)^2 <= norm(M v_i)^2 = norm(M underbrace(x_0, t = + 0))^2$ + +Now: +$ + f(t) & = norm(M((v_i + t v_j) / norm(v_i + t v_j)))^2 \ + & = (norm(M(v_i + t v_j))^2) / norm(v_i + t v_j)^2 \ + & = norm(M (v_i) + t M (v_j))^2 / (norm(v_i)^2 + 2 lr(chevron.l v_i, t v_j chevron.r) + norm(t v_j)^2) \ + & = (norm(M v_i)^2 + 2 lr(chevron.l M v_i, t M v_j chevron.r) + norm(t M v_j)^2) / (1 + 0 + t^2) \ + & = (norm(M v_i)^2 + 2 t lr(chevron.l M v_i, M v_j chevron.r) + t^2 norm(M v_j)^2) / (1 + t^2) \ + f'(t) & = ((2 lr(chevron.l M v_i, M v_j chevron.r) + 2 norm(M v_j)^2 t) dot (1 + t^2) - 2 t dot (dots)) / ((1 + + t^2)^2) \ + ==> f'(0) & = 2 lr(chevron.l M v_i, M v_j chevron.r) \ + & = 0 "since " t = 0 " is a local maximum" +$ |