Norms

Norm is the generalization of the notion of "length" to vectors, matrices and tensors.

A norm is any function $f$ that statisfies the following 3 conditions:

• $f(x) = 0 => x = 0$

• Triangular Inequality: $f(x+y) \le f(x) + f(y)$​

• Linearity: $f(\alpha x) = |\alpha|f(x)$

There are 2 reasons to use norms:

• To estimate how "big" a vector or matrix or a tensor is.

• To estimate "how close" one tensor is to another:

  • $||\triangle{v}|| = ||v_1 - v_2|| \\$

Euclidean Norm

The euclidean norm is given by the below equation:

$$||v||_2 = (v_1^2+v_2^2 + ... + v_n^2)^{1/2}$$

​It is also called 2-norm or L2 norm. A vector of length one is said to be a unit vector.

There is a relation between euclidean norm and dot product.

$$v^Tv = \begin{pmatrix} v_0 \\ v_1 \\ ... \\ v_{n-1} \\ \end{pmatrix}^T \begin{pmatrix} v_0 \\ v_1 \\ ... \\ v_{n-1} \\ \end{pmatrix} \\ = \begin{pmatrix} v_0 & v_1 & ... &v_{n-1} \end{pmatrix} \begin{pmatrix} v_0 \\ v_1 \\ ... \\ v_{n-1} \\ \end{pmatrix} \\ = v^2_0 + v^2_1 + ... + v^2_{n-1}$$

Thus, we can observe that:

$$||v||_2 = \sqrt{v^Tv}$$

The length of a vector also equals the square root of the dot product of the vector with itself.

Absolute Value of A Complex Number

Consider the following complex number:

$$\chi = \chi_r + \chi_c i, \\ where \hspace{2mm}i = \sqrt{-1}$$

Then, absolute value of a complex number is given by

$$|\chi| = \sqrt{\chi^{2}_{r} + \chi^{2}_{c}} = \sqrt{\overline{\chi}\chi} \\ where \hspace{2mm} \overline{\chi} = \chi_r - \chi_ci$$

$\overline{\chi}$ is also called the conjugate of $\chi$. Following are the properties of absolute value of a complex number:

• $\chi \neq 0 => |\chi| > 0$. This also means that the norm is positive definite.

• $|\alpha\chi| = |\alpha||\chi|$. This means that the norm is homogenous.

• $|\chi + \psi| \leq |\chi| + |\psi|$. This means that the norm obeys triangle inequality.

Length of A 2D Vector

Let $x \isin \mathbb{R}^2 \hspace{2mm} and \hspace{2mm} x = \begin{pmatrix} \chi_0 \\ \chi_1 \end{pmatrix}$. The (Euclidean) length of $x$ is given by:

$$\sqrt{\chi^{2}_{0} + \chi^{2}_{1}}$$

Slicing & Dicing: Dot Product

Consider the dot product of 2 vectors $x$ and $y$. The dot product can be given:

• Partitioning the vectors making sure that corresponding sub-vectors have the same size.

• Then, we take the dot product of the corresponding sub-vectors and add all those together.

$$x^Ty = \begin{pmatrix} x_0\\ \hline \\ x_1 \\ \hline \\ ... \\ \hline \\ x_{N-1} \end{pmatrix} = \begin{pmatrix} y_0\\ \hline \\ y_1 \\ \hline \\ ... \\ \hline \\ y_{N-1} \end{pmatrix} \\ = x^T_0y_0 + x^T_1y_1 + ... + x^T_{N-1}y_{N-1} \\ = \sum^{N-1}_{i=0} x^T_iy_i$$

Algorithm: Dot Product

Following details the algorithm to calculate dot product using slicing and dicing:

$$Partition \hspace{1.5mm} x \rightarrow \begin{pmatrix} x_T \\ \hline \\ x_B \end{pmatrix}, y \rightarrow \begin{pmatrix} y_T \\ \hline \\ y_B \end{pmatrix} \\ \hspace{5mm} where \hspace{1.5mm} x_T \hspace{1.5mm} and \hspace{1.5mm} y_T \hspace{1.5mm} have \hspace{1.5mm} 0 \hspace{1.5mm} elements \\ \alpha := 0 \\ while \hspace{1.5mm} m(x_T) < m(x) \hspace{1.5mm} do \\ \hspace{5mm} Repartition \\ \hspace{5mm} \begin{pmatrix} x_T \\ \cdots \\ x_B \end{pmatrix} \rightarrow \begin{pmatrix} x_0 \\ \cdots \\ \chi_1 \\ \hline \\ x_2 \end{pmatrix} , \begin{pmatrix} y_T \\ \cdots \\ y_B \end{pmatrix} \rightarrow \begin{pmatrix} y_0 \\ \cdots \\ \psi_1 \\ \hline \\ y_2 \end{pmatrix} \\ where \hspace{1.5mm} \chi_1 \hspace{1.5mm} has \hspace{1.5mm} 1 \hspace{1.5mm} row, \psi_1 \hspace{1.5mm} has \hspace{1.5mm} 1 \hspace{1.5mm} row \\ \alpha := \chi_1 \times \psi_1 + \alpha \\ Continue \hspace{1.5mm} with \\ \hspace{5mm} \begin{pmatrix} x_T \\ \cdots \\ x_B \end{pmatrix} \leftarrow \begin{pmatrix} x_0 \\ \hline \\ \chi_1 \\ \cdots \\ x_2 \end{pmatrix} , \begin{pmatrix} y_T \\ \cdots \\ y_B \end{pmatrix} \leftarrow \begin{pmatrix} y_0 \\ \hline \\ \psi_1 \\ \cdots \\ y_2 \end{pmatrix} \\ endwhile$$

1-Norm

This is given by the following equation:

$$||v||_1 = |v_1|+|v_2| + ... + |v_n|$$

​p-Norm

This is given the following equation:

​

$$||v||_p = (|v_1|^p+|v_2|^p + ... + |v_n|^p)^{1/p} \\ \forall p \ge1$$

∞​-Norm

∞-Norm is also called max-norm. Following is the given equation for it:

$$||v||_ ∞ = max(|v|_1, |v|_2,..., |v_n|)$$

​Frobenius Norm

Frobenius Norm is calculated for matrices:

$$A_F = (\sum _{i, j} A_{i, j}^2)^{1/2}$$

​Also, $A_f$ and $A_2$ are not the same as denoted by the below equation:

$$||A||_F \neq ||A||_2$$