論文の概要: Sparse Dimensionality Reduction Revisited
- arxiv url: http://arxiv.org/abs/2302.06165v1
- Date: Mon, 13 Feb 2023 08:01:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 16:26:24.566448
- Title: Sparse Dimensionality Reduction Revisited
- Title（参考訳）: スパース次元還元再訪
- Authors: Mikael M{\o}ller H{\o}gsgaard, Lion Kamma, Kasper Green Larsen, Jelani
Nelson, Chris Schwiegelshohn
- Abstract要約: スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。
疎な埋め込みを再検討し、下界の抜け穴を同定する。
また,最適埋め込み次元に対する最適半空間埋め込みの空隙性も改善する。
- 参考スコア（独自算出の注目度）: 13.170012290527017
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The sparse Johnson-Lindenstrauss transform is one of the central techniques
in dimensionality reduction. It supports embedding a set of $n$ points in
$\mathbb{R}^d$ into $m=O(\varepsilon^{-2} \lg n)$ dimensions while preserving
all pairwise distances to within $1 \pm \varepsilon$. Each input point $x$ is
embedded to $Ax$, where $A$ is an $m \times d$ matrix having $s$ non-zeros per
column, allowing for an embedding time of $O(s \|x\|_0)$.
Since the sparsity of $A$ governs the embedding time, much work has gone into
improving the sparsity $s$. The current state-of-the-art by Kane and Nelson
(JACM'14) shows that $s = O(\varepsilon ^{-1} \lg n)$ suffices. This is almost
matched by a lower bound of $s = \Omega(\varepsilon ^{-1} \lg
n/\lg(1/\varepsilon))$ by Nelson and Nguyen (STOC'13). Previous work thus
suggests that we have near-optimal embeddings.
In this work, we revisit sparse embeddings and identify a loophole in the
lower bound. Concretely, it requires $d \geq n$, which in many applications is
unrealistic. We exploit this loophole to give a sparser embedding when $d =
o(n)$, achieving $s = O(\varepsilon^{-1}(\lg n/\lg(1/\varepsilon)+\lg^{2/3}n
\lg^{1/3} d))$. We also complement our analysis by strengthening the lower
bound of Nelson and Nguyen to hold also when $d \ll n$, thereby matching the
first term in our new sparsity upper bound. Finally, we also improve the
sparsity of the best oblivious subspace embeddings for optimal embedding
dimensionality.
- Abstract（参考訳）: スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。
これは$n$の点集合を$\mathbb{R}^d$に$m=O(\varepsilon^{-2} \lg n)$次元に埋め込み、すべての対距離を$1 \pm \varepsilon$に保存することをサポートする。
それぞれの入力ポイント$x$は$Ax$に埋め込まれ、$A$は$m \times d$Matrixで列当たり$s$非ゼロで、$O(s \|x\|_0)$の埋め込み時間を可能にする。
A$の空白が埋め込み時間を支配するので、多くの作業が空白$s$の改善に費やされている。
Kane and Nelson (JACM'14) による現在の最先端は、s = O(\varepsilon ^{-1} \lg n)$ suffices であることを示している。
これは、Nelson and Nguyen (STOC'13) による $s = \Omega(\varepsilon ^{-1} \lg n/\lg(1/\varepsilon))$ の下界とほぼ一致する。
これまでの研究は、ほぼ最適な埋め込みがあることを示唆している。
本研究では, スパース埋め込みを再検討し, 下界の抜け穴を同定する。
具体的には$d \geq n$が必要で、多くのアプリケーションでは非現実的である。
この抜け穴を利用して、$d = o(n)$, achieve $s = O(\varepsilon^{-1}(\lg n/\lg(1/\varepsilon)+\lg^{2/3}n \lg^{1/3} d)$ のときにスペーサーを埋め込む。
我々はまた、Nelson と Nguyen の下界を$d \ll n$ のときも保持するように強化することで解析を補完し、新しいスパーシティ上界の最初の項と一致する。
最後に、最適な埋め込み次元のための最良部分空間埋め込みのスパース性も改善する。
関連論文リスト
- Sparsifying Suprema of Gaussian Processes [6.638504164134713]
我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。
また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
論文 参考訳（メタデータ） (2024-11-22T01:43:58Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳（メタデータ） (2024-06-04T15:50:42Z) - 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) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - 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) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳（メタデータ） (2021-06-25T19:14:45Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。