論文の概要: A Near-Linear Time Algorithm for the Chamfer Distance
- arxiv url: http://arxiv.org/abs/2307.03043v1
- Date: Thu, 6 Jul 2023 15:07:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-07 13:48:49.999671
- Title: A Near-Linear Time Algorithm for the Chamfer Distance
- Title（参考訳）: シャンファー距離の近距離時間アルゴリズム
- Authors: Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik
Waingarten
- Abstract要約: チャンファー距離は点雲間の相似性の一般的な尺度である。
1+epsilon)$-approximate アルゴリズムは,Chamfer 距離をほぼ直線走行時間で推定する。
我々の実験は、大規模な高次元データセット上では正確かつ高速であることを示した。
- 参考スコア（独自算出の注目度）: 21.018781726524946
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For any two point sets $A,B \subset \mathbb{R}^d$ of size up to $n$, the
Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A}
\min_{b \in B} d_X(a,b)$, where $d_X$ is the underlying distance measure (e.g.,
the Euclidean or Manhattan distance). The Chamfer distance is a popular measure
of dissimilarity between point clouds, used in many machine learning, computer
vision, and graphics applications, and admits a straightforward $O(d n^2)$-time
brute force algorithm. Further, the Chamfer distance is often used as a proxy
for the more computationally demanding Earth-Mover (Optimal Transport)
Distance. However, the \emph{quadratic} dependence on $n$ in the running time
makes the naive approach intractable for large datasets.
We overcome this bottleneck and present the first $(1+\epsilon)$-approximate
algorithm for estimating the Chamfer distance with a near-linear running time.
Specifically, our algorithm runs in time $O(nd \log (n)/\varepsilon^2)$ and is
implementable. Our experiments demonstrate that it is both accurate and fast on
large high-dimensional datasets. We believe that our algorithm will open new
avenues for analyzing large high-dimensional point clouds. We also give
evidence that if the goal is to \emph{report} a $(1+\varepsilon)$-approximate
mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic
time algorithm is unlikely to exist.
- Abstract（参考訳）: 任意の二つの点集合に対して、$A,B \subset \mathbb{R}^d$ が$n$ になるとき、$A$ から $B$ までのチャムファー距離は $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} d_X(a,b)$ と定義される。
チャンファー距離は点雲間の相似性の一般的な尺度であり、多くの機械学習、コンピュータビジョン、グラフィックアプリケーションで使われ、単純な$O(d n^2)$-time brute forceアルゴリズムが認められている。
さらに、チャンファー距離はより計算的に要求される地球移動距離のプロキシとしてしばしば用いられる。
しかし、実行時の$n$に依存する \emph{quadratic} は、大規模なデータセットでは難解なアプローチとなる。
このボトルネックを克服し、ほぼ直線走行時間でチャンファー距離を推定する最初の$(1+\epsilon)$-approximateアルゴリズムを示す。
具体的には、我々のアルゴリズムは時間$O(nd \log (n)/\varepsilon^2)$で実行でき、実装可能である。
我々の実験は、大規模な高次元データセットでは正確かつ高速であることを示した。
我々は,我々のアルゴリズムが大規模高次元点雲を解析するための新たな道を開くと信じている。
また、emph{report} a $(1+\varepsilon)$-approximate mapping to \emph{report} a $(1+\varepsilon) from $a$ to $b$ (単なる値とは対照的に) ならば、任意のサブ量子時間アルゴリズムは存在し得ない。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Metricizing the Euclidean Space towards Desired Distance Relations in
Point Clouds [1.2366208723499545]
我々は教師なし学習アルゴリズム、具体的には$k$-Means and density-based clustering algorithm(DBSCAN)を攻撃している。
クラスタリングアルゴリズムの結果は、特定の距離関数を使用するための標準化された固定された処方令がなければ、一般的には信頼できない可能性がある。
論文 参考訳（メタデータ） (2022-11-07T16:37:29Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Provably Approximated ICP [40.349822671753024]
そこで、emphalwaysが$p times q$で3ドルのペアからなる"witness"集合があることを証明し、新しいアライメントアルゴリズムにより、この大域的最適化に対する定数因子近似を定義する。
私たちの近似定数は、実際には1ドル近くであり、最先端のアルゴリズムよりも最大10ドル小さいです。
論文 参考訳（メタデータ） (2021-01-10T18:09:29Z) - A Linear Transportation $\mathrm{L}^p$ Distance for Pattern Recognition [4.991212094743681]
輸送$mathrmLp$距離は、ワッサーシュタイン$mathrmWp$距離の一般化として提案されている。
線形$mathrmTLp$距離は信号処理タスクの線形$mathrmWp$距離よりも大幅に向上することを示す。
論文 参考訳（メタデータ） (2020-09-23T17:19:19Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for
RMS Matching in a Plane [3.9596068699962315]
2-ワッサーシュタイン距離(英: 2-Wasserstein distance、RMS distance)は確率分布間の類似性の有用な尺度である。
我々は$O(n5/4mathrmpolylog n,1/varepsilon)$timeで実行される新しい$varepsilon$-approximationアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-15T14:47:25Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。