论文标题
关于Tukey深度中央区域的精确计算
On exact computation of Tukey depth central regions
论文作者
论文摘要
Tukey（或半空间）深度将非参数方法扩展到多元数据。分位数的多元类似物是Tukey深度的中央区域，定义为$ d $二维空间中的点集，其Tukey深度超过给定阈值$ K $。我们解决了这些中央区域快速准确计算的问题。首先，我们分析了Liu等人的有效算法A。 （2019年），并证明它产生的确切导致尺寸$ d = 2 $，或者以较低的阈值$ k $在任意维度中。我们提供示例，其中算法A未能以$ d> 2 $恢复确切的Tukey深度区域，并提出了保证准确的修改。我们表达了计算双重公式中确切中心区域的问题，并使用该观点证明对我们的算法的进一步改进不太可能。 r软件包TukeyRegion可以自由获得我们精确算法的有效C ++实现。
The Tukey (or halfspace) depth extends nonparametric methods toward multivariate data. The multivariate analogues of the quantiles are the central regions of the Tukey depth, defined as sets of points in the $d$-dimensional space whose Tukey depth exceeds given thresholds $k$. We address the problem of fast and exact computation of those central regions. First, we analyse an efficient Algorithm A from Liu et al. (2019), and prove that it yields exact results in dimension $d=2$, or for a low threshold $k$ in arbitrary dimension. We provide examples where Algorithm A fails to recover the exact Tukey depth region for $d>2$, and propose a modification that is guaranteed to be exact. We express the problem of computing the exact central region in its dual formulation, and use that viewpoint to demonstrate that further substantial improvements to our algorithm are unlikely. An efficient C++ implementation of our exact algorithm is freely available in the R package TukeyRegion.
