The projection median as a weighted average

Abstract

The projection median of a set $P$ of $n$ points in $\mathbb{R}^d$ is a robust geometric generalization of the notion of univariate median to higher dimensions. In its original definition, the projection median is expressed as a normalized integral of the medians of the projections of $P$ onto all lines through the origin. We introduce a new definition in which the projection median is expressed as a weighted mean of $P$, and show the equivalence of the two definitions. In addition to providing a definition whose form is more consistent with those of traditional statistical estimators of location, this new definition for the projection median allows many of its geometric properties to be established more easily, as well as enabling new randomized algorithms that compute approximations of the projection median with increased accuracy and efficiency, reducing computation time from $O(n^{d+\epsilon})$ to $O(mnd)$, where $m$ denotes the number of random projections sampled. Selecting $m \in \Theta(\epsilon^{-2} d^2 \log n)$ or $m \in \Theta(\min ( d + \epsilon^{-2} \log n, \epsilon^{-2} n))$, suffices for our algorithms to return a point within relative distance $\epsilon$ of the true projection median with high probability, resulting in running times $O(d^3 n \log n)$ and $O(\min(d^2 n, d n^2))$ respectively, for any fixed $\epsilon$.

Author Biographies

Stephane Durocher, University of Manitoba
Associate Professor, Department of Computer Science
Alexandre Leblanc, Department of Statistics University of Manitoba
Associate ProfessorDepartment of Statistics
Matthew Skala, IT University of Copenhagen
Postdoctoral FellowIT University of Copenhagen
Published
2017-05-01
How to Cite
Durocher, S., Leblanc, A., & Skala, M. (2017). The projection median as a weighted average. Journal of Computational Geometry, 8(1), 78–104. https://doi.org/10.20382/jocg.v8i1a5
Section
Articles

Most read articles by the same author(s)