論文の概要: Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL
- arxiv url: http://arxiv.org/abs/2611.11151v1
- Date: Sun, 08 Nov 2026 05:46:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-11 09:45:37.947152
- Title: Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL
- Title(参考訳): Lopsided EmbeddingsとStructured JLによる高速近似 $\ell_p$ Chamfer Distance
- Abstract要約: 本稿では,Chamfer 距離を $ell_p ノルムで 1 p le 2$ で近似する効率的なアルゴリズムを提案する。
チャムファー距離を保存するのに十分であることを示す。
また, ストリーミング環境における角距離および上下境界について, 追加的な結果を与える。
- 参考スコア(独自算出の注目度): 63.08320557041278
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For two $d$-dimensional point sets $A, B$ of size $n$, the Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a, b)$, where $\mathsf{dist}$ is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the $\ell_p$ norm for $1 < p \le 2$. For the general case $1 < p < 2$, we utilize lopsided $\ell_p$ to $\ell_1$ embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to $O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2)$ total time. For the specific Euclidean case ($p=2$), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous $\ell_1$-specific Chamfer algorithm in $\ell_2$. These achieve a runtime matching the recent state-of-the-art $\ell_1$ result of $O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2)$, improving upon the previous $O(nd \log n/\varepsilon^2)$ bound for $\ell_2$. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.
- Abstract(参考訳): 2つの$d$-次元点集合 $A, B$ of size $n$ に対して、$A$ から $B$ までのチャムファー距離は $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a,b)$ と定義される。
1 < p \le 2$ に対して $\ell_p$ ノルムの下で Chamfer 距離を近似する効率的なアルゴリズムを提案する。
一般的な場合、1 < p < 2$ に対して、弱保証付き lopsided $\ell_p$ を $\ell_1$ 埋め込みに利用する。
チャムファー距離を保存するのに十分であることを示す。
高次元構造では, 高速行列乗算法を用いて, ラップサイドの埋め込みを高速化する。
これらは$O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2)$ total timeとなる。
特定のユークリッドの場合(p=2$)、Toeplitz行列に基づくFast Johnson-Lindenstrauss変換を利用し、以前の$\ell_1$-specific Chamferアルゴリズムを$\ell_2$で再解析する。
これらは、最近の$O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2)$の結果と一致するランタイムを実現し、以前の$O(nd \log n/\varepsilon^2)$bound for $\ell_2$を改良した。
また, ストリーミング環境における角距離および上下境界について, 追加的な結果を与える。
関連論文リスト
- Shallow ReLU$^s$ Networks in $L^p$-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization [12.871748162999062]
特に、$_d$が均一測度で$1le p2$のとき、近似率は$O!left(m-fracp(2s+2d+1)-2d2dpright)$ for $1le p*$と$O!left(m-fracp(4s+3d-1)-2d+24dpright)$ for $p*p2$である。
non (複数形 nons)
論文 参考訳(メタデータ) (2026-05-18T14:27:49Z) - New Algorithmic Directions in Optimal Transport and Applications for Product Spaces [5.9725566031600925]
アルゴリズムの観点から2つの高次元分布$mu,nu$ in$Rn$の最適輸送について検討する。
実行時間は、$mu,nu$の完全な表現サイズではなく、次元に依存する。
ガウス測度$varepsilon$の場合、ほとんどの$Phin$サンプルは距離$O(sqrtlog 1/varepsilon)$ in $poly(n/varepsilon)$にマッピングできる。
論文 参考訳(メタデータ) (2025-09-25T19:58:06Z) - Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。
A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。
A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文 参考訳(メタデータ) (2025-09-15T14:26:11Z) - Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳(メタデータ) (2025-08-09T08:28:06Z) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳(メタデータ) (2023-11-17T18:01:58Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - Sparse Dimensionality Reduction Revisited [13.170012290527017]
スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。
疎な埋め込みを再検討し、下界の抜け穴を同定する。
また,最適埋め込み次元に対する最適半空間埋め込みの空隙性も改善する。
論文 参考訳(メタデータ) (2023-02-13T08:01:25Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。