Fugu-MT 論文翻訳(概要): Optimal Embedding Dimension for Sparse Subspace Embeddings

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

arxiv url: http://arxiv.org/abs/2311.10680v2
Date: Thu, 6 Jun 2024 02:57:38 GMT
ステータス: 処理完了
システム内更新日: 2024-06-08 00:20:02.592548
Title: Optimal Embedding Dimension for Sparse Subspace Embeddings
Title（参考訳）: スパース部分空間埋め込みのための最適埋め込み次元
Authors: Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, 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)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
参考スコア（独自算出の注目度）: 4.042707434058959
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 Leverage Score Sparsification (LESS), which is a recently introduced non-oblivious embedding technique. We use LESS to construct 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 であるときである。 for any $\theta > 0$, for a Gaussian embeddedding matrix with $m\geq (1+\theta) d$ is a OSE with $\epsilon = O_\theta(1)$。しかし、そのような最適な埋め込み次元は他の埋め込みでは知られていない。特に興味深いのがスパースOSEで、列当たり$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 を持つ。我々の結果は、Nelson and Nguyen (FOCS 2013) が提起した主要なオープンな問題に対処し、OSEs のスパースが$m=O(d)$埋め込み次元を達成できると推測し、Cohen (SODA 2016) が示した$m=O(d\log(d))$を改善する。これを応用して、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元による最初の難解な部分空間埋め込みを構築し、最小二乗回帰のための最適シングルパスアルゴリズムを得る。我々はさらに、最近導入された非公開埋め込み技術であるLevanage Score Sparsification (LESS)に結果を拡張した。 LESSを用いて低歪み$\epsilon=o(1)$と最適埋め込み次元$m=O(d/\epsilon^2)$で最初の部分空間埋め込みを構築する。

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

関連論文リスト