Norms, distances, and similarity

Introduction

Many methods in machine learning compare observations. A nearest-neighbour rule selects the observation closest to a new point. K-means assigns an observation to the closest centroid. A support vector machine measures the distance between observations and a separating boundary. Kernel methods replace an ordinary comparison by one computed in a larger feature space. These procedures use different objectives, but their basic ingredients are norms, distances, and inner products.

Let \(X\in\mathbb{R}^{n\times p}\) be a data matrix with \(n\) observations in its rows and \(p\) variables in its columns. The \(i\)th row is written \(x_i^\top\), where \(x_i\in\mathbb{R}^p\) is the corresponding column vector. Thus two observations \(x_i\) and \(x_j\) have the same \(p\) coordinates and can be compared coordinate by coordinate. This note defines the relevant comparisons, explains how their units affect them, and collects all pairwise inner products in a Gram matrix.

Length and distance

The Euclidean norm of a vector \(x=(x_1,\ldots,x_p)^\top\in\mathbb{R}^p\) is its length:

\[ \lVert x\rVert_2 =\left(\sum_{k=1}^p x_k^2\right)^{1/2} =\left(x^\top x\right)^{1/2}. \]

The two expressions agree because \(x^\top x=x_1^2+\cdots+x_p^2\). Squaring makes every coordinate contribution non-negative; taking the square root returns the result to the original units. For example, if \(x\) records income in euros and years of education, its Euclidean norm has no useful unit. The calculation combines quantities measured on incomparable scales. This point matters for every distance-based method.

The Euclidean distance between two observations is the length of the displacement from one to the other:

\[ d(x_i,x_j)=\lVert x_i-x_j\rVert_2 =\left(\sum_{k=1}^p(x_{ik}-x_{jk})^2\right)^{1/2}. \]

The difference \(x_i-x_j\) has one entry for each variable. It is zero in coordinate \(k\) precisely when the two observations have the same value of that variable. Squaring prevents positive and negative differences from cancelling. A nearest-neighbour method therefore selects the \(x_j\) with the smallest value of \(d(x_i,x_j)\).

Many objectives use the squared distance instead:

\[ \begin{aligned} d(x_i,x_j)^2 &=(x_i-x_j)^\top(x_i-x_j)\\ &=x_i^\top x_i-x_i^\top x_j-x_j^\top x_i+x_j^\top x_j\\ &=\lVert x_i\rVert_2^2+\lVert x_j\rVert_2^2-2x_i^\top x_j. \end{aligned} \]

The first equality substitutes the definition of the norm. The second distributes the transpose and multiplication over the subtraction. The final equality uses \(x_i^\top x_j=x_j^\top x_i\), since both are the same scalar. Squared distance ranks pairs in exactly the same order as distance because the square function is increasing for non-negative numbers. It avoids a square root, which makes sums of squared distances particularly convenient to minimize.

For example, k-means chooses centroids \(c_1,\ldots,c_K\in\mathbb{R}^p\) and allocates each observation to a centroid. Its usual criterion is the within-cluster sum of squared distances,

\[ \sum_{g=1}^K\ \sum_{i\in C_g}\lVert x_i-c_g\rVert_2^2, \]

where \(C_g\) is the set of observation indices assigned to cluster \(g\). The criterion penalizes a large separation more heavily than two smaller separations whose ordinary distances sum to the same amount.

Angles and cosine similarity

The inner product \(x_i^\top x_j\) also describes whether two vectors point in similar directions. For nonzero vectors, their cosine similarity is

\[ \operatorname{cos}(x_i,x_j) =\frac{x_i^\top x_j}{\lVert x_i\rVert_2\lVert x_j\rVert_2}. \]

The denominator divides out the two lengths. The resulting quantity is the cosine of the angle between the vectors: it is \(1\) for the same direction, \(0\) for perpendicular directions, and \(-1\) for opposite directions. The Cauchy–Schwarz inequality, \(|x_i^\top x_j|\leq\lVert x_i\rVert_2\lVert x_j\rVert_2\), ensures that this ratio lies between \(-1\) and \(1\). It is undefined when either vector is zero, because a zero vector has no direction.

Cosine similarity gives the same result after a positive rescaling of either vector. If \(a>0\), then

