ℓ1 Norm Distance Function: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - "“" to "“") |
m (Remove links to pages that are actually redirects to this page.) |
||
| Line 1: | Line 1: | ||
An [[ℓ1 Norm Distance Function|ℓ1 norm distance function]] is a [[Minkowski distance function]] with <math>d=1</math> (that represents the [[shortest]] [[distance]] in [[unit step]]s along each [[axis]] between two [[point]]s). | An [[ℓ1 Norm Distance Function|ℓ1 norm distance function]] is a [[Minkowski distance function]] with <math>d=1</math> (that represents the [[shortest]] [[distance]] in [[unit step]]s along each [[axis]] between two [[point]]s). | ||
* <B>AKA:</B> [[Taxicab Geometry]], [[Manhattan/Rectilinear Distance]], <math>\ell_1</math>. | * <B>AKA:</B> [[ℓ1 Norm Distance Function|Taxicab Geometry]], [[Manhattan/Rectilinear Distance]], <math>\ell_1</math>. | ||
* <B>Context</U>:</B> | * <B>Context</U>:</B> | ||
** It can be defined as <math>\|\mathbf{x}\|_1 := \sum_{i=1}^{n} |x_i|.</math> | ** It can be defined as <math>\|\mathbf{x}\|_1 := \sum_{i=1}^{n} |x_i|.</math> | ||
Revision as of 20:45, 23 December 2019
An ℓ1 norm distance function is a Minkowski distance function with [math]\displaystyle{ d=1 }[/math] (that represents the shortest distance in unit steps along each axis between two points).
- AKA: Taxicab Geometry, Manhattan/Rectilinear Distance, [math]\displaystyle{ \ell_1 }[/math].
- Context:
- It can be defined as [math]\displaystyle{ \|\mathbf{x}\|_1 := \sum_{i=1}^{n} |x_i|. }[/math]
- It can be a part of an L1 Norm Metric Space.
- It can be computed by the Sum of the differences in each Dimension.
- It can (often) be an input to L1-Norm Regularization.
- Example(s):
- [math]\displaystyle{ \ell_1 ((1,1),(2,3)) \Rightarrow 3 }[/math].
- Counter-Example(s):
- See: Set Distance Function; Case-Based Learning; Nearest Neighbor, Lp Space, Absolute Difference, Cartesian Coordinate.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/taxicab_geometry Retrieved:2015-11-22.
- 'Taxicab geometry, considered by Hermann Minkowski in 19th century Germany, is a form of geometry in which the usual distance function of metric or Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian coordinates. The taxicab metric is also known as rectilinear distance, L1 distance or [math]\displaystyle{ \ell_1 }[/math] norm (see Lp space), city block distance, Manhattan distance, or Manhattan length, with corresponding variations in the name of the geometry. [1] The latter names allude to the grid layout of most streets on the island of Manhattan, which causes the shortest path a car could take between two intersections in the borough to have length equal to the intersections' distance in taxicab geometry.
2011
- (Craw, 2011c) ⇒ Susan Craw. (2011). “Manhattan Distance.” In: (Sammut & Webb, 2011) p.639
- http://en.wikipedia.org/wiki/L1_norm#Formal_description
- QUOTE: The taxicab distance, [math]\displaystyle{ d_1 }[/math], between two vectors [math]\displaystyle{ \mathbf{p}, \mathbf{q} }[/math] in an n-dimensional real vector space with fixed Cartesian coordinate system, is the sum of the lengths of the projections of the line segment between the points onto the coordinate axes. More formally, [math]\displaystyle{ d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|, }[/math] where [math]\displaystyle{ \mathbf{p}=(p_1,p_2,\dots,p_n)\text{ and }\mathbf{q}=(q_1,q_2,\dots,q_n)\, }[/math] are vectors. For example, in the plane, the taxicab distance between [math]\displaystyle{ (p_1,p_2) }[/math] and [math]\displaystyle{ (q_1,q_2) }[/math] is [math]\displaystyle{ | p_1 - q_1 | + | p_2 - q_2 |. }[/math]
Taxicab distance depends on the rotation of the coordinate system, but does not depend on its reflection about a coordinate axis or its translation. Taxicab geometry satisfies all of Hilbert's axioms (a formalization of Euclidean geometry) except for the side-angle-side axiom, as one can generate two triangles each with two sides and the angle between them the same, and have them not be congruent.
- QUOTE: The taxicab distance, [math]\displaystyle{ d_1 }[/math], between two vectors [math]\displaystyle{ \mathbf{p}, \mathbf{q} }[/math] in an n-dimensional real vector space with fixed Cartesian coordinate system, is the sum of the lengths of the projections of the line segment between the points onto the coordinate axes. More formally, [math]\displaystyle{ d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|, }[/math] where [math]\displaystyle{ \mathbf{p}=(p_1,p_2,\dots,p_n)\text{ and }\mathbf{q}=(q_1,q_2,\dots,q_n)\, }[/math] are vectors. For example, in the plane, the taxicab distance between [math]\displaystyle{ (p_1,p_2) }[/math] and [math]\displaystyle{ (q_1,q_2) }[/math] is [math]\displaystyle{ | p_1 - q_1 | + | p_2 - q_2 |. }[/math]
2010
- http://en.wikipedia.org/wiki/Norm_%28mathematics%29#Taxicab_norm_or_Manhattan_norm
- [math]\displaystyle{ \|\boldsymbol{x}\|_1 := \sum_{i=1}^{n} |x_i|. }[/math]
2009
- (Weisstein, 2009-11-02) ⇒ Eric W. Weisstein. (2009). “L1-Norm." From MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/L1-Norm.html
- A vector norm defined for a vector [math]\displaystyle{ \mathbf{x}=[x_1, x_2, ..., x_n] }[/math], with complex entries by [math]\displaystyle{ |x|_1=\sum_{r=1}^n|x_r| }[/math]. The [math]\displaystyle{ L^1 }[/math]-norm [math]\displaystyle{ |x|_1 }[/math] of a vector [math]\displaystyle{ x }[/math] is ...
2008
- (Friedman et al., 2008) ⇒ Jerome H. Friedman, Trevor Hastie, and Robert Tibshirani. (2008). “Sparse Inverse Covariance Estimation with the Graphical Lasso.” In: Biostatistics, 9(3). doi:10.1093/biostatistics/kxm045.
1990
- (Horn & Johnson, 1990) ⇒ R. A. Horn, and C. R. Johnson. (1990). “Norms for Vectors and Matrices." Ch. 5 in Matrix Analysis. Cambridge University Press.