On the quality of randomized approximations of Tukey's depth
- URL: http://arxiv.org/abs/2309.05657v2
- Date: Fri, 20 Oct 2023 13:18:03 GMT
- Title: On the quality of randomized approximations of Tukey's depth
- Authors: Simon Briend and G\'abor Lugosi and Roberto Imbuzeiro Oliveira
- Abstract summary: Tukey's depth is a widely used measure of centrality for multivariate data.
It is hard to compute exact approximations of Tukey's depth in high dimensions.
We show that a randomized algorithm correctly approximates the maximal depth $1/2$ and depths close to zero.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Tukey's depth (or halfspace depth) is a widely used measure of centrality for
multivariate data. However, exact computation of Tukey's depth is known to be a
hard problem in high dimensions. As a remedy, randomized approximations of
Tukey's depth have been proposed. In this paper we explore when such randomized
algorithms return a good approximation of Tukey's depth. We study the case when
the data are sampled from a log-concave isotropic distribution. We prove that,
if one requires that the algorithm runs in polynomial time in the dimension,
the randomized algorithm correctly approximates the maximal depth $1/2$ and
depths close to zero. On the other hand, for any point of intermediate depth,
any good approximation requires exponential complexity.
Related papers
- Fast kernel half-space depth for data with non-convex supports [5.725360029813277]
We extend the celebrated halfspace depth to tackle distribution's multimodality.
The proposed depth can be computed using manifold gradient making faster than halfspace depth by several orders of magnitude.
The performance of our depth is demonstrated through numerical simulations as well as applications such as anomaly detection on real data and homogeneity testing.
arXiv Detail & Related papers (2023-12-21T18:55:22Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space.
We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size.
We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
arXiv Detail & Related papers (2023-02-14T22:12:16Z) - Adaptive Data Depth via Multi-Armed Bandits [6.29475963948119]
We develop an instance-adaptive algorithm for data depth computation.
We focus on simplicial depth, developed by Liu (1990), which has emerged as a promising notion of depth.
We show that we can reduce the complexity of identifying the deepest point in the data set from $O(nd)$ to $tildeO(nd-(d-1)alpha/2)$, where $tildeO$ suppresses logarithmic factors.
arXiv Detail & Related papers (2022-11-08T03:44:22Z) - Non-parametric Depth Distribution Modelling based Depth Inference for
Multi-view Stereo [43.415242967722804]
Recent cost volume pyramid based deep neural networks have unlocked the potential of efficiently leveraging high-resolution images for depth inference from multi-view stereo.
In general, those approaches assume that the depth of each pixel follows a unimodal distribution.
We propose constructing the cost volume by non-parametric depth distribution modeling to handle pixels with unimodal and multi-modal distributions.
arXiv Detail & Related papers (2022-05-08T05:13:04Z) - Eikonal depth: an optimal control approach to statistical depths [0.7614628596146599]
We propose a new type of globally defined statistical depth, based upon control theory and eikonal equations.
This depth is easy to interpret and compute, expressively captures multi-modal behavior, and extends naturally to data that is non-Euclidean.
arXiv Detail & Related papers (2022-01-14T01:57:48Z) - Depth Completion using Plane-Residual Representation [84.63079529738924]
We introduce a novel way of interpreting depth information with the closest depth plane label $p$ and a residual value $r$, as we call it, Plane-Residual (PR) representation.
By interpreting depth information in PR representation and using our corresponding depth completion network, we were able to acquire improved depth completion performance with faster computation.
arXiv Detail & Related papers (2021-04-15T10:17:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Efficient Depth Completion Using Learned Bases [94.0808155168311]
We propose a new global geometry constraint for depth completion.
By assuming depth maps often lay on low dimensional subspaces, a dense depth map can be approximated by a weighted sum of full-resolution principal depth bases.
arXiv Detail & Related papers (2020-12-02T11:57:37Z) - Non-Local Spatial Propagation Network for Depth Completion [82.60915972250706]
We propose a robust and efficient end-to-end non-local spatial propagation network for depth completion.
The proposed network takes RGB and sparse depth images as inputs and estimates non-local neighbors and their affinities of each pixel.
We show that the proposed algorithm is superior to conventional algorithms in terms of depth completion accuracy and robustness to the mixed-depth problem.
arXiv Detail & Related papers (2020-07-20T12:26:51Z) - Occlusion-Aware Depth Estimation with Adaptive Normal Constraints [85.44842683936471]
We present a new learning-based method for multi-frame depth estimation from a color video.
Our method outperforms the state-of-the-art in terms of depth estimation accuracy.
arXiv Detail & Related papers (2020-04-02T07:10:45Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.