Tukey depth intuition

Question

In a bagplot, the inner polygon, called the bag, is constructed using the Tukey depth. What is the intuition of Tukey depth and how is it calculated? A simple two-dimensional example with ten to twenty data points may be helpful. Further, how often is is Tukey depth utilised and what alternative methods are similar?

Answer 1

Bagplot

A bagplot is a method in robust statistics for visualizing two- or three-dimensional statistical data, analogous to the one-dimensional box plot.

---

Construction of a Bagplot

The bagplot consists of three nested polygons, called the "bag", the "fence", and the "loop".

• The inner polygon, called the bag, is constructed on the basis of Tukey depth, the smallest number of observations that can be contained by a half-plane that also contains a given point. It contains at most $50\%$ of the data points. For more refer to Functional bagplot

An asterisk symbol (*) near the center of the graph is used to mark the depth median, the point with the highest possible Tukey depth.

• The outermost of the three polygons, called the fence is not drawn as part of the bagplot but is used to construct it. It is formed by inflating the bag by a certain factor (usually 3). Observations outside the fence are flagged as outliers.
• The observations that are not marked as outliers are surrounded by a loop, the convex hull of the observations within the fence.

---

Tukey Depth

Tukey depth is also known as location depth or halfspace depth. The Tukey depth is a measure of the depth of a point in a fixed set of points.

Given a finite set $S$ of $n$ points and a point $p$ in $\mathbb{R}^d$, the Tukey depth of $p$ is defined as the minimum number of points of $S$ contained in any closed halfspace with $p$ on its boundary. An equivalent definition is the minimum number of points of $S$ contained in any halfspace which also contains $p$.

Many different algorithms have been developed to compute the Tukey depth of a point. This problem is equivalent to the $\textit{maximum feasible subsystem} ~\textrm{(MAX FS)}$ problem which is a long-standing problem and has been extensively studied.

---

Calculating Tukey Depth

Suppose points in $S$ are in general position (no $d+1$ points of $S\cup\{p\}$ lie on a common hyperplane), an upper bound on the Tukey depth of $p$ can be obtained by selecting any non-trivial vector $v\in\mathbb{R}^d$ and computing the Tukey depth of $p\cdot v$ in the one-dimensional point set

$$S\cdot v=\{x\cdot v:~x {\in} S\}.\tag 1$$ If $v$ is the inner-normal of the boundary of the halfspace $\hbar$ that defines the depth value of $p$, then

$$\mathrm{depth}(p,S)=\mathrm{depth}(p\cdot v,S\cdot v).\tag 2$$

In $\mathbb{R}^1$, we rank the points $S\cup\{p\}$ starting with $0$ from both ends to the median, then the depth of $p$ is its rank. More generally, given any $k$-flat $f$ orthogonal to the boundary of $\hbar$ we have

$\mathrm{depth}(p,S)=\mathrm{depth}(p\cdot f,S\cdot f),\tag 3$$

where $p\cdot f$ is the orthogonal projection of $p$ onto $f,$ and $S\cdot f$ is the orthogonal projection of $S$ onto $f.$

---

From this paper Absolute approximation of Tukey depth: Theory and experiments

Theorem 1

Let $S$ be a set of $n$ points in general position in $\mathbb{R}^d,~S^1$ be a subset of $d-1$ elements chosen at random and without replacement from $S, v$ be the vector perpendicular to the plane containing $S^1$ and another point $p$, $σ$ be an integer such that

$$0\leqslant\sigma\leqslant\left\lfloor\frac nd\right\rfloor-1.$$

Then

$$\Pr{\{\mathrm{depth}(p\cdot v,S\cdot v)\leqslant\mathrm{depth}(p,S)+\sigma\}}\geqslant\frac{{\sigma+d-1}\choose{d-1}}{n\choose{d-1}}.$$

Under point/hyperplane duality, the selection of $v$ is equivalent to selecting a random vertex in an arrangement of hyperplanes in $d-1$ dimensions. This selection of $v$ approximates $\text{depth}(p, S)$ to within $\sigma$ provided that the vertex is contained in a particular pseudo-ball of radius $\sigma.$ Therefore the proof boils down to showing that the number of vertices of an arrangement in a pseudo-ball of radius $σ$ is sufficiently large. In particular, we show that the number of vertices in such a pseudo-ball is at least ${\sigma+d-1}\choose{d-1}.$

---

Calculating Tukey Depth in R

Rdocumentation - depth.halfspace to calculate Tukey Depth

# NOT RUN {
# 3-dimensional normal distribution
data <- mvrnorm(200, rep(0, 3), 
                matrix(c(1, 0, 0,
                         0, 2, 0, 
                         0, 0, 1),
                nrow = 3))
x <- mvrnorm(10, rep(1, 3), 
             matrix(c(1, 0, 0,
                      0, 1, 0, 
                      0, 0, 1),
             nrow = 3))
              
# default - random Tukey depth
depths <- depth.halfspace(x, data)
cat("Depths: ", depths, "\n")

# default exact method - "recursive"
depths <- depth.halfspace(x, data, exact = TRUE)
cat("Depths: ", depths, "\n")

# method "line"
depths <- depth.halfspace(x, data, method = "line")
cat("Depths: ", depths, "\n")
# }