Norms and Condition Number

Norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways, which can be used to measure the size of vectors (vector norm) and matrices (matrix norm). And norm is denoted by \(\parallel . \parallel\).

The condition number is an application of the derivative, and is formally defined as the value of the asymptotic worst-case relative change in output for a relative change in input. The "function" is the solution of a problem and the "arguments" are the data in the problem, so the condition number depends on the nature of the underlying problem.

Conditions of Norms

To be valid and useful as norms, all norms must satisfy the following conditions:

1. \(\parallel A \parallel\) \(\ge 0\) for vectors \(\parallel x \parallel\) \(\ge 0\)

2. \(\parallel A \parallel\) \(= 0\) if and only if \(A=0\)

3. \(\parallel \alpha A \parallel\) = \(\mid \alpha\mid.\parallel A \parallel\)

4. \(\parallel A+B \parallel\) \(\le\) \(\parallel A \parallel + \parallel B \parallel\), triangle inequality
   

5. \(\parallel AB \parallel\) \(\le\) \(\parallel A \parallel . \parallel B \parallel\), Cauchy-Schwarz inequality also \(\parallel Ax \parallel\) \(\le\) \(\parallel A \parallel . \parallel x \parallel\) is valid

Vector Norms

2-norm is most used but which one to use depends on the application. Let \(x\) be a vector of length \(n\)

1. 2-norm, Euclidian norm:
   \(\|x\|_{2}=\sqrt{\left|x_{1}\right|^{2}+\left|x_{2}\right|^{2}+\cdots+\left|x_{n}\right|^{2}}=\sqrt{x^{T} x}\)

2. 1-norm, minimum norm:
   \(\|x\|_{1}=\left|x_{1}\right|+\left|x_{2}\right|+\cdots+\left|x_{n}\right|\)

3. \(\infty\) -norm, maximum norm:
   \(\|x\|_{\infty}=\max _{i}\left\{\left|x_{1}\right|, \ldots,\left|x_{n}\right|\right\}\)

Matrix Norms

1. Frobenius norm (straightforward extension of the Euclidean norm):
   \(\|A\|_{F}=\sqrt{\sum_{i=1}^{m} \sum_{i=1}^{n} a_{i j}^{2}}\)

2. Another common matrix norm (\(Ax\) and \(x\) are vectors):
   \(\|A\|=\max _{x \neq 0} \frac{\|A x\|}{\|x\|}\)

Norms

1. 1-norm, min norm, \(l_1\)-norm:
   \(\|A\|_{1} = \max _{1 \le j \le n} \sum_{i=1}^{m} \left|a_{ij}\right|\)

2. \(\infty\)-norm, max norm, \(l_{\infty}\)-norm:
   \(\|A\|_{\infty} = \max _{1 \le i \le m} \sum_{j=1}^{n} \left|a_{ij}\right|\)

3. 2-norm, Euclidian/spectral norm, \(l_2\)-norm (\(\lambda(A^{T}A)\) are the eigenvalues of \(A^{T}A\)):
   \(\|A\|_{2} = \sqrt{\max \{ \lambda (A^{T}A)\}}\)
   

Norm Calculation in Python

import numpy as np
A = np.array([[1,-2],[6,4]])
# 1-norm
np.linalg.norm(A,1)
# max-norm
np.linalg.norm(A,np.inf)
# 2-norm
np.linalg.norm(A,2) 
# Frobenius
np.linalg.norm(A,’fro’)
# Default
np.linalg.norm(A)            

Characteristics of Condition Number

1. A very big condition number suggests that matrix close to singular (\(cond \approx 10^{16}\)), and it also means that the system is sensitive to these perturbations.

2. Best possible case: Condition number = 1
   \(cond(A)\) \(=\) \(\parallel A^{-1} \parallel . \parallel A \parallel\) \(\le\) \(\parallel A^{-1}A \parallel\) \(=\) \(\parallel I \parallel\) \(= 1\)
   meaning no magnification at all

3. No sharp definition for what’s large/small.

4. Condition number also tends to get bigger when matrix size increases.

Condition Number Calculation in Python

import numpy as np
A = np.array([[1,1],[1,-1]])
# 1-norm condition no.
np.linalg.cond(A,1)      
# max-norm condition no.
np.linalg.cond(A,np.inf) 
# 2-norm condition no.
np.linalg.cond(A,2)      
# Frobenius condition no.
np.linalg.cond(A,’fro’)