3 - Norms

Basic Definition

• Norm: A measure of size (of vectors, matrices, etc.)
• For vector, denote $\|v\|$ as the norm of $v$
• Can be defined in many ways

Vector Norm Definition

• A vector norm ($\|\cdot\|$) is a function mapping $\mathbb{R}^n$ to $\mathbb{R}$.
• $\|\cdot\|$ is a norm if:
  1. $\|x\| \geq 0$ for all $x \in \mathbb{R}^n$. $\|x\| = 0$ if and only if $x = 0$ — ไม่ติดลบ + ศูนย์เฉพาะที่ศูนย์
  2. If $\alpha$ is a scalar: $\|\alpha x\| = |\alpha| \cdot \|x\|$ — ยืด-หดตามสเกล
  3. For all $x, y \in \mathbb{R}^n$: $\|x + y\| \leq \|x\| + \|y\|$ ("triangular inequality") — อสมการสามเหลี่ยม
     

Commonly-used Vector Norms

1. 2-norm (Euclidean norm):

$\boxed{\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2} = \sqrt{x^T x}}$

• ตัวอย่าง: $(3,4)$ → $\sqrt{3^2 + 4^2} = 5$ (ระยะทางจริงในระนาบ)
  Proof:

$\sqrt{x^T x} = \sqrt{\begin{bmatrix} x_1 & x_2 & \cdots & x_n \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}} = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2} = \|x\|_2$

2. 1-norm:

$\boxed{\|x\|_1 = \sum_{i=1}^n |x_i|}$

• ตัวอย่าง: $(3,4)$ → $|3|+|4|=7$ (เหมือนเดิน 3 บล็อกไปขวา แล้ว 4 บล็อกขึ้น)
• เหมือน เดินเป็นเส้นตรงแนวแกน

3. ∞-norm:

$\boxed{\|x\|_\infty = \max_{i=1}^n \{|x_i|\}}$

• ความหมาย: สนใจเฉพาะ “ตัวที่ใหญ่ที่สุด” ในเวกเตอร์
• ใช้ใน worst-case analysis หรือเวลาสนใจ error ที่แย่ที่สุด
• ตัวอย่าง: $(3,4)$ → $\max(3,4)=4$

4. p-norm:

$\boxed{\|x\|_p = \left(|x_1|^p + |x_2|^p + \ldots + |x_n|^p\right)^{\frac{1}{p}}, \quad p \geq 1}$

• The 1-, 2-, and ∞-norms are actually p-norms

เป็นการ “ปรับน้ำหนัก” ว่าเราจะให้ความสำคัญกับค่ามาก ๆ แค่ไหน

• $p$ เล็ก → ใส่ใจกับทุกค่าแบบพอ ๆ กัน
• $p$ ใหญ่ → เน้นค่าที่ใหญ่ ๆ มากขึ้นเรื่อย ๆ
• $p \to \infty$ → เหลือแต่ค่าที่ใหญ่ที่สุด (∞-norm)

Example 1

Let $y = \begin{bmatrix} 1 \\ -2 \\ 0 \\ 4 \end{bmatrix}$. Find $\|y\|_2$, $\|y\|_1$, and $\|y\|_\infty$.
Solution:

• $\|y\|_2 = \sqrt{1^2 + (-2)^2 + 0^2 + 4^2} = \sqrt{1 + 4 + 0 + 16} = \sqrt{21}$
• $\|y\|_1 = |1| + |-2| + |0| + |4| = 7$
• $\|y\|_\infty = \max\{|1|, |-2|, |0|, |4|\} = 4$

Exercise 2

• Let $x = \begin{bmatrix} 3 \\ -4 \end{bmatrix}$. Compute $\|x\|_1$, $\|x\|_2$, and $\|x\|_\infty$.
  Solution:
• $\|x\|_1 = |3| + |-4| = 7$
• $\|x\|_2 = \sqrt{3^2 + (-4)^2} = \sqrt{9 + 16} = \sqrt{25} = 5$
• $\|x\|_\infty = 4$

Vector Norm in MATLAB

