論文の概要: On the quality of randomized approximations of Tukey's depth

• arxiv url: http://arxiv.org/abs/2309.05657v1
• Date: Mon, 11 Sep 2023 17:52:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-12 11:29:40.761788
• Title: On the quality of randomized approximations of Tukey's depth
• Title（参考訳）: タキー深さのランダム化近似の品質について
• Authors: Simon Briend and G\'abor Lugosi and Roberto Imbuzeiro Oliveira
• Abstract要約: タキー深度は多変量データの集中度を広く測定する尺度である。 タキーの深さの正確な近似を高次元で計算することは困難である。 ランダム化アルゴリズムは最大深さ1/2$と0に近い深さを正確に近似することを示した。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: テューキーの深さ (tukey's depth) は多変量データに対して広く使われる中心性の尺度である。 しかし、チューキーの深さの正確な計算は高次元では難しい問題であることが知られている。 治療として、ツキーの深さのランダム化近似が提案されている。 本稿では,そのようなランダム化アルゴリズムが,Tukeyの深さの近似値を返す方法を検討する。 ログコンケーブ等方性分布からデータがサンプリングされた場合について検討する。 アルゴリズムが次元において多項式時間で動く必要がある場合、ランダム化されたアルゴリズムは最大深さ1/2$と0に近い深さを正確に近似する。 一方、任意の中間深さの点に対して、良い近似は指数複雑性を必要とする。

関連論文リスト

• Fast kernel half-space depth for data with non-convex supports [5.725360029813277]
  我々は、分布の多モード性に取り組むために、祝福された半空間深さを延長する。 提案した深さは、半空間の深さよりも数桁高速な多様体勾配を用いて計算することができる。 数値シミュレーションや, 実データにおける異常検出, 均一性試験などの応用により, 深度特性を実証した。
  論文  参考訳（メタデータ） (2023-12-21T18:55:22Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Adaptive Data Depth via Multi-Armed Bandits [6.29475963948119]
  データ深度計算のためのインスタンス適応アルゴリズムを開発した。 我々は、Liu (1990) によって開発されたsimplicial depthに焦点をあてる。 我々は、$O(nd)$から$tildeO(nd-(d-1)alpha/2)$に設定したデータセットの最も深い点を特定する複雑さを減らすことができることを示した。
  論文  参考訳（メタデータ） (2022-11-08T03:44:22Z)
• Non-parametric Depth Distribution Modelling based Depth Inference for Multi-view Stereo [43.415242967722804]
  最近のコストボリュームピラミッドに基づくディープニューラルネットワークは、多視点ステレオからの深度推論に高解像度の画像を効率的に活用する可能性を解き放った。 一般に、これらのアプローチは各ピクセルの深さが一様分布に従うと仮定する。 本研究では,非パラメトリック深度分布モデルを用いて,一様および多モード分布の画素を扱うコストボリュームを構築することを提案する。
  論文  参考訳（メタデータ） (2022-05-08T05:13:04Z)
• Eikonal depth: an optimal control approach to statistical depths [0.7614628596146599]
  本稿では,制御理論と固有方程式に基づく,グローバルに定義された新しいタイプの統計深度を提案する。 この深さは解釈や計算が容易で、マルチモーダルな振る舞いを表現的に捉え、非ユークリッド的なデータに自然に拡張する。
  論文  参考訳（メタデータ） (2022-01-14T01:57:48Z)
• Depth Completion using Plane-Residual Representation [84.63079529738924]
  深度情報を最も近い深度平面ラベル$p$と残値$r$で解釈する新しい方法を紹介し,これをPlane-Residual (PR)表現と呼ぶ。 PR表現で深度情報を解釈し,それに対応する深度補完網を用いて,高速な計算により深度補完性能を向上させることができた。
  論文  参考訳（メタデータ） (2021-04-15T10:17:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Depth Completion Using Learned Bases [94.0808155168311]
  深度補正のための新しい大域的幾何制約を提案する。 低次元部分空間上によく配置される深さ写像を仮定することにより、高密度深度写像は全解像度の主深度基底の重み付け和で近似することができる。
  論文  参考訳（メタデータ） (2020-12-02T11:57:37Z)
• Non-Local Spatial Propagation Network for Depth Completion [82.60915972250706]
  本研究では,深度完了のための堅牢で効率的な非局所的空間伝搬ネットワークを提案する。 提案するネットワークは,RGBとスパース深度画像を入力とし,各画素の非局所的近傍とその親和性を推定する。 提案アルゴリズムは,混合深度問題に対する深度補完精度とロバスト性の観点から,従来のアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-07-20T12:26:51Z)
• Occlusion-Aware Depth Estimation with Adaptive Normal Constraints [85.44842683936471]
  カラービデオから多フレーム深度を推定する新しい学習手法を提案する。 本手法は深度推定精度において最先端の手法より優れる。
  論文  参考訳（メタデータ） (2020-04-02T07:10:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。