Second hour

1 files changed, 76 insertions, 7 deletions

diff --git a/lecture_2.typ b/lecture_2.typ
index 1725a02..b765f74 100644
--- a/lecture_2.typ
+++ b/lecture_2.typ
@@ -39,7 +39,7 @@
 
 = Reminder
 
-*Definition* (SVD): Let there be $M in Mat_(n times m) (RR)$. The SVD of this matrix is:
+*Definition* (SVD): Let there be $M in MM_(n times m) (RR)$. The SVD of this matrix is:
 $
   M = U dot Sigma dot V^T
 $
@@ -54,6 +54,8 @@ $
   tr(A B) & = tr(B A)
 $
 
+*IEP*: $E, F subset.eq R^m$, then $dim(E + F) = dim(E) + dim(F) - dim(E inter F)$ where $E + F = "span"(E union F)$
+
 = Matrix Norms
 
 *Definition* (norm): A norm on a (real) vector space $V$ is a function $norm(dot.c) : V -> [0, inf)$ such that:
@@ -72,7 +74,7 @@ $
 
 == Matrix Norms
 
-This is a fancy name where we take $V$ to be the vector space of matrices: $V = Mat_(n times m) (RR) tilde.equiv R^(n dot
+This is a fancy name where we take $V$ to be the vector space of matrices: $V = MM_(n times m) (RR) tilde.equiv R^(n dot
 m)$. For example, for $M in V$:
 
 + The operator norm / spectral norm is a measure of the size of a matrix, how much it can increase a vector $v$:
@@ -82,15 +84,15 @@ m)$. For example, for $M in V$:
   Recall that $norm(M)_"op" = sigma_1$, the largest singular value of $M$
 + Frobenius norm:
   $
-    norm(M)_F = (sum_(i = 1)^(n) sum_(j = 1)^(m)Mat_(i j)^(2))^(1 / 2)
+    norm(M)_F = (sum_(i = 1)^(n) sum_(j = 1)^(m)MM_(i j)^(2))^(1 / 2)
   $
 
 #pagebreak()
 *Claim*: $norm(M)_F^2 = tr(M dot M^T)$ \
 _Proof_:
 $
-  (M dot M^T)_(i i) & = sum_(j = 1)^(m) Mat_(i j) dot Mat_(j i)^(T) \
-                    & = sum_(j = 1)^(m)Mat_(i j)^(2)
+  (M dot M^T)_(i i) & = sum_(j = 1)^(m) MM_(i j) dot MM_(j i)^(T) \
+                    & = sum_(j = 1)^(m)MM_(i j)^(2)
 $
 
 *Claim*: $norm(M)_F = (sum_(i = 1)^(k)sigma_i^2)^(1 / 2)$\
@@ -113,9 +115,9 @@ $
 
 *Definition* $rk(M) = rank(M) = dim(Im(M))$
 
-*Claim*: Let $M in Mat_(n times m) (RR)$. The rank of $M$ is the minimum number $r$ such that
+*Claim*: Let $M in MM_(n times m) (RR)$. The rank of $M$ is the minimum number $r$ such that
 $
-  exists A in Mat_(n times r) (RR), B in Mat_(r times m) (RR) : M = A dot B
+  exists A in MM_(n times r) (RR), B in MM_(r times m) (RR) : M = A dot B
 $
 It is clear that $rk(A) <= r and rk(A dot B) <= rk(A) <= r$. Therefore, if $M = A dot B => rk(M) <= r$.
 
@@ -133,3 +135,70 @@ $
           )
 $
 Therefore, $Im(M)$ is spanned by $u_i : sigma_i > 0$.
