Talk:Geometric median

Latest comment: 1 year ago by David Eppstein in topic Clarity within the Definition section

DyK

edit
Here's a permalink of that page. --Hirak 99 10:16, 2 April 2007 (UTC)Reply

1-median of a graph or tree

edit

Do we have a Wikipedia article that explains the median of a graph or tree (i.e., a node that minimises the average distance to all other nodes)? A similar concept is the graph center, which minimises the maximum distance, and facility location problems in graphs are also related. But I couldn't find a page that explicitly mentions the concept of a median of a graph. Median graph is something different. 1-center problem has a lot of relevant links, but they are all red.

Here are some references if someone is interested in writing more about medians of graphs:

  • Hakimi, S. L. (1964), "Optimum locations of switching centers and the absolute centers and medians of a graph", Operations Research, 12 (3): 450–459, doi:10.1287/opre.12.3.450, JSTOR 168125.
  • Zelinka, Bohdan (1968), "Medians and peripherians of trees", Archivum Mathematicum, 4 (2): 87–95.
  • Goldman, A. J. (1971), "Optimal center location in simple networks", Transportation Science, 5 (2): 212–221, doi:10.1287/trsc.5.2.212.
  • Alstrup, Stephen; Holm, Jacob; Thorup, Mikkel (2000), "Maintaining center and median in dynamic trees", Proceedings of the SWAT 2000, LNCS, vol. 1851, Springer, pp. 46–56, doi:10.1007/3-540-44985-X_6.
  • Auletta, Vincenzo; Parente, Domenico; Persiano, Giuseppe (1996), "Dynamic and static algorithms for optimal placement of resources in a tree", Theoretical Computer Science, 165 (2): 441–461, doi:10.1016/0304-3975(96)00089-8.

One might also cover more general k-medians; see, e.g.:

I think there are at least enough references to show that the concept is notable enough to have some coverage in Wikipedia. But I am not sure if it is best to create a new article or extend an existing article (e.g., this page). — Miym (talk) 16:27, 11 October 2009 (UTC)Reply

I think median graph is less different than you suggest: trees are median graphs, and median graphs are the graphs in which the 1-median of any three vertices is uniquely determined as meeting the obvious lower bound on average distance. Regardless, I think graph-theoretic medians are too separate a topic to be included in this article. —David Eppstein (talk) 16:46, 11 October 2009 (UTC)Reply
Yes, you are right, but I do not think it makes sense to try to explain the concept of the 1-median of a graph in the median graph article, either. (But if we had an article on graph median, then it would certainly be a good idea to explain the connection between median graphs and graph medians, like you said.) — Miym (talk) 17:43, 11 October 2009 (UTC)Reply
edit

In the passage

Alfred Weber's name is associated with the more general Fermat–Weber problem due to a discussion of the problem in his 1909 book on facility location.

I changed Fermat-Weber problem to Fermat–Weber problem, but the addition of the wikilink was reverted with the edit summary

unexplained change of a self-reference to a reference to a different article

Actually the above-quoted sentence makes it clear the the Fermat-Weber problem is more general than the one in this article, so it's not a self-reference to this article but rather refers to a broader problem about which someone has recently created an article. So there ought to be a link to the relevant article. Duoduoduo (talk) 18:28, 29 July 2013 (UTC)Reply

Okay if I restore the wikilink now? Duoduoduo (talk) 19:48, 29 July 2013 (UTC)Reply
But this is a misreading of this sentence. The phrase "the more general problem" in this particular sentence refers to the geometric median, as a generalization of the Fermat point. Additionally, it is not true that "Fermat–Weber problem" unambiguously refers to the weighted version of the problem; rather, some sources use it to refer to the weighted problem (described in the article Weber problem) while other sources use it to refer to the unweighted problem (described here). I've rewritten the intro to clarify that the term is ambiguous. —David Eppstein (talk) 21:38, 29 July 2013 (UTC)Reply

Robustness of the Geometric Median

edit