norm(x); % 2-norm
norm(x,2); % 2-norm
norm(x,1); % 1-norm
norm(x,p); % p-norm
norm(x,inf); % Infinity-norm

Some Vector Norm Properties

• $\|x\|_1 \geq \|x\|_2 \geq \|x\|_\infty$
  • บอกว่า ขนาดที่ได้จาก norm แต่ละแบบ มีลำดับแน่นอน
  • ทำให้เราสามารถ ประมาณกันได้ เช่น ถ้าเรารู้ $|x|_\infty$ อยู่ในกรอบ ก็รู้เลยว่า $|x|_2$ และ $|x|_1$ ก็ต้องไม่ต่ำกว่านี้
• Hölder inequality:
  $\left|x^T y\right| \leq \|x\|_p \|y\|_q, \quad \frac{1}{p} + \frac{1}{q} = 1$
  • คิดง่าย ๆ ว่า ถ้า $x$ ใหญ่มาก และ $y$ ใหญ่มาก การคูณรวมกันก็จะ “ไม่เกินกว่า” ผลคูณของความใหญ่ตาม norm ที่เลือก
• "Cauchy-Schwarz inequality":
  $\left|x^T y\right| \leq \|x\|_2 \|y\|_2$
  • dot product ของสองเวกเตอร์ ไม่เคยใหญ่เกินกว่าผลคูณของความยาวจริง ๆ

Orthogonal Matrix Property

Suppose $Q \in \mathbb{R}^{n \times n}$ is an orthogonal matrix (which means $Q^T Q = QQ^T = I$ by definition).
$\boxed{\|Qx\|_2 = \|x\|_2}$
Proof:
Recall $\|y\|_2 = \sqrt{y^T y}$.
$\|Qx\|_2 = \sqrt{(Qx)^T Qx} = \sqrt{x^T Q^T Qx} = \sqrt{x^T x} = \|x\|_2$

Theorem (The Equivalence of Norms)

For any two norms $\|\cdot\|_a$ and $\|\cdot\|_b$, there exists a pair of real numbers $0 < C_1 \leq C_2$ such that, for all $x$:
$\boxed{C_1 \|x\|_b \leq \|x\|_a \leq C_2 \|x\|_b}$
Interpretation: If a vector $x$ is small under one norm, it is small under any other norm.

Matrix Norm

• Define on matrix $A \in \mathbb{R}^{m \times n}$
• Same three properties of norms must hold for matrix norms (อยู่ข้างบนแล้วเด้อ)
• The equivalence of norms also applies to matrix norms

Matrix Norm คือ การวัดว่าเมทริกซ์นี้ทำให้เวกเตอร์ใหญ่ขึ้นได้มากสุดแค่ไหน

Useful Matrix Norms

$A \in \mathbb{R}^{m \times n}$

1. Frobenius norm:

$\boxed{\|A\|_F = \left(\sum_{i=1}^m \sum_{j=1}^n a_{ij}^2\right)^{\frac{1}{2}}}$

• สูตร: เอาทุกตัวในเมทริกซ์มายกกำลังสอง บวกกันหมด แล้วรูท
• ความหมาย: วัดเหมือนว่าเอา entries ทั้งหมดมาต่อเป็นเวกเตอร์ยาว ๆ แล้ววัด 2-norm

2. Induced p-norms:

$\boxed{\|A\|_p = \max_{x \neq 0} \frac{\|Ax\|_p}{\|x\|_p} = \max_{\|x\|_p = 1} \|Ax\|_p}$
Following from the definition of p-norm:

• 1-norm (Maximum absolute column sum):
  • คิดว่า "คอลัมน์ไหนรวมค่ามากที่สุด"
    $\boxed{\|A\|_1 = \max_{j=1,\ldots,n} \sum_{i=1}^m |a_{ij}|}$
• ∞-norm (Maximum absolute row sum):
  • คิดว่า "แถวไหนรวมค่ามากที่สุด"
    $\boxed{\|A\|_\infty = \max_{i=1,\ldots,m} \sum_{j=1}^n |a_{ij}|}$
• 2-norm: (Will see later)

Example 3

