Geometric median in nearly linear time

DOI10.1145/2897518.2897647zbMATH Open1377.68267arXiv1606.05225OpenAlexW2410099853MaRDI QIDQ5361815FDOQ5361815

Aaron Sidford, Michael B. Cohen, Gary L. Miller, Yin Tat Lee, Jakub W. Pachocki

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: In this paper we provide faster algorithms for solving the geometric median problem: given $n$ points in $mathbb{R}^d$ compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite an abundance of research the previous fastest algorithms for computing a $(1+epsilon)$-approximate geometric median were $O(dcdot{n}^{4/3}epsilo{n}^{-8/3})$ by Chin et. al, $ildeO(dexpepsilo{n}^{-4}logepsilo{n}^{-1})$ by Badoiu et. al, $O(nd+mathrmpoly(d,epsilo{n}^{-1})$ by Feldman and Langberg, and $O((nd{)}^{O(1)}logfrac1epsilon)$ by Parrilo and Sturmfels and Xue and Ye. In this paper we show how to compute a $(1+epsilon)$-approximate geometric median in time $O(ndlo{g}^{3}frac1epsilon)$ and $O(depsilo{n}^{-2})$. While our $O(depsilo{n}^{-2})$ is a fairly straightforward application of stochastic subgradient descent, our $O(ndlo{g}^{3}frac1epsilon)$ time algorithm is a novel long step interior point method. To achieve this running time we start with a simple $O((nd{)}^{O(1)}logfrac1epsilon)$ time interior point method and show how to improve it, ultimately building an algorithm that is quite non-standard from the perspective of interior point literature. Our result is one of very few cases we are aware of outperforming traditional interior point theory and the only we are aware of using interior point methods to obtain a nearly linear time algorithm for a canonical optimization problem that traditionally requires superlinear time. We hope our work leads to further improvements in this line of research.

Full work available at URL: https://arxiv.org/abs/1606.05225

Recommendations

• Optimal algorithms for geometric centers and depth
• Approximation algorithms for geometric median problems
• Faster algorithms for the geometric transportation problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• The projection median as a weighted average

zbMATH Keywords

geometric medianinterior-point methodsstochastic gradient descent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (19)

• Finding the Median (Obliviously) with Bounded Space
• Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
• Sub-Gaussian estimators of the mean of a random vector
• Approximation and complexity of the capacitated geometric median problem
• Mean estimation with sub-Gaussian rates in polynomial time
• The geometric median and applications to robust mean estimation
• Approximation algorithms for geometric median problems
• Active-learning a convex body in low dimensions
• On Geometric Prototype and Applications
• Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
• A causal filter of gradient information for enhanced robustness and resilience in distributed convex optimization
• Mean estimation in high dimension
• Mean estimation and regression under heavy-tailed distributions: A survey
• Hardness Results for Structured Linear Systems
• Robust Estimators in High-Dimensions Without the Computational Intractability
• An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions
• Minimizing the size of the uncertainty regions for centers of moving entities
• Medians in median graphs and their cube complexes in linear time
• Computing kemeny rankings from \(d\)-Euclidean preferences

This page was built for publication: Geometric median in nearly linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361815)