論文の概要: The Fast Johnson-Lindenstrauss Transform is Even Faster

• arxiv url: http://arxiv.org/abs/2204.01800v1
• Date: Mon, 4 Apr 2022 18:54:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-06 14:43:58.926268
• Title: The Fast Johnson-Lindenstrauss Transform is Even Faster
• Title（参考訳）: 高速johnson-lindenstrauss変換はさらに高速
• Authors: Ora Nova Fandina, Mikael M{\o}ller H{\o}gsgaard, Kasper Green Larsen
• Abstract要約: 高速JL変換は、$d$次元ユークリッド空間に$n$点の集合を最適な$k=O(varepsilon-2 ln n)$次元に埋め込む。 我々は、Fast JL 変換の驚くべき新しい解析を行い、埋め込み時間の $k ln2 n$ 項を $(k ln2 n)/alpha$ for a $alpha = Omega(minvarepsilon-1ln (1/varepsilon), ln n$ に改善できることを示した。
• 参考スコア（独自算出の注目度）: 9.348107805982604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of $n$ points in $d$-dimensional Euclidean space into optimal $k=O(\varepsilon^{-2} \ln n)$ dimensions, while preserving all pairwise distances to within a factor $(1 \pm \varepsilon)$. The Fast JL transform supports computing the embedding of a data point in $O(d \ln d +k \ln^2 n)$ time, where the $d \ln d$ term comes from multiplication with a $d \times d$ Hadamard matrix and the $k \ln^2 n$ term comes from multiplication with a sparse $k \times d$ matrix. Despite the Fast JL transform being more than a decade old, it is one of the fastest dimensionality reduction techniques for many tradeoffs between $\varepsilon, d$ and $n$. In this work, we give a surprising new analysis of the Fast JL transform, showing that the $k \ln^2 n$ term in the embedding time can be improved to $(k \ln^2 n)/\alpha$ for an $\alpha = \Omega(\min\{\varepsilon^{-1}\ln(1/\varepsilon), \ln n\})$. The improvement follows by using an even sparser matrix. We also complement our improved analysis with a lower bound showing that our new analysis is in fact tight.
• Abstract（参考訳）: Ailon and Chazelle (SICOMP'09) による半素のFast Johnson-Lindenstrauss (Fast JL) 変換は、$d$-次元ユークリッド空間に$n$点の集合を最適$k=O(\varepsilon^{-2} \ln n)$次元に埋め込むとともに、すべての対距離を$(1 \pm \varepsilon)$の範囲内で保存する。 高速JL変換は、$O(d \ln d +k \ln^2 n)$ timeにおけるデータポイントの埋め込みの計算をサポートし、$d \ln d$ termは$d \times d$ Hadamard matrixによる乗法から、$k \ln^2 n$ termはスパース$k \times d$ matrixによる乗法に由来する。 高速JL変換は10年以上前からあるが、これは、$\varepsilon, d$ と$n$の間の多くのトレードオフにおいて、最も高速な次元削減手法の1つである。 本研究では, jl 変換の高速化に関する驚くべき解析を行い, 埋め込み時間の $k \ln^2 n$ 項を $(k \ln^2 n)/\alpha$ for a $\alpha = \omega(\min\{\varepsilon^{-1}\ln(1/\varepsilon), \ln n\})$ に改善できることを示した。 この改善は偶数スパルサー行列を用いることで従う。 また,改良した解析を下位のバウンダリで補完し,新しい解析が実際に密接であることを示す。

関連論文リスト

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• 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 Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions [44.655316553524855]
  我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。 それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
  論文  参考訳（メタデータ） (2023-11-17T22:07:18Z)
• 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)
• Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products [9.661328973620531]
  自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。 我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。 我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
  論文  参考訳（メタデータ） (2023-11-03T14:56:24Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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