The article states in "properties" that the geometric median has a breakdown point of 0.5, i.e., half of all points can be arbitrarily set, which will not affect the geometric median. This is IMHO wrong. Since the geometric median minimizes the distances to all points, dragging one point away from the others affects the geometric median linearly - which is better than for the average, which minimizes the squared distances instead and is thus affected by an outlier much stronger. Still, the assertion about the break point appears to be wrong.

Also, under "Special cases" it is said that the geometric median is equal to the Radon point for 4 coplanar and convex quadrilateral points. This is IMHO wrong as well. Taking one of the four points and moving it away from the others in the direction of its diagonal will affect the geometric median, but it does not affect the Radon point.

Any opinions on that? — Preceding unsigned comment added by Altzheimer (talkcontribs) 11:20, 29 March 2017 (UTC)Reply

The geometric median coincides with the median in 1D, so your example of dragging away a single point is obviously wrong. It doesn't work in higher dimensions either: any minimization of the sum of distances gained by moving closer to the outlier is offset by the increase in moving further away from the other points. — Preceding unsigned comment added by Rslz (talkcontribs) 15:00, 27 January 2020 (UTC)Reply

Clarity within the Definition section

edit

Can someone explain why the formula for the

Geometric Median  

is terminated by underscore 2? If it is important then an explanation is needed. Otherwise it should be removed. Frank M. Jackson (talk) 14:16, 21 February 2018 (UTC)Reply