+
+*Question*: Given $M in MM_(n times m)(RR)$, find $B in MM_(n times m) (RR)$ of rank $<= r$ that minimises
+$norm(M - B)_"op"$ and $norm(M - B)_F$.
+
+*Definition*: Given diagonal matrix $Sigma$, and $r <= k$, replace the last $k - r$ singular values on the diagonal with 0.
+
+#pagebreak()
+*Theorem*: For every matrix $B$ of rank $<= r$, it holds that $norm(M - B) >= norm(M - U Sigma_((r)) V^T)$, for both the
+Frobenius, and the operator norm:
+$
+     norm(M - B)_F & >= norm(M - U Sigma_((r)) V^T)_F \
+                   & = (sum_(i = r + 1)^(k)sigma_i^2)^(1 / 2) \
+  norm(M - B)_"op" & >= norm(M - U Sigma_((r)) V^T)_"op" \
+                   & = sigma_(r + 1)
+$
+_Proof_: This proof requires the Min-Max Theorem for singular values (below).
+
+
+*Theorem* (Min-Max Theorem for singular values): Let $M in MM_(n times m) (RR)$, with singular value decomposition $M = U
+Sigma V^T$.
+$
+  forall 1 <= i <= k & = min(m, n) \
+             sigma_i & = max_(E subset.eq RR^m \ dim(E) = i) (min_(v in E \ norm(v) = 1) norm(M v)) \
+                     & = min_(E subset.eq R^m \ dim(E) = m - i + 1) (max_(v in E \ norm(v) = 1) norm(M v))
+$
+The second equality will not be proven, but is left as an exercise. \
+_Proof_ (of first equality):
++ We need to show that there is $E subset.eq RR^m, dim(E) = i : min_(v in E \ norm(v) = 1) norm(M v) = sigma_i$
++ For every $E subset.eq RR^m, dim(E) = i$, it holds that $min_(v in E \ norm(v) = 1) <= sigma_i$, that s $exists v in
+  E, #h(0.4em) norm(v) = 1 : norm(M v) <= sigma_i$
+
+#let sp = [sp]
+1. _Proof_: We will choose $E = sp{v_1, dots, v_i} => dim(E) = i$. Let $v in E, norm(v) = 1$. Let us write
+  $
+                   v & = sum_(j = 1)^(i)alpha_j v_j \
+                   1 & = norm(v) = sum_(j = 1)^(i)alpha_j^2 \
+                 M v & = sum_(j = 1)^(i)alpha_j M v_j \
+                     & = sum_(j = 1)^(i)alpha_j sigma_j u_j \
+     ==> norm(M v)^2 & = sum_(j = 1)^(i)alpha_j^2 sigma_j^2 \
+           norm(M v) & >= sigma_i quad forall v in E, norm(v) = 1 \
+         norm(M v)^2 & = sum_(j = 1)^(i)alpha_j^2 sigma_j^2 \
+                     & >= sigma_i^2 sum_(j = 1)^(i)alpha_j^2 \
+                     & = sigma_i^2 \
+    "Choose" v = v_i & : v in E, norm(v) = 1 and \
+           norm(M v) & = norm(M v_i) \
+                     & = norm(sigma_i u_i) \
+                     & = sigma_i
+  $
++ _Proof_: Given $E$, we need to find the vector, rather than choosing $E$: \
+  Let $E subset.eq R^m$ of $dim(E) = i$. Consider $F = sp{v_i, v_(i + 1), dots, v_m}, #h(0.5em) dim(F) = m - i + 1$.
+  Therefore
+  $
+    dim(E) + dim(F) & = m + 1 \
+     dim(E inter F) & > 0
+  $
+  Let $v in E inter F$ of $norm(v) = 1$.
+  + $v in E, norm(v) = 1$
+  + $v = sum_(j = i)^(m)alpha_j v_j$ since $v in F$.
+  $
+        1 = norm(v) & = sum_(j = i)^(m)alpha_j^2 \
+                M v & = sum_(j = i)^(m) alpha_j M v_j \
+                    & = sum_(j = i)^(k)alpha_i sigma_j u_j \
+    ==> norm(M v)^2 & = sum_(j = i)^(k)alpha_j^2 sigma_j^2 \
+                    & <= sigma_i^2 dot underbrace(sum_(j = i)^(k)alpha_i^2, <= norm(v)^2 = 1) \
+                    & <= sigma_i^2
+  $
+