3.1 Norms
A norm measures the length of a vector.
Definition 3.1 A norm on a vector space \(V\) is a function: \[ \| \cdot \| : V \to \mathbb{R}, \quad \mathbf{x} \mapsto \|\mathbf{x}\| \] satisfying:
- Absolute homogeneity: \(\|\lambda \mathbf{x}\| = |\lambda| \|\mathbf{x}\|\)
- Triangle inequality: \(\|\mathbf{x} + \mathbf{y}\| \le \|\mathbf{x}\| + \|\mathbf{y}\|\)
- Positive definiteness: \(\|\mathbf{x}\| \ge 0\) and \(\|\mathbf{x}\| = 0 \iff \mathbf{x} = 0\)
Geometrically, the triangle inequality means that in any triangle, the sum of any two sides is at least the length of the third.
Example 3.1 An example of a norm is the Manhattan Norm (or \(l_1\) norm): \[ \|\mathbf{x}\|_1 = \sum_{i=1}^n |x_i|. \] One can show that it satisfies all of norm properties given in the definition.
Example 3.2 Another example of a norm is the Euclidean Norm (or \(l_2\) norm): \[ \|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2} = \sqrt{\mathbf{x}^\top \mathbf{x}}. \] Again, this function satisfies all of the properties of a norm.
Example 3.3 The sup norm is another common norm: \[ \|\mathbf{x}\|_{\infty} = \max_{i} \{ x_i \} \] Again, this function satisfies all of the properties of a norm.
The Euclidean norm is the default norm used in the book and these notes.
Exercises
Exercise 3.1
Compute the length of \(\mathbf{x} = \begin{bmatrix}1\\2\\3\end{bmatrix}\) using the Manhattan, Euclidean and \(l_{\infty}\) norms.Exercise 3.2
Compute the length of \(\mathbf{x} = \begin{bmatrix}3\\4\\6\\8\end{bmatrix}\) using the Manhattan, Euclidean and \(l_{\infty}\) norms.Exercise 3.3
Compute the length of \(\mathbf{x} = \begin{bmatrix}-2\\-5\\3\end{bmatrix}\) using the Manhattan, Euclidean and \(l_{\infty}\) normsExercise 3.4
Consider the \(l_{\infty}\) norm: \(\| \mathbf{x} \| = \max_{i} |x_i|\). To prove the triangle inequality holds, we claim that $_{i} |x_i+y_i| $ \(\max_i |x_i | + \max_i |y_i|\). Find an example where this is true as an equality and find an example where this is true as a strict inequality.Exercise 3.8