The _2 means to use the Euclidean distance, i.e. the l2 norm. —David Eppstein (talk) 16:42, 21 February 2018 (UTC)Reply
David is correct, but the rest of the article uses   implicitly as the Euclidian norm, so its explicit use in this case is inconsistent. I think that the definition of the various norms is sufficiently specialised that it would be useful to at least state explicitly what the notation means where it is used, and to adopt a single consistent notation (in this article the reader does not really need any concept more specialised than the standard Euclidian distance).FredV (talk) 07:05, 1 April 2019 (UTC)Reply
@David Eppstein, @Fredvanner, The article starts with talking about the Median as the minimizer of the   norm while the problem is formulated by the   norm. Either should be updated. Royi A (talk) 15:33, 2 December 2023 (UTC)Reply
It minimizes the L1 norm of the vector of distances to the given points. The distances themselves are L2, but that's not the part that we mean when we say it's L1. —David Eppstein (talk) 17:41, 2 December 2023 (UTC)Reply
@David Eppstein, I don't see it the way you do. When it says the median in the context of L1 norm one would expect to find the parameter which minimized the L1 norm of a point from a set of points. In this case it minimizes the Euclidean Distance, not the L1 Distance. Royi A (talk) 19:58, 7 December 2023 (UTC)Reply
There are multiple Euclidean distances from multiple points, distance d1 from point p1, distance d2 from point p2, distance d3 from point p3, etc. What it minimizes is L1(d1,d2,d3,...). This is different from the centroid, which minimizes L2(d1,d2,d3,...), and from the 1-center problem, which minimizes L∞(d1,d2,d3,...). —David Eppstein (talk) 21:08, 7 December 2023 (UTC)Reply
@David Eppstein, I understand what's happening. I just think the semantics used are not the common ones. At least to my knowledge. This problem minimizes the sum of L2 distances. The Centroids minimizes the sum of L2 squared distances. The Median is the minimizer of the sum of L1 distances. Specifically, how would you call  ? Royi A (talk) 08:19, 8 December 2023 (UTC)Reply
You can minimize the sum of distances, the sum of squared distances, or the max distance for any definition you like. You happen to be using a definition of distance that also involves a sum of squares of Cartesian coordinates, but if you were using complex numbers it would just be the sum of   or if you were using polar coordinates you would have some other distance formula. The coordinates and the distance formula are not important. —David Eppstein (talk) 18:35, 8 December 2023 (UTC)Reply
"how would you call  ?" Because the sum of the L1 norm can be split into separate parts for each component, these can be minimised separately resulting in the standard median for each component. The result is called the "marginal median"; as an example, for 2D cartesian coordinates, the x component is the median of the x coordinates, and the y component is the median of the y coordinates.FredV (talk) 12:41, 11 December 2023 (UTC)Reply
The article nowhere talks about minimising the L1 norm. It notes that the Geometric median "is also known as the L1 estimator (after the L1 norm)" The note in parenthesis was added in a recent edit (https://en.wikipedia.org/w/index.php?title=Geometric_median&oldid=1149908007) and is incorrect - the L1 estimator has nothing to do with the L1 norm. The only norm involved in this article is the standard euclidian L2 norm. FredV (talk) 23:01, 9 December 2023 (UTC)Reply
Nonsense. See e.g. DOI:10.1007/s001840050029, first two sentences of abstract: "The center of a univariate data set... can be defined as the point m that minimizes the norm of the vector of distances y ... As the median and the mean are the minimizers of respectively the L1- and the L2-norm of y, they are two alternatives to describe the center of a univariate data set." —David Eppstein (talk) 23:20, 9 December 2023 (UTC)Reply
None of these are references to the L1 Estimator, a concept that had been around for decades, and has absolutely no connection to the L1 norm. The "L"s have entirely different origins; the L1 estimator is one of the class of L-estimators (L being short for "Linear combination of order statistics"); the L1 norm is one of the class of Lp norms, or Lebesgue norms, named after Henri Lebesgue. It should be noted that, apart from this recently-introduced comment in brackets, the remainder of the article makes no reference to the L1 norm - a fairly clear indication that it is not a defining part of the concept. There are  -estimators, which do refer to the L1 norm, but they have nothing to do with this article. If you disagree, please point me at a defining reference of the L1 estimator that makes reference to the L1 norm. If you can't point out such a reference, please restore my (entirely correct) edit.FredV (talk) 10:30, 11 December 2023 (UTC)Reply
DOI:10.1080/03610918308812318: "p = 1 is the optimal value of p for the Laplace distribution and one should use the median or L1 estimator". DOI:10.1109/CVPR.2008.4587747: "L1 estimator, also known as the geometric median". —David Eppstein (talk) 18:12, 11 December 2023 (UTC)Reply
I can't access the first reference, but I note that the abstract refers to "lp estimates" which are entirely different from L-estimates. The second reference is indeed to the L1 (geometric median) estimate, and makes no reference (anywhere in the paper) to the L1 norm. FredV (talk) 13:10, 13 December 2023 (UTC)Reply
We have sources that say that L1 estimators are the same as geometric medians. We have sources that say that geometric medians use the L1 norm of the distance vector. The only reason you might ask for sources that say both of those two things in the same place is because you want to keep arguing, not because you have an actual point to make any more. —David Eppstein (talk) 19:27, 13 December 2023 (UTC)Reply
edit

I find it very confusing that the title is "Geometric median", which immediately sounds like it is related to the geometric mean. Spatial median is a much better name, in my opinion. — Preceding unsigned comment added by 37.44.138.159 (talk) 16:16, 28 March 2019 (UTC)Reply

We cannot use a name that is not the name used by published sources. See WP:NEO. —David Eppstein (talk) 21:10, 7 December 2023 (UTC)Reply
I agree the name is not helpful, but I'm not sure "spatial median" is much better - although it is used. As a generalisation of the 1 dimensional median to n dimensional space, perhaps "generalised median" might be reasonable. But, as noted above, in a reference work like this it is not our job to invent new terminology, just to document the terminology in use. FredV (talk) 23:08, 9 December 2023 (UTC)Reply

Weizfeld's algorithm as fixed point iteration

edit

Computation

edit

Weizfeld's algorithm is a simply a fixed-point iteration to find the stationary point of the gradient. Should this be mentioned? The relationship to IRLS doesn't seem so clear to me. To derive the fixed point iteration scheme, simply set the gradient to zero:

 

Then Weizfeld's algorithm is obviously just the fixed point iteration  .