論文の概要: Approximate Multiplication of Sparse Matrices with Limited Space

• arxiv url: http://arxiv.org/abs/2009.03527v2
• Date: Sun, 23 Jun 2024 17:11:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-26 23:34:57.554770
• Title: Approximate Multiplication of Sparse Matrices with Limited Space
• Title（参考訳）: 空間を限定したスパース行列の近似乗算
• Authors: Yuanyu Wan, Lijun Zhang,
• Abstract要約: 我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。 理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
• 参考スコア（独自算出の注目度）: 24.517908972536432
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate matrix multiplication with limited space has received ever-increasing attention due to the emergence of large-scale applications. Recently, based on a popular matrix sketching algorithm -- frequent directions, previous work has introduced co-occuring directions (COD) to reduce the approximation error for this problem. Although it enjoys the space complexity of $O((m_x+m_y)\ell)$ for two input matrices $X\in\mathbb{R}^{m_x\times n}$ and $Y\in\mathbb{R}^{m_y\times n}$ where $\ell$ is the sketch size, its time complexity is $O\left(n(m_x+m_y+\ell)\ell\right)$, which is still very high for large input matrices. In this paper, we propose to reduce the time complexity by exploiting the sparsity of the input matrices. The key idea is to employ an approximate singular value decomposition (SVD) method which can utilize the sparsity, to reduce the number of QR decompositions required by COD. In this way, we develop sparse co-occuring directions, which reduces the time complexity to $\widetilde{O}\left((\nnz(X)+\nnz(Y))\ell+n\ell^2\right)$ in expectation while keeps the same space complexity as $O((m_x+m_y)\ell)$, where $\nnz(X)$ denotes the number of non-zero entries in $X$ and the $\widetilde{O}$ notation hides constant factors as well as polylogarithmic factors. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD. Furthermore, we empirically verify the efficiency and effectiveness of our algorithm.
• Abstract（参考訳）: 空間を限定した近似行列乗法は、大規模応用の出現により、ますます注目を集めている。 近年,一般的な行列スケッチアルゴリズム-頻繁な方向-に基づいて,この問題に対する近似誤差を低減するための共起方向(co-occuring direction, COD)を導入している。 2つの入力行列に対して$O((m_x+m_y)\ell)$X\in\mathbb{R}^{m_x\times n}$と$Y\in\mathbb{R}^{m_y\times n}$はスケッチサイズであるが、その時間複雑性は$O\left(n(m_x+m_y+\ell)\right)$である。 本稿では,入力行列の空間性を利用して,時間的複雑性を低減することを提案する。 鍵となる考え方は、その空間を利用できる近似特異値分解(SVD)法を用いて、CODが必要とするQR分解数を減少させることである。 このようにして、時間複雑性を$\widetilde{O}\left((\nnz(X)+\nnz(Y))\ell+n\ell^2\right)$に減少させるスパース共起方向を開発するとともに、$O((m_x+m_y)\ell)$と同じ空間複雑性を保持する。 理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。 さらに,本アルゴリズムの有効性と有効性を実証的に検証した。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。 結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
  本稿では,三重相関を捉える注意の一般化について検討する。 この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。 構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
  論文  参考訳（メタデータ） (2023-10-06T07:42:39Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• The Complexity of Dynamic Least-Squares Regression [11.815510373329337]
  動的最小二乗回帰の複雑さ。 ゴールは、$min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin に対する $epsilon-approximate ソリューションを維持することである。
  論文  参考訳（メタデータ） (2022-01-01T18:36:17Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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