Norms and Spaces

Refer 3b1b
Metric spaces, normed vector spaces and inner product spaces are needed to anaylse some machine learning algorithms in-depth.
Metrics are generalisation of the notion of distance, norms are a generealisation of the notion of length and inner products are a generalisation of the dot product.

Metric space

Generalisation of the notion of distance from Euclidean space.
A metric on a set S is a function
such that for all

1. (non negative distance, distance from a point to itself is zero)
2. (distance should be the same, symmetry)
3. (triangle inequality)
   ex. Take and define ; then forms a metric space.
   For a metric, is interpreted as the distance between x and y.

Norm

A norm on a real vector space (in context of machine learning) is a function such that for all and :

3. 
   Here is called a normed vector space.

Every normed space is a metric space, but the converse is not true.

Some special norms; remember that is a vector :

1. The Manhattan norm on is defined for as: where is the absolute value. It’s also called the norm.
2. The Euclidean norm of is defined as: it computes the Euclidean distance of from the origin. It’s also called the norm.
3. The norm is calculated as: it’s also called the p-norm.
4. The “max norm” is calculated as:
5. The "" norm is defined as the number of non zero elements of . Strictly speaking, it’s not a norm because it doesn’t satisfy the second property, but it’s still very useful in compression sensing.
   • ex. then as there are five non zero elements in the vector.

All norms are part of the convex set.

Convex function: A function is said to be convex if for , we have:

where .
In plain English, a function is said to be convex if the line segment between any two distinct points on the graph of the function lies above or on graph of the function between the two points.

Convex set: A set is said to be convex if the line joining any two points of the set lies entirely in the set .
A convex set:

A non-convex set (note how the line joining the two points does not lie entirely in the set):

All norms () are a part of a convex set.

Inner product spaces

An inner product on a real vector space V is a function:

satisfying for all and

3. 
   A vector space together with an inner product is called an inner product space.
   ex. Let . Now consider

here it’s just the definition of the dot product, a particular type of inner product.

ex. consider . If we define

then is an inner product but different from the dot product.

NOTE

The pair is called an inner product space or (real) vector space with inner product. If we use the dot product instead, is called a Euclidean vector space.

The particular type of inner product, the scalar/dot product in is given by
Any inner product induces a norm in a natural way, such that we can compute the lengths of vectors using the inner product. The Manhattan norm is an example of a norm without a corresponding inner product.

For an inner product vector space the induced norm satisfies the Cauchy-Schwarz inequality
We have already seen what the metric means, but in an inner product space,

is called the distance between and if x and y are two vectors in V. If we use the dot product as the inner product, this is called the Euclidean distance.

Angles

When we remove the absolute value bars from the Cauchy-Schwarz inequality, we get the equation

Dividing this we get

There exists a unique with
And the number is the angle between the vectors.
We already know that if the inner product is zero, the angle between them is 90 degrees.