Let $B = \begin{bmatrix} -2 & 0 \\ 2 & 3 \end{bmatrix}$. Find $\|B\|_F$, $\|B\|_1$, and $\|B\|_\infty$.
Solution:

• $\|B\|_F = \sqrt{(-2)^2 + 0^2 + 2^2 + 3^2} = \sqrt{17}$
• $\|B\|_1 = \max\{|-2| + |2|, |0| + |3|\} = \max\{4, 3\} = 4$
• $\|B\|_\infty = \max\{|-2| + |0|, |2| + |3|\} = \max\{2, 5\} = 5$

Exercise 4

1. Let $A = \begin{bmatrix} 1 & -1 & 2 \\ 1 & 2 & 0 \end{bmatrix}$

Solution:

• $\|A\|_F = \sqrt{1^2 + (-1)^2 + 2^2 + 1^2 + 2^2 + 0^2} = \sqrt{11}$
• $\|A\|_1 = \max\{|1| + |1|, |-1| + |2|, |2| + |0|\} = \max\{2, 3, 2\} = 3$
• $\|A\|_\infty = \max\{|1| + |-1| + |2|, |1| + |2| + |0|\} = \max\{4, 3\} = 4$

2. Let $C = \begin{bmatrix} 0 & 1 \\ -1 & -2 \\ 3 & 1 \end{bmatrix}$

Solution:

• $\|C\|_F = \sqrt{0^2 + 1^2 + (-1)^2 + (-2)^2 + 3^2 + 1^2} = \sqrt{16} = 4$
• $\|C\|_1 = \max\{|0| + |-1| + |3|, |1| + |-2| + |1|\} = \max\{4, 4\} = 4$
• $\|C\|_\infty = \max\{|0| + |1|, |-1| + |-2|, |3| + |1|\} = \max\{1, 3, 4\} = 4$

Matrix Norm in MATLAB

norm(A); % 2-norm
norm(A,2); % 2-norm
norm(A,1); % 1-norm
norm(A,inf); % Infinity-norm
norm(A,"fro"); % Frobenius-norm
norm(A,'fro'); % Frobenius-norm

Note: Other matrix induced p-norms are not implemented in the norm() function. Only $p = 1, 2, \infty$ are provided.

Some Matrix Norm Properties

สองทฤษฎีที่ต้องรู้ (แต่ไม่ต้องท่องแห้ง ๆ เพราะมันมีความหมาย) เริ่ด

Theorem (Subordination)

For any vector p-norm and induced matrix p-norm:
$\boxed{\|Ax\|_p \leq \|A\|_p \cdot \|x\|_p}$
where $A \in \mathbb{R}^{m \times n}$ and $x \in \mathbb{R}^n$. This is called subordination.

Proof:
$\|A\|_p = \max_{y \neq 0} \frac{\|Ay\|_p}{\|y\|_p} \geq \frac{\|Ax\|_p}{\|x\|_p}, \text{ for any } x$
Therefore: $\|A\|_p \cdot \|x\|_p \geq \|Ax\|_p$

คิดเหมือนเครื่องขยายเสียง: ต่อให้เปิดไมค์ดังแค่ไหน มันก็ไม่ดังเกินกว่าความสามารถของแอมป์

Theorem (Submultiplicativity)

$\boxed{\|AB\|_p \leq \|A\|_p \cdot \|B\|_p}$
for any p-norm, where $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{n \times l}$.

คิดว่า $B$ เป็นการยืดครั้งแรก, $A$ เป็นการยืดครั้งที่สอง → ผลรวมการยืด “ไม่มีวันเกิน” คูณกันตรง ๆ

Proof:
$\|AB\|_p = \max_{\|x\|_p = 1} \|ABx\|_p = \|ABx_{\max}\|_p$
$\leq \|A\|_p \cdot \|Bx_{\max}\|_p \quad \text{(by subordination)}$
$\leq \|A\|_p \cdot \max_{\|x\|_p = 1} \|Bx\|_p \quad \text{(since } \|x_{\max}\|_p = 1\text{)}$
$= \|A\|_p \cdot \|B\|_p$