Fast computation of Tukey trimmed regions and median in dimension <i>p</i> &gt; 2

Given data in ℝp, a Tukey <i>κ</i>-trimmed region is the set of all points that have at least Tukey depth <i>κ</i> w.r.t. the data. As they are visual, affine equivariant and robust, Tukey regions are useful tools in nonparametric multivariate analysis. While these regions are easily defined and interpreted, their practical use in applications has been impeded so far by the lack of efficient computational procedures in dimension <i>p</i> &gt; 2. We construct two novel algorithms to compute a Tukey <i>κ</i>-trimmed region, a naïve one and a more sophisticated one that is much faster than known algorithms. Further, a strict bound on the number of facets of a Tukey region is derived. In a large simulation study the novel fast algorithm is compared with the naïve one, which is slower and by construction exact, yielding in every case the same correct results. Finally, the approach is extended to an algorithm that calculates the innermost Tukey region and its barycenter, the Tukey median. Supplementary material is available online.给定p维实空间（ℝ^p）中的数据集，图基κ修剪区域（Tukey κ-trimmed region）是指所有相对于该数据集满足至少κ阶图基深度（Tukey depth）的点构成的集合。由于图基区域具备可可视化性、仿射不变性（affine equivariant）与鲁棒性，其在非参数多元分析（nonparametric multivariate analysis）中是一类极具价值的工具。尽管这类区域的定义与解释都较为直观，但此前由于在维度p>2时缺乏高效的计算方法，其在实际应用中的推广一直受到阻碍。本文构建了两种全新的用于计算图基κ修剪区域的算法：一种为朴素实现算法，另一种则更为精细，且运行速度远优于现有已知算法。此外，本文还推导得到了图基区域的面数（facets）严格上界。在大规模模拟研究中，本文将提出的快速新算法与朴素算法进行了对比：后者虽基于精确构造且运行较慢，但二者在所有实验场景下均得到了一致的正确结果。最后，本文将该方法进一步拓展，得到可计算最内层图基区域及其重心（barycenter，即图基中位数（Tukey median））的算法。本文附带在线补充材料。