First hour

1 files changed, 135 insertions, 0 deletions

diff --git a/lecture_2.typ b/lecture_2.typ
new file mode 100644
index 0000000..1725a02
--- /dev/null
+++ b/lecture_2.typ
@@ -0,0 +1,135 @@
+#set document(
+  title: [Lecture 2 - Matrix Norms: Low rank Approximation],
+  author: "Gidon Rosalki",
+  date: auto,
+)
+#set heading(numbering: "1.")
+#set text(font: "New Computer Modern")
+#set page(margin: (
+  bottom: 0.5cm,
+  right: 1.5cm,
+  left: 1.5cm,
+  top: 1.5cm,
+))
+#set list(indent: 10pt)
+#set enum(indent: 10pt)
+
+#show title: set align(center)
+#show link: set text(rgb("005eff"))
+#show link: underline
+#show math.equation.where(block: true): set block(breakable: true)
+#title()
+#align(center)[
+  Gidon Rosalki \
+  2026-10-20
+]
+
+#let colourmaths(x, color) = text(fill: color)[$#x$]
+
+// 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)
+  }
+  it
+}
+
+#let Mat = [Mat]
+
+= Reminder
+
+*Definition* (SVD): Let there be $M in Mat_(n times m) (RR)$. The SVD of this matrix is:
+$
+  M = U dot Sigma dot V^T
+$
+Where $U, V$ are orthogonal. The columns $u_1, dots, u_n$ of $U$ are orthonormal basis for $RR^n$, and the columns $v_1,
+dots, v_m$ of $V$ are an orthonormal basis for $RR^m$. \
+$Sigma$ is a diagonal matrix where $forall i != j, Sigma_(i j) = 0$. Note that $Sigma$ is not necessarily square. We
+denote the values of the diagonal $sigma_1 >= sigma_2 >= dots >= sigma_k : k = min(m, n)$.
+
+*Definition* trace:
+$
+    tr(A) & = sum_(i = 1)^(n)A_(i, i) \
+  tr(A B) & = tr(B A)
+$
+
+= Matrix Norms
+
+*Definition* (norm): A norm on a (real) vector space $V$ is a function $norm(dot.c) : V -> [0, inf)$ such that:
++ $norm(x) = 0 <==> x = 0 quad forall x in V$
++ Triangle inequality: $norm(x + y) <= norm(x) + norm(y) quad forall x, y in V$.
++ $norm(alpha x) = abs(alpha) norm(x) quad forall x in V, alpha in RR$
+
+== Examples
+
+For $V = RR^n$
+$
+            norm(x) = & norm(x)_2        && = sqrt(sum_(i = 1)^(n)x_i^2) \
+  1 <= p < infinity : & norm(x)_p        && = (sum_(i = 1)^(n) abs(x_i)^(p))^(1 / p) \
+                      & norm(x)_infinity && = max_(i in {1, dots, n}) abs(x_i)
+$
+
+== 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
+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$:
+  $
+    norm(M)_"op" = max {norm(M v) : v in RR^m, norm(v) = 1}
+  $
+  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)
+  $
+
+#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)
+$
+
+*Claim*: $norm(M)_F = (sum_(i = 1)^(k)sigma_i^2)^(1 / 2)$\
+_Proof_:
+$
+  norm(M)_F^2 & = tr(M M^T) \
+              & = tr(underbrace(U Sigma V^T, M) dot underbrace(V Sigma^T U^T, M^T)) \
+              & = tr(underbrace(U Sigma Sigma^T, A) underbrace(U^T, B)) \
+              & = tr(U^T U Sigma Sigma^T) \
+              & = tr(Sigma Sigma^T) \
+              & = norm(Sigma)_F^2 \
+              & = sum_(i = 1)^(k)sigma_i^2
+$
+
+= Low Rank Approximation
+
+#let rk = [rk]
+#let rank = [rank]
+#let Im = [Im]
+
+*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
+$
+  exists A in Mat_(n times r) (RR), B in Mat_(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$.
+
+*Claim*: Suppose that the singular values of $M$ are $sigma_1 >= sigma_2 >= dots >= sigma_k >= 0$. Then
+$rk(M)$ is the number of non-zero singular values.
+$
+  rk(M) = max{i : i < k and sigma_i > 0}
+$
+_Proof_:
+$
+      M & = U Sigma V^T \
+  M v_i & = cases(
+            sigma_i u_i && "if" 1 <= i <= k,
+            0 && "if" i > k
+          )
+$
+Therefore, $Im(M)$ is spanned by $u_i : sigma_i > 0$.