論文の概要: Optimal Embedding Dimension for Sparse Subspace Embeddings

• arxiv url: http://arxiv.org/abs/2311.10680v1
• Date: Fri, 17 Nov 2023 18:01:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-20 13:40:18.713641
• Title: Optimal Embedding Dimension for Sparse Subspace Embeddings
• Title（参考訳）: スパース部分空間埋め込みのための最適埋め込み次元
• Authors: Shabarish Chenakkod, Micha{\l} Derezi\'nski, Xiaoyu Dong, and Mark Rudelson
• Abstract要約: ランダム$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)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
• 参考スコア（独自算出の注目度）: 13.387361384552484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A random $m\times n$ matrix $S$ is an oblivious subspace embedding (OSE) with parameters $\epsilon>0$, $\delta\in(0,1/3)$ and $d\leq m\leq n$, if for any $d$-dimensional subspace $W\subseteq R^n$, $P\big(\,\forall_{x\in W}\ (1+\epsilon)^{-1}\|x\|\leq\|Sx\|\leq (1+\epsilon)\|x\|\,\big)\geq 1-\delta.$ It is known that the embedding dimension of an OSE must satisfy $m\geq d$, and for any $\theta > 0$, a Gaussian embedding matrix with $m\geq (1+\theta) d$ is an OSE with $\epsilon = O_\theta(1)$. However, such optimal embedding dimension is not known for other embeddings. Of particular interest are sparse OSEs, having $s\ll m$ non-zeros per column, with applications to problems such as least squares regression and low-rank approximation. We show that, given any $\theta > 0$, an $m\times n$ random matrix $S$ with $m\geq (1+\theta)d$ consisting of randomly sparsified $\pm1/\sqrt s$ entries and having $s= O(\log^4(d))$ non-zeros per column, is an oblivious subspace embedding with $\epsilon = O_{\theta}(1)$. Our result addresses the main open question posed by Nelson and Nguyen (FOCS 2013), who conjectured that sparse OSEs can achieve $m=O(d)$ embedding dimension, and it improves on $m=O(d\log(d))$ shown by Cohen (SODA 2016). We use this to construct the first oblivious subspace embedding with $O(d)$ embedding dimension that can be applied faster than current matrix multiplication time, and to obtain an optimal single-pass algorithm for least squares regression. We further extend our results to construct even sparser non-oblivious embeddings, leading to the first subspace embedding with low distortion $\epsilon=o(1)$ and optimal embedding dimension $m=O(d/\epsilon^2)$ that can be applied in current matrix multiplication time.
• Abstract（参考訳）: ランダム$m\times n$ matrix $S$ は、パラメータ $\epsilon>0$, $\delta\in(0,1/3)$ および $d\leq m\leq n$ が、任意の$d$-次元部分空間 $W\subseteq R^n$, $P\big(\,\forall_{x\in W}\ (1+\epsilon)^{-1}\|x\|\leq\|Sx\|\leq (1+\epsilon)\|x\|\|\\big)\geq 1-\delta であるときである。 任意の$\theta > 0$ に対して、$m\geq (1+\theta) d$ のガウス埋め込み行列は、$\epsilon = o_\theta(1)$ のオースである。 しかし、そのような最適埋め込み次元は他の埋め込みでは知られていない。 特に興味があるのはスパースosで、1カラムあたり$s\ll m$ non-zerosを持ち、最小二乗回帰や低ランク近似といった問題への応用がある。 任意の$\theta > 0$が与えられたとき、$m\times n$ random matrix $S$ with $m\geq (1+\theta)d$は、ランダムにスパースされた$\pm1/\sqrt s$エントリを持ち、$s= O(\log^4(d))$ non-zeros per column を持つ。 その結果、sparse oses が $m=o(d)$ 埋め込み次元を達成できると推測したnelson and nguyen (focs 2013) が提起した主要なオープン問題に対処し、cohen が示した $m=o(d\log(d))$ を改善した(soda 2016)。 これを応用して、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元による最初の難解な部分空間埋め込みを構築し、最小二乗回帰のための最適シングルパスアルゴリズムを得る。 さらに、この結果をさらに拡張して、低歪み$\epsilon=o(1)$ と最適な埋め込み次元 $m=O(d/\epsilon^2)$ で、現在の行列乗算時間で適用できる最初の部分空間の埋め込みを構築する。

関連論文リスト

• 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)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。 我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
  論文  参考訳（メタデータ） (2023-04-06T16:15:19Z)
• Sparse Dimensionality Reduction Revisited [13.170012290527017]
  スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。 疎な埋め込みを再検討し、下界の抜け穴を同定する。 また,最適埋め込み次元に対する最適半空間埋め込みの空隙性も改善する。
  論文  参考訳（メタデータ） (2023-02-13T08:01:25Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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)
• Subspace approximation with outliers [6.186553186139257]
  本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。 我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
  論文  参考訳（メタデータ） (2020-06-30T07:22:33Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。 最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。 これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
  論文  参考訳（メタデータ） (2020-04-16T22:57:06Z)

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

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