Intuitive norms are Euclidean
Shay Moran, Alexander Shlimovich, Amir Yehudayoff · 2025
Read Intuitive norms are Euclidean by Shay Moran, Alexander Shlimovich, Amir Yehudayoff (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-02561.txt.
Introduction
Shay Moran, Alexander Shlimovich, and Amir Yehudayoff characterize the intuitive norms in a 2025 math paper. They call a norm intuitive when a geometric median of any finite point set, measured in that norm, always lands inside the set's convex hull. The hull is the smallest convex region holding the points. The paper determines exactly which norms on finite-dimensional space have this property, settling the class completely. The catalog title carries grant-acknowledgment text; the work's own title is the short one used here.
Catalog record
| CREATOR | Shay Moran, Alexander Shlimovich, Amir Yehudayoff |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-02561
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Intuitive norms are Euclidean Thanks: A.Y. is supported by a DNRF chair grant, and partially supported by BARC Shay Moran, Alexander Shlimovich, Amir Yehudayoff Abstract . We call a norm on ℝ n \mathbb{R}^{n} intuitive if for every points p 1 , … , p m p_{1},\ldots,p_{m} in ℝ n \mathbb{R}^{n} , one of the geometric medians of the points over the norm is in their convex hull. We characterize all intuitive norms. 1. Introduction The starting point of our work is the intuitive statement that the geometric median of a set of points is in their convex hull. The geometric median of p_{1},\ldots,p_{m}\in\mathbb{R}^{n} is the minimizer of the convex function \mathbb{R}^{n}\ni\xi\mapsto\sum_{i\in[m]}\|\xi-p_{i}\|_{2}; it is unique when the points are not collinear (see e.g. [ 3 ] and references within). The geometric median is also known as the Fermat-Weber point, the Torricelli point, Haldane’s median, and by several other names. It is important in statistics because its breakdown point in 50\% ; i.e., we need to change at least half of the mass to send the geometric median to infinity [ 2 ] . It is important in facility location because it captures minimizing the cost of transportation. Consequently, it has a very rich history and there are many related algorithmic results (see e.g. [ 1 ] and the long list of references within). The geometric median makes sense over general norms. Let K\subset\mathbb{R}^{n} be a symmetric convex body (i.e., compact with non-empty interior so that K=-K ), and denote by \|\cdot\|_{K} the norm defined by K : \|\xi\|_{K}=\inf\{t>0:\xi\in tK\}. We also allow weights for the points. For a finite set of points P\subset\mathbb{R}^{n} , denote by \Delta_{P} the collection of probability distributions on P . The geometric median \mathsf{GM}_{K}(W) of W over K is the set of minimizers of the convex function F_{K,W}(\xi)=\sum_{p\in P}W(p)\|\xi-p\|_{K}. The geometric median is always non-empty and convex. If K is strictly convex and the points in P are not collinear then it is a unique point [ 3 ] . It is intuitively obvious that the geometric median is in the convex hull \mathsf{conv}(P) because norms are convex. Let us say that K is intuitive if there always exists a geometric median is in the convex hull of the data points; for every W\in\Delta_{P} , \mathsf{GM}_{K}(W)\cap\mathsf{conv}(P)\neq\emptyset. Let us start by describing some intuitive norms. Observation . All centered \ell_{2} balls are intuitive. Proof. If \xi is outside \mathsf{conv}(P) then there is a separating hyperplane with a normal \ell_{2} unit vector u so that \langle u,\xi-p\rangle>0 for all p\in P . For every p\in P and t\in\mathbb{R} , \|\xi-tu-p\|_{2}=\sqrt{\|\xi-p\|_{2}^{2}-2t\langle u,\xi-p\rangle+t^{2}}. Now, if t>0 is small enough then the point \xi-tu has a smaller F_{\ell_{2},W} value than \xi . ∎ We can obtain more intuitive norms, because being intuitive is invariant under linear transformations. Observation . If K\subset\mathbb{R}^{n} is intuitive and T:\mathbb{R}^{n}\to\mathbb{R}^{n} is an invertible linear map, then TK is intuitive. Proof. For every \xi , \displaystyle F_{TK,W}(\xi) \displaystyle=\sum_{p\in P}W(p)\|\xi-p\|_{TK} \displaystyle=\sum_{p\in P}W(p)\|T^{-1}(\xi-p)\|_{K} \displaystyle=F_{K,W^{\prime}}(T^{-1}\xi), for P^{\prime}=T^{-1}P and W^{\prime}=W\circ T . Because K is intuitive, there is a minimizer x of F_{K,W^{\prime}} in \mathsf{conv}(P^{\prime}) . The point \xi=Tx is a minimizer of F_{TK,W} and \xi\in\mathsf{conv}(P) . ∎ Because linear maps of balls are ellipsoids, we can conclude that all Euclidean norms are intuitive (a.k.a. finite dimensional Hilbert spaces). Corollary . All centered ellipsoids are intuitive. The first theorem we prove is that in the plane all norms are intuitive. Theorem 1 . Every symmetric convex body K\subset\mathbb{R}^{2} is intuitive. What about higher dimensions? Our main result is that in higher dimensions, the only intuitive norms are Euclidean. Theorem 2 . Let K\subset\mathbb{R}^{n} be a symmetric convex body for n\geq 3 . Then, K is intuitive \iff K is an ellipsoid. Theorem 2 shows, in particular, that polytopes are never intuitive (for n\geq 3 ). More generally, that if a norm is intuitive then it must be strictly convex and smooth. It is also natural to consider a stronger definition where instead of “there is a geometric median in the convex hull” we require “every geometric median is in the convex hull”. Instead of \mathsf{GM}_{K}(W)\cap\mathsf{conv}(P)\neq\emptyset , we require \mathsf{GM}_{K}(W)\subseteq\mathsf{conv}(P) . This stronger definition never holds when the boundary of K has a flat part even just in the case that P comprises two points. In particular, this stronger definition never holds for polytopes. The reason is that if the boundary of K contains a flat part F then for every p in the interior of F , the geometric median of P=\{0,p\} contains an open set but \mathsf{conv}(P) is one-dimensional. For example, in the plane the geometric median of (0,1) and (1,0) over the \ell_{1} norm is the entire unit square. Because ellipsoids are strictly convex, however, Theorem 2 shows that in dimensions at least three, the two definitions are equivalent. We can reduce the case n>3 in Theorem 2 to the case n=3 as follows. A section of K is a set of the form K\cap H for a linear space H\subset\mathbb{R}^{n} . The dimension of the section is the dimension of H . We think of the section as a subset of the Euclidean space H . Observation . If K is intuitive then every section of K is intuitive. Proof. Assume K is intuitive. If H is a subspace and \xi\in H then \|\xi\|_{K\cap H}=\|\xi\|_{K} . So, if P\subset H and W\in\Delta_{P} then \emptyset\neq\mathsf{GM}_{K}(W)\cap\mathsf{conv}(P)=\mathsf{GM}_{K\cap H}(W)\cap\mathsf{conv}(P).\qed There are many known characterizations of ellipsoids (see e.g. [ 5 , 7 ] ). The following well-known lemma provides one such characterization (a concrete reference is Theorem (3.1) in [ 5 ] ). In Section 4 we mention a second characterization that we shall use. The lemma can, e.g., be proved by Jordan and von Neumann’s result that K is an ellipsoid iff the parallelogram law \|x+y\|_{K}^{2}+\|x-y\|_{K}^{2}=\|x\|_{K}^{2}+\|y\|_{K}^{2} hold for all x,y\in\mathbb{R}^{n} , which is a two-dimensional condition. Lemma . A convex body K\subset\mathbb{R}^{n} is an ellipsoid iff every 3 -dimensional section of K is an ellipsoid. The observation and the lemma imply that in order to prove Theorem 2 it suffices to prove the following. Theorem 3 . If K\subset\mathbb{R}^{3} is intuitive then K is an ellipsoid. Remark . The proof of the theorem works for a more general class of norms than “intuitive norms”. It works for all symmetric convex bodies K so that for all sets P of three points and W\in\Delta_{P} , we have that \mathsf{GM}_{K}(W)\cap A_{P}\neq\emptyset , where A_{P} is the affine span of P . All convex bodies that satisfy this condition are ellipsoids. 2. Sub-gradients To argue about general norms, we need the language of sub-gradients. In this section, we recall what are sub-gradients and describe some of their basic properties. The sub-gradient of f:\mathbb{R}^{n}\to\mathbb{R} at \xi\in\mathbb{R}^{n} is \partial f(\xi)=\{g\in\mathbb{R}^{n}:\forall y\in\mathbb{R}^{n}\ f(y)\geq f(\xi)+\langle g,y-\xi\rangle\}. If f is convex then \partial f(\xi) is non-empty and convex for all \xi . If f is also differentiable at \xi then the sub-gradient is unique (and is equal to the gradient). The sum property says that if f_{1},f_{2}:\mathbb{R}^{n}\to\mathbb{R} are convex, then for all \xi\in\mathbb{R}^{n} , \partial(f_{1}+f_{2})(\xi)=\partial f_{1}(\xi)+\partial f_{2}(\xi), where A+B=\{a+b:a\in A,b\in B\} is Minkowski sum. For p\in\mathbb{R}^{n} , we use the notation F_{K,p}(\xi)=\|\xi-p\|_{K}. When K is clear from the