Linear Algebra Review: Vector Norms, Gram-Schmidt and QR, Fundamental Theorem of Linear Algebra

2023-07-11

Linear Alegbra Bootcamp

We'll review:

• Vectors, Norms
• Gram-Schmidt
• Fundamental Theorem of Linear Algebra

Vector: $\vec{x} \in R^n$

2-norm(Euclidean Norm): $\mid\mid\vec{x}\mid\mid_2=\sqrt{\sum_{i=1}^n x_i^2}$

Norm

Vector Space $\mathcal{X}$

A $f: \mathcal{X} \rightarrow \mathbb{R}$ is a norm if

• $||\vec{x}|| \geq 0, \forall \vec{x} \in \mathcal{X},$ and $||\vec{x}|| = 0$ if and only if $\vec{x}=0$.
• Triangle inequality: $||\vec{x}+\vec{y}|| \leq ||\vec{x}|| + ||\vec{y}||, \forall \vec{x}, \vec{y} \in \mathcal{X}$.
• $||\alpha \vec{x}||=|\alpha|||\vec{x}||,\forall \alpha \in \mathbb{R}, \vec{x} \in \mathcal{X}$.

Examples

$l_p$-norm

$\mid\mid\vec{x}\mid\mid_p \dot{=} (\sum_{i=1}^{n}|x_i|^p)^{1/p}$,$1\leq q \lt \infty$

Choose $p=2$, Euclidean norm.

Choose $p=1$, Manhattan norm. $\mid\mid\vec{x}\mid\mid_1=\sum_{i=1}^n|x_i|$

Choose $p=\infty$, $\mid\mid\vec{x}\mid\mid_\infty=\max_{i=1 \dots n}|x_i|$

Cauchy-Schwartz Inequality

Inner product: $<\vec{x},\vec{y}>=\vec{x}^T\vec{y}=||\vec{x}||_2||\vec{y}||_2\cos\theta$

$\theta$ is the angle between $\vec{x}$ and $\vec{y}$.

$$ <\vec{x}, \vec{y}> \leq ||\vec{x}||_2||\vec{y}||_2 $$

$$ |\vec{x}^T\vec{y}| \leq ||\vec{x}||_2||\vec{y}||_2 $$

Holder's Inequality

$p, q \geq 1, s.t. \frac{1}{p} + \frac{1}{q} = 1$

$$ |\vec{x}^T\vec{y}| \leq \sum_{i=1}^n|x_iy_i| \leq ||\vec{x}||_p||\vec{y}||_q $$

Cauchy-Schwartz Inequality is a special case of Holder's Inequality when $p=q=\frac{1}{2}$.

First optimization problem

$$ \max \vec{x}^T\vec{y} \ ||\vec{x}||_p \leq 1 $$

$\vec{y} \in \mathbb{R}$ is fixed and given.

Start with $p=2$ case, $||\vec{x}||_2 \leq 1$ is a circle with radius of 1. $\vec{x}=\frac{\vec{y}}{||\vec{y}||_2}$ is the unit vector in direction of $\vec{y}$.

$p=\infty$, the geometry in $\mathbb{R}^2$ is a square "ball". $\vec{x}^T\vec{y}=x_1y_1+x_2y_2+\dots+x_ny_n$, $x_i=sgn(y_i)$, $\vec{x}=sgn(\vec{y})$.

$$ \max_{\mid\mid\vec{x}\mid\mid_{\infty}} \vec{x}^T\vec{y} = \sum_{i=1}^n |y_i| = \mid\mid\vec{y}\mid\mid_1 $$

$p=1$, the geometry(norm ball or unit ball) in $\mathbb{R}^2$ is a "diamond". $\vec{x}^T\vec{y} \leq |\vec{x}^T \vec{y}|=|\sum_{i=1}^n x_iy_i|$.

By triangle inequality $|\sum_{i=1}^n x_iy_i| \leq \sum_{i=1}^n |x_iy_i|$.

$|y_{max}|$: largest absolute value of $|y_i|$

$\sum_{i=1}^n|x_i||y_i| \leq \sum_{i=1}^n|x_i||y_{max}| \leq |y_{max}| = \mid\mid \vec{y} \mid\mid_{\infty}$

$\vec{y} = (y_1,y_2,\dots, y_{max}, \dots y_n)$

$\vec{x} = (0, 0, \dots, sgn(y_{max}), \dots, 0)$

Gram-Schmidt/QR-decomposition

$\mathcal{X}$: ${\vec{a_1},\vec{a_2},\dots, \vec{a_n}}$ are basis of the vector space.

Orthonormal basis for the vector space

Choose $\vec{q_1}=\vec{a_1}/\mid\mid \vec{a_1} \mid\mid_2$, $\mid\mid \vec{q_1} \mid\mid = 1$.

Project $\vec{a_2}$ along $\vec{q_1}=\vec{q_1}<\vec{a_2},\vec{q_1}>$ ($\vec{q_1}$ is normalized).

$\vec{s_2}=\vec{a_2}-\vec{q_1}<\vec{a_2},\vec{q_1}>$

$\vec{q_2}=\vec{s_2}/\mid\mid \vec{s_2} \mid\mid_2$

From the below pattern, $\vec{q_3}$ is the spam{$\vec{q_1},\vec{q_2},\vec{q_3}$} = spam{$\vec{a_1},\vec{a_2},\vec{a_3}$}. $\vec{q_3} \bot \vec{q_1}, \vec{q_2}$.

$\vec{s_3}= \vec{a_3}-<\vec{a_3},\vec{q_1}>\vec{q_1}-<\vec{a_3},\vec{q_2}>\vec{q_2}$

$\vec{q_3}=\vec{s_3}/\mid\mid \vec{s_3} \mid\mid_2$

Continue doing this...

$$ A=QR $$

$$ [\vec{a_1},\dots, \vec{a_n}]=[\vec{q_1},\dots, \vec{q_n}] \begin{bmatrix} r_{11} & r_{12} & \dots & r_{1n} \\ 0 & r_{22} & \dots & r_{2n} \\ 0 & 0 & \ddots & \vdots \\
0 & 0 & 0 & r_{nn} \end{bmatrix} $$