論文の概要: Faster Binary Embeddings for Preserving Euclidean Distances
- arxiv url: http://arxiv.org/abs/2010.00712v2
- Date: Wed, 10 Mar 2021 01:30:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 07:53:49.690025
- Title: Faster Binary Embeddings for Preserving Euclidean Distances
- Title(参考訳): ユークリッド距離保存のための高速バイナリ埋め込み
- Authors: Jinjie Zhang, Rayan Saab
- Abstract要約: 本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。
我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
- 参考スコア(独自算出の注目度): 9.340611077939828
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a fast, distance-preserving, binary embedding algorithm to
transform a high-dimensional dataset $\mathcal{T}\subseteq\mathbb{R}^n$ into
binary sequences in the cube $\{\pm 1\}^m$. When $\mathcal{T}$ consists of
well-spread (i.e., non-sparse) vectors, our embedding method applies a stable
noise-shaping quantization scheme to $A x$ where $A\in\mathbb{R}^{m\times n}$
is a sparse Gaussian random matrix. This contrasts with most binary embedding
methods, which usually use $x\mapsto \mathrm{sign}(Ax)$ for the embedding.
Moreover, we show that Euclidean distances among the elements of $\mathcal{T}$
are approximated by the $\ell_1$ norm on the images of $\{\pm 1\}^m$ under a
fast linear transformation. This again contrasts with standard methods, where
the Hamming distance is used instead. Our method is both fast and memory
efficient, with time complexity $O(m)$ and space complexity $O(m)$. Further, we
prove that the method is accurate and its associated error is comparable to
that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization
error that admits a polynomial decay as the embedding dimension $m$ increases.
Thus the length of the binary codes required to achieve a desired accuracy is
quite small, and we show it can even be compressed further without compromising
the accuracy. To illustrate our results, we test the proposed method on natural
images and show that it achieves strong performance.
- Abstract(参考訳): 本稿では,高次元データセット $\mathcal{T}\subseteq\mathbb{R}^n$ を立方体 $\{\pm 1\}^m$ のバイナリ列に変換する,高速で保存可能なバイナリ埋め込みアルゴリズムを提案する。
$\mathcal{T}$ が well-spread (つまり非スパース) ベクトルからなるとき、埋め込み法は安定なノイズシェーピング量子化スキームを $A x$ に適用する。
これはほとんどのバイナリ埋め込みメソッドとは対照的で、通常は埋め込みに$x\mapsto \mathrm{sign}(Ax)$を使用する。
さらに、$\mathcal{T}$の要素間のユークリッド距離は、高速線型変換の下で$\{\pm 1\}^m$の像上の$\ell_1$ノルムによって近似されることを示す。
これは、代わりにハミング距離を使用する標準的な方法とは対照的である。
我々の方法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
さらに、この手法は正確であり、関連する誤差は、連続値のジョンソン-リンデンシュトラウス埋め込みと、埋め込み次元が$m$増加するにつれて多項式減衰を許容する量子化誤差に匹敵することを示す。
したがって、所望の精度を達成するために必要なバイナリコードの長さは非常に小さく、精度を損なうことなくさらに圧縮できることを示す。
この結果を説明するために,提案手法を自然画像上でテストし,強力な性能を実現することを示す。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Solving Dense Linear Systems Faster than via Preconditioning [15.781447266000159]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP
hierarchies [37.29025597886073]
多次元スケーリング(MDS)は、$n$オブジェクト間のペアワイドな相似性を低次元空間に埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
我々の分析は、低次元ユークリッド空間の幾何学を利用して、アスペクト比$Delta$への指数的依存を避けることができる。
論文 参考訳(メタデータ) (2023-11-29T17:42:05Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Approximate Multiplication of Sparse Matrices with Limited Space [27.875251633343666]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳(メタデータ) (2020-09-08T05:39:19Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳(メタデータ) (2020-08-15T11:06:45Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳(メタデータ) (2020-08-01T19:23:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。