\[ \frac{(a x_i)^\top x_j}{\lVert a x_i\rVert_2\lVert x_j\rVert_2} =\frac{a x_i^\top x_j}{a\lVert x_i\rVert_2\lVert x_j\rVert_2} =\operatorname{cos}(x_i,x_j). \]

It is consequently useful when the composition of a vector is of interest but its overall size is not. Distances behave differently: multiplying one observation by \(a\) usually changes its distance to every other observation.

Feature scaling

Distance and inner product depend on the units of the variables. Suppose the first coordinate records income in euros and the second records years of education. A difference of one thousand euros contributes \(1{,}000^2\) to a squared Euclidean distance, whereas a difference of one year contributes \(1\). Without a transformation, income will dominate the comparison simply because it is numerically recorded on a larger scale.

A common transformation standardizes each column. Let \(\bar{x}_k\) be the sample mean of variable \(k\) and let \(s_k>0\) be its sample standard deviation. The standardized value is

\[ z_{ik}=\frac{x_{ik}-\bar{x}_k}{s_k}. \]

Subtracting \(\bar{x}_k\) puts zero at the sample mean. Dividing by \(s_k\) gives every transformed column standard deviation one. Euclidean distances between rows of the standardized matrix \(Z\) compare differences in units of each variable’s own standard deviation. This gives variables equal variance weight, not necessarily equal substantive importance. Scaling should therefore follow the measurement and the question: a meaningful common unit may make unscaled distances preferable, while a variable known to be noisier may warrant less rather than equal weight.

Pairwise comparisons and Gram matrices

The \(n\times n\) matrix of all row inner products is the Gram matrix:

\[ G=XX^\top, \qquad G_{ij}=x_i^\top x_j. \]

The dimensions follow directly: \(X\) is \(n\times p\) and \(X^\top\) is \(p\times n\), so \(G\) is \(n\times n\). Its \((i,j)\) entry is the dot product of row \(i\) and row \(j\). The matrix is symmetric because \(G_{ij}=x_i^\top x_j=x_j^\top x_i=G_{ji}\).

The diagonal gives squared row lengths, \(G_{ii}=\lVert x_i\rVert_2^2\). Combining this diagonal with the preceding expansion gives every pairwise squared distance without separately subtracting each pair:

\[ D_{ij}^2=G_{ii}+G_{jj}-2G_{ij}. \]

This representation is useful when \(n\) is moderate and many pairwise comparisons are required. It also shows that distance and similarity are closely related, although they answer different questions. A large inner product can result from two long vectors even when their angle is not especially small; cosine similarity removes that effect by normalizing the diagonal entries.

Gram matrices also have a property required by kernel methods. For every \(a=(a_1,\ldots,a_n)^\top\in\mathbb{R}^n\),

\[ a^\top G a =a^\top XX^\top a =(X^\top a)^\top(X^\top a) =\lVert X^\top a\rVert_2^2\geq0. \]

Thus \(G\) is positive semidefinite: every quadratic form \(a^\top G a\) is non-negative. A kernel replaces \(x_i^\top x_j\) by \(k(x_i,x_j)=\phi(x_i)^\top\phi(x_j)\), the inner product after a feature map \(\phi\). Its kernel matrix \(K\), with entries \(K_{ij}=k(x_i,x_j)\), is a Gram matrix in that feature space and is consequently positive semidefinite as well.

Support vector machines use this fact to construct nonlinear separating boundaries while working only with \(K_{ij}\), rather than with the coordinates of \(\phi(x_i)\). In the ordinary linear case, the distance from a point to a separating hyperplane is inversely proportional to the norm of its normal vector. The margin is therefore a geometric distance, and the inner products that form a Gram or kernel matrix make its computation possible from pairwise comparisons. The next notes make the projection and hyperplane calculations explicit.

Conclusion

Norms turn vectors into lengths, distances compare their locations, and inner products compare their alignment. Their definitions make the role of measurement units explicit: rescaling a variable changes Euclidean comparisons, while standardisation instead measures each coordinate in standard-deviation units. The Gram matrix collects all pairwise inner products and, together with its diagonal, determines every squared Euclidean distance. Its positive-semidefinite structure also supplies the condition that allows kernels to represent inner products in a feature space.