# Norm bijections

Back to PastelMath

A norm bijection is the composition of a norm and an increasing bijection.

## Theory

### Norm bijection

Let $| x | : {\mathbb{R}}^{n} \to {\mathbb{R}}^{+}$ be a norm and $f : {\mathbb{R}}^{+} \to {\mathbb{R}}^{+}$ an increasing bijection. A norm bijection is a function defined by $\left\langlex\right\rangle : {\mathbb{R}}^{n} \to {\mathbb{R}}^{+} : \left\langlex\right\rangle = f \left(| x |\right)$.

### Restricted norm bijection

A restricted norm bijection is any function $g : {\mathbb{R}}^{n} \to {\mathbb{R}}^{+}$, which can expressed in the form $g \left(x\right) = {\oplus}_{i = 1}^{n} f \left(| {x}_{i} |\right)$ with the functions $f$ and $\oplus$ defined below (redundant conditions in parentheses).

$f : {\mathbb{R}}^{+} \to {\mathbb{R}}^{+}$, such that:

• $f$ is continuous

• $f$ is increasing

• ($f$ is invertible)

• $\setminus \forall a \in {\mathbb{R}}^{+} : f \left(a x\right) = f \left(a\right) f \left(x\right)$

• $\left(\setminus \forall a \in {\mathbb{R}}^{+} : {f}^{-} 1 \left(a x\right) = {f}^{-} 1 \left(a\right) {f}^{-} 1 \left(x\right)\right)$

$\oplus : {\mathbb{R}}^{{+}^{2}} \to {\mathbb{R}}^{+}$, such that

• $\setminus \forall x , y , z : \left(x \oplus y\right) \oplus z = x \oplus \left(y \oplus z\right)$

• $\setminus \forall x , y : x \oplus y = y \oplus x$

• $\setminus \forall x : x \oplus 0 = x$

• $\setminus \forall a , x , y \in {\mathbb{R}}^{+} : \left(a x\right) \oplus \left(a y\right) = a \left(x \oplus y\right)$

• $\setminus \forall x , y : x \le x \oplus y$

• $\left(\setminus \forall x , y : y \le x \oplus y\right)$

In particular, ${f}^{-} 1 o g$ is a norm and $f$ is the increasing bijection in the definition of norm bijection.

## Practice

The motivation for the definition of a norm bijection is efficiency. The efficiency follows from the observation that the norm value is rarely of interest itself. Rather, it is the ordering of norms that is of interest. In particular, the p-norms (also called Minkowski norms) compute a $p$:th root for each evaluation, which is a rather slow operation. However, if all you have is an inequality $| x {|}^{p} < | y {|}^{p}$, then this is equivalent to $| x | < | y |$ and you can avoid the root computation.

A norm bijection allows you, in particular, to move between the norm bijection value and the norm value. However, we have noticed that to really produce efficient code with norm bijections, it is essential to restrict them further. Therefore, when talking about norm bijections, in Pastel this always means a restricted norm bijection as defined above. Pastel implements the following restricted norm bijections:

### Manhattan / 1

$\left\langlex\right\rangle = \setminus {\sum}_{i = 1}^{n} | {x}_{i} |$

$\oplus \left(x , y\right) = x + y$

$f \left(x\right) = x$

### Euclidean / 2

$\left\langlex\right\rangle = \setminus {\sum}_{i = 1}^{n} {x}_{i}^{2}$

$\oplus \left(x , y\right) = x + y$

$f \left(x\right) = {x}^{2}$

### Minkowski / P

$\left\langlex\right\rangle = \setminus {\sum}_{i = 1}^{n} | {x}_{i} {|}^{p}$

$\oplus \left(x , y\right) = x + y$

$f \left(x\right) = {x}^{p}$

### Maximum / Infinity

$\left\langlex\right\rangle = {\textrm{\max}}_{i = 1}^{n} | {x}_{i} |$

$\oplus \left(x , y\right) = \textrm{\max} \left(x , y\right)$

$f \left(x\right) = x$

## Files

### Euclidean_NormBijection class

A norm bijection of the Euclidean norm

### Manhattan_NormBijection class

A norm bijection of the Manhattan norm

### Maximum_NormBijection class

A norm bijection of the maximum norm

### Minkowski_NormBijection class

A norm bijection of the Minkowski norm (p-norm)