論文の概要: 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$増加するにつれて多項式減衰を許容する量子化誤差に匹敵することを示す。
したがって、所望の精度を達成するために必要なバイナリコードの長さは非常に小さく、精度を損なうことなくさらに圧縮できることを示す。
この結果を説明するために,提案手法を自然画像上でテストし,強力な性能を実現することを示す。
関連論文リスト
- Combinatorial optimization of the coefficient of determination [0.0]
決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。
誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
論文 参考訳（メタデータ） (2024-10-12T00:53:25Z) - 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) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - 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) - Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
我々はスパース共起方向を開発し、期待値の$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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。