---
title: Ch6-6
tags: Linear algebra
GA: G-77TT93X4N1
---

# Chapter 6 extra note 6

> Operator norm
> condition number

---

### Operator norm of a linear transformation

Given $T\in\mathcal{L}(V, W)$ where $V$ and $W$ are normed spaces. The operator norm of $T$, denoted by $\|T\|$, is defined as
$$
\tag{1}
\|T\| = \max_{\bf v\in V, \|{\bf v}\|\le 1}\{\|T{\bf v}\|\}.
$$

**Remark:**
(1) is often called *operator* norm or *natural* norm.

**Remark:**
One should verify that (1) indeed defines a [norm](https://hackmd.io/uRRb5etTTN-aS1l4LXG2PQ).

**Proposition:**
$$
\tag{2}
\|T\| = \max_{\bf v\in V, \|{\bf v}\|= 1}\{\|T{\bf v}\|\}.
$$
* Proof (idea):
> If $\|{\bf v}\|\le 1$, then
> $$
> \tag{3}
> T{\bf v} = \|{\bf v}\|\,T\left(\frac{{\bf v}}{\|{\bf v}\|}\right)\le T\left(\frac{{\bf v}}{\|{\bf v}\|}\right).
> $$

**Proposition:**
$$
\tag{4}
\|T{\bf v}\| \le \|T\|\|{\bf v}\|.
$$
* Proof (idea):
> $$
> \tag{5}
> \|T{\bf v}\| = \left\|\|{\bf v}\|\,T\left(\frac{{\bf v}}{\|{\bf v}\|}\right)\right\|= \|{\bf v}\|\left\|T\left(\frac{{\bf v}}{\|{\bf v}\|}\right)\right\|\le \|{\bf v}\|\|T\|.
> $$

**Proposition:**
Let $V$ and $W$ be inner product space, then $\|T\|=\sigma_1$.
* Proof:
> Given $\|{\bf v}\|\le 1$, we have
> $$
> \tag{6}
> \|T{\bf v}\|^2 = \sum^r_{i=1}\sigma^2_i\langle{\bf v}, {\bf v}_i\rangle^2\le\sigma^2_1\sum^r_{i=1}\langle{\bf v}, {\bf v}_i\rangle^2\le\sigma^2_1.
> $$
> Also, choose ${\bf v}={\bf v}_1$, we have
> $$
> \tag{7}
> \|T{\bf v}_1\| = \sigma_1.
> $$
> Therefore, $\|T\|=\sigma_1$.

**Example:**
Let $A\in\mathbb{M}_{m\times n}$, then $A$ defines a linear transfomration and $A\in\mathcal{L}(\mathbb{R}^n, \mathbb{R}^m)$, and the operator $2$-norm of $A$ is
$$
\tag{8}
\|A\|_2 = \sqrt{\rho(A^*A)},
$$
where $\rho(A^*A)$ denotes the largest eigenvalue of $A^*A$.

**Remark:**
Be aware that the notation here is different from the textbook.

---

### Condition number

> To find $x$ such that $Ax=b$.

Given $\hat{x}$, we define the residual as $r = b - A\hat{x}$.

Question: If $\|r\|\le \epsilon$, do we have $\|x-\hat{x}\|<\epsilon$?

Answer: NO!

---

> *Condition number* measures how sensitive the answer is to perturbation in the input data.

Assuming that $A\hat{x}=b - \epsilon$, we define $\hat{x} = x - \delta$ to have
$$
\tag{9}
A(x - \hat{x}) = b - (b-\epsilon) = \epsilon \quad \Rightarrow\quad \delta = A^{-1}\epsilon.
$$
Also,
$$
\tag{10}
\|\delta\| = \|A^{-1}\epsilon\|\le \|A^{-1}\|\|\epsilon\|,
$$
and as a result,
$$
\tag{11}
\frac{\|\delta\|}{\|x\|} \le
\frac{\|A^{-1}\|\|\epsilon\|}{\|x\|}\frac{\|b\|}{\|b\|} =
\frac{\|A^{-1}\|\|\epsilon\|}{\|x\|}\frac{\|Ax\|}{\|b\|} \le
\|A\|\|A^{-1}\|\frac{\|\epsilon\|}{\|b\|}.
$$

We define $\kappa(A)=\|A\|\|A^{-1}\|$ as the *condition number* of a matrix $A$. We have
$$
\tag{12}
\frac{\|\delta\|}{\|x\|} \le\kappa(A)\frac{\|\epsilon\|}{\|b\|}.
$$

**Remark:**
$$
\tag{13}
1 = \|I\| = \|AA^{-1}\|\le \|A\|\|A^{-1}\| = \kappa(A).
$$
So the condition number of a matrix is always greater than or equals to one.

**Remark:**
Condition number depends on the chosen norm. If we choose to use the operator $2$-norm, then
$$
\tag{14}
\kappa(A) = \frac{\sigma_{max}}{\sigma_{min}},
$$
where $\sigma_{max}$($\sigma_{min}$) denotes the largest(smallest) singular values of $A$.

* working example - [2-by-2 linear system](https://github.com/teshenglin/computational_mathematics/blob/master/linear_algebra/cond.ipynb)

---

#### 計算數學 lecture 0

**Question:**
考慮調和級數([Harmonic series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)))
$$
\sum^{\infty}_{n=1} \frac{1}{n}
$$
是否能以程式判斷其收斂或發散?

如果我們以電腦完全依照這級數一項一項做加法, 則一定會收斂到某個數字. 因為可以將此級數拆解為
$$
\sum^{10^{16}}_{n=1} \frac{1}{n} + \sum^{\infty}_{n=10^{16}+1} \frac{1}{n}.
$$
後面那個級數裡的每一項都小於 machine epsilon, 所以當他們被加進級數和時會沒有任何作用.

因此若以程式將此級數一項一項做加法, 一定會不大於前面那個級數和.

**Remark:**
1.
$$
\sum^{N}_{n=1} \frac{1}{n} \approx \int^N_1\frac{1}{x}\,dx = \ln(N).
$$
2. $\ln(10^{16})\approx 37$.

---

### Image compression

* [SVD demo](http://timbaumann.info/svd-image-compression-demo/)
* [Image compression using SVD](https://github.com/teshenglin/computational_mathematics/blob/master/linear_algebra/image_compression.ipynb)
* Vision transformer ([ViT](https://arxiv.org/abs/2010.11929))
* [Better SVD approximation of images, using the SVD](https://youtu.be/ZGwVlnuuzt4?si=zM9TiBLR9keoJNNy)