2.2 Norms
In many practical problems, we may be interested in measuring the objects in a set, either as an objective function or as a way of analyzing solutions. A norm is a geometric concept that allows us to make this measurement. The most common norm is the Euclidean distance given by (Equation 2.12)
However, this function is not the only way to measure a distance. In general, we can define a norm as a function ‖⋅‖:Ω→R that fulfills the following conditions:
The first two conditions indicate that a norm must return a positive value, except when the input is the vector 0→ The third condition indicates that it is scalable; for example, the norm must be twice the original vector’s norm if we multiply all the vector entries by 2. The last condition, known as the triangle inequality, is a generalization of the triangles’ property (therein lies its name). The sum of any two sides’ lengths is greater (or equal) to the remaining side’s length. This property is intuitive for the Euclidean norm, but surprisingly it is general for many other functions, such as (Equation 2.17):
This function is known as p-norm, where p ≥ 1. Three of the most common examples of p-norms in Rnn have a well-defined representation, as presented below:
The Euclidean distance is equivalent to a 2-norm whereas 1-norm, also known as Manhattan distance, consists in measuring the distance along axes at right angles (see Figure 2.2b), and infinity-norm or uniform norm, takes the maximum distance along axes as shown in Figure 2.2c). In general, ‖x‖1 ≤ ‖x‖2 ≤ ‖x‖∞. All of these norms are suitable ways to measure vectors in the space.
Figure 2.2 Three ways to measure the vector
We can use a norm to define a set given by all the points at a distance less or equal to a given value r, as given in (Equation 2.21).
This set is known as a ball of radius r. Figure 2.3 shows the shape of unit balls (i.e., balls of radius 1), generated by each of the three previously mentioned norms.