Minkowski distance

Vector distance using pth powers

Not to be confused with the pseudo-Euclidean metric of the Minkowski space.

The Minkowski distance or Minkowski metric is a metric in a normed vector space which can be considered as a generalization of both the Euclidean distance and the Manhattan distance. It is named after the Polish mathematician Hermann Minkowski.

Comparison of Chebyshev, Euclidean and taxicab/Manhattan distances for the hypotenuse of a 3-4-5 triangle on a chessboard (represented by a king, an ant, and a wazir). The wazir moves like a rook but only one square at a time.

## Definition

[edit]

The Minkowski distance of order  p {\displaystyle p} (where  p {\displaystyle p} is an integer) between two points  X = ( x 1 , x 2 , … , x n )  and  Y = ( y 1 , y 2 , … , y n ) ∈ R n {\displaystyle X=(x_{1},x_{2},\ldots ,x_{n}){\text{ and }}Y=(y_{1},y_{2},\ldots ,y_{n})\in \mathbb {R} ^{n}} is defined as:  D ( X , Y ) = ( ∑ i = 1 n | x i − y i | p ) 1 p . {\displaystyle D\left(X,Y\right)={\biggl (}\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}{\biggr )}^{\frac {1}{p}}.}

For  p ≥ 1 , {\displaystyle p\geq 1,} the Minkowski distance is a metric as a result of the Minkowski inequality.[1] When  p < 1 , {\displaystyle p<1,} the distance between  ( 0 , 0 ) {\displaystyle (0,0)} and  ( 1 , 1 ) {\displaystyle (1,1)} is  2 1 / p > 2 , {\displaystyle 2^{1/p}>2,} but the point  ( 0 , 1 ) {\displaystyle (0,1)} is at a distance  1 {\displaystyle 1} from both of these points. Since this violates the triangle inequality, for  p < 1 {\displaystyle p<1} it is not a metric. However, a metric can be obtained for these values by simply removing the exponent of  1 / p . {\displaystyle 1/p.} The resulting metric is also an F-norm.

Minkowski distance is typically used with  p {\displaystyle p} being 1 or 2, which correspond to the Manhattan distance and the Euclidean distance, respectively.[2] In the limiting case of  p {\displaystyle p} reaching infinity, we obtain the Chebyshev distance:  lim p → ∞ ( ∑ i = 1 n | x i − y i | p ) 1 p = max i = 1 n | x i − y i | . {\displaystyle \lim _{p\to \infty }{{\biggl (}\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}{\biggr )}^{\frac {1}{p}}}=\max _{i=1}^{n}|x_{i}-y_{i}|.}

Similarly, for  p {\displaystyle p} reaching negative infinity, we have:  lim p → − ∞ ( ∑ i = 1 n | x i − y i | p ) 1 p = min i = 1 n | x i − y i | . {\displaystyle \lim _{p\to -\infty }{{\biggl (}\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}{\biggr )}^{\frac {1}{p}}}=\min _{i=1}^{n}|x_{i}-y_{i}|.}

The Minkowski distance can also be viewed as a multiple of the power mean of the component-wise differences between  P {\displaystyle P} and  Q . {\displaystyle Q.}

The following figure shows unit circles (the level set of the distance function where all points are at the unit distance from the center) with various values of  p {\displaystyle p} :

## Applications

[edit]

The Minkowski metric is very useful in the field of machine learning and AI. Many popular machine learning algorithms use specific distance metrics such as the aforementioned to compare the similarity of two data points. Depending on the nature of the data being analyzed, various metrics can be used. The Minkowski metric is most useful for numerical datasets where one wants to determine the similarity of size between multiple datapoint vectors.

## See also

[edit]

* Generalized mean – N-th root of the arithmetic mean of the given numbers raised to the power n
* L p {\displaystyle L^{p}} space – Function spaces generalizing finite-dimensional p norm spaces
* Norm (mathematics) – Length in a vector space
* p {\displaystyle p} -norm – Function spaces generalizing finite-dimensional p norm spacesPages displaying short descriptions of redirect targets

## References

[edit]

1. ^ Şuhubi, Erdoğan S. (2003), "Chapter V: Metric Spaces", Functional Analysis, Springer Netherlands, pp. 261–356, doi:10.1007/978-94-017-0141-9_5, ISBN 9789401701419
2. ^ Zezula, Pavel; Amato, Giuseppe; Dohnal, Vlastislav; Batko, Michal (2006), "Chapter 1, Foundations of Metric Space Searching, Section 3.1, Minkowski Distances", Similarity Search: The Metric Space Approach, Advances in Database Systems, Springer, p. 10, doi:10.1007/0-387-29151-2, ISBN 9780387291512

## External links

[edit]

* Unit Balls for Different p-Norms in 2D and 3D at wolfram.com
* Unit-Norm Vectors under Different p-Norms at wolfram.com
* Simple IEEE 754 implementation in C++
* NPM JavaScript Package/Module

* v
* t
* e

Lp spaces

Basic concepts|

* Banach & Hilbert spaces
* Lp spaces
* Measure
* Lebesgue
* Measure space
* Measurable space/function
* Minkowski distance
* Sequence spaces

L1 spaces|

* Integrable function
* Lebesgue integration
* Taxicab geometry

L2 spaces|

* Bessel's
* Cauchy–Schwarz
* Euclidean distance
* Hilbert space
* Parseval's identity
* Polarization identity
* Pythagorean theorem
* Square-integrable function

L ∞ {\displaystyle L^{\infty }} spaces|

* Bounded function
* Chebyshev distance
* Infimum and supremum
* Essential
* Uniform norm

Maps|

* Almost everywhere
* Convergence almost everywhere
* Convergence in measure
* Function space
* Integral transform
* Locally integrable function
* Measurable function
* Symmetric decreasing rearrangement

Inequalities|

* Babenko–Beckner
* Chebyshev's
* Clarkson's
* Hanner's
* Hausdorff–Young
* Hölder's
* Markov's
* Minkowski
* Young's convolution

Results|

* Marcinkiewicz interpolation theorem
* Plancherel theorem
* Riemann–Lebesgue
* Riesz–Fischer theorem
* Riesz–Thorin theorem

| For Lebesgue measure|

* Isoperimetric inequality
* Brunn–Minkowski theorem
* Milman's reverse
* Minkowski–Steiner formula
* Prékopa–Leindler inequality
* Vitale's random Brunn–Minkowski inequality

|

Applications & related|

* Bochner space
* Fourier analysis
* Lorentz space
* Probability theory
* Quasinorm
* Real analysis
* Sobolev space
* *-algebra
* C*-algebra
* Von Neumann

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template