Norms and Distances

A norm measures the size of a vector or matrix; a distance measures separation between two objects. These choices decide what “near”, “small error”, and “best approximation” mean in optimization, clustering, and low-rank approximation.

Defining math

A norm $\Vert x\Vert$ is nonnegative, homogeneous, and obeys the triangle inequality:

$$\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert .$$

Common vector norms are

$$\Vert x{\Vert }_1=\sum _i|x_i|,\Vert x{\Vert }_2=\sqrt{\sum _i{x}_i^2},\Vert x{\Vert }_{\infty }=\underset{i}{\max }|x_i|.$$

A distance is often induced by a norm, $d(x,y)=\Vert x-y\Vert$. The Euclidean norm is tied to orthogonality; $L_1$ often encourages sparse errors or coefficients; matrix Frobenius norm is the squared-entry analogue used in singular value decomposition.

Worked example

The same vector has different sizes under different norms. For $x=(3,4)$,

$$\Vert x{\Vert }_1=|3|+|4|=7,\Vert x{\Vert }_2=\sqrt{3^2+4^2}=5,\Vert x{\Vert }_{\infty }=\max (3,4)=4.$$

The Euclidean distance to $y=(1,1)$ is $\Vert x-y{\Vert }_2=\Vert (2,3){\Vert }_2=\sqrt{13}\approx 3.606$. The triangle inequality holds with a little room to spare:

$$\Vert x{\Vert }_2+\Vert y{\Vert }_2=5+\sqrt{2}\approx 6.414\ge \Vert x+y{\Vert }_2=\Vert (4,5){\Vert }_2=\sqrt{41}\approx 6.403,$$

a gap of about $0.011$.

Caveats

Distances can be dominated by scale, irrelevant dimensions, or sparse high-dimensional effects. A model optimized with one norm may behave poorly under the metric users care about, so connect the norm to the task before tuning gradient descent.

References

• MIT OpenCourseWare: 18.06 Linear Algebra

Nav

Section — Mathematical Foundations

← Orthogonality Eigenvalues and Eigenvectors →