論文の概要: Multiplication-Avoiding Variant of Power Iteration with Applications
- arxiv url: http://arxiv.org/abs/2110.12065v1
- Date: Fri, 22 Oct 2021 20:59:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-01 01:50:26.943184
- Title: Multiplication-Avoiding Variant of Power Iteration with Applications
- Title（参考訳）: 電力反復の乗算回避と応用
- Authors: Hongyi Pan, Diaa Badawi, Runxuan Miao, Erdem Koyuncu and Ahmet Enis
Cetin
- Abstract要約: 乗算回避パワーイテレーション(MAPI)を導入する。
MAPIはレギュラーパワーイテレーション(RPI)に現れる標準の$ell$-inner製品を置き換える
RPIと比較すると、MAPIは通常、より高速に収束するだけでなく、優れたパフォーマンスを提供する。
- 参考スコア（独自算出の注目度）: 14.296970557215747
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Power iteration is a fundamental algorithm in data analysis. It extracts the
eigenvector corresponding to the largest eigenvalue of a given matrix.
Applications include ranking algorithms, recommendation systems, principal
component analysis (PCA), among many others. In this paper, We introduce
multiplication-avoiding power iteration (MAPI), which replaces the standard
$\ell_2$-inner products that appear at the regular power iteration (RPI) with
multiplication-free vector products which are Mercer-type kernel operations
related with the $\ell_1$ norm. Precisely, for an $n\times n$ matrix, MAPI
requires $n$ multiplications, while RPI needs $n^2$ multiplications per
iteration. Therefore, MAPI provides a significant reduction of the number of
multiplication operations, which are known to be costly in terms of energy
consumption. We provide applications of MAPI to PCA-based image reconstruction
as well as to graph-based ranking algorithms. When compared to RPI, MAPI not
only typically converges much faster, but also provides superior performance.
- Abstract（参考訳）: パワーイテレーションはデータ分析の基本的なアルゴリズムである。
与えられた行列の最大固有値に対応する固有ベクトルを抽出する。
アプリケーションには、ランキングアルゴリズム、レコメンデーションシステム、主成分分析(PCA)などが含まれている。
本稿では、正規電力繰り返し(RPI)に現れる標準の$\ell_2$-innerを、$\ell_1$ノルムに関連するマーサー型カーネル操作である乗算自由ベクトル積に置き換える乗算回避パワーイテレーション(MAPI)を導入する。
正確には、$n\times n$行列の場合、MAPIは$n$乗算を必要とし、RPIはイテレーション毎に$n^2$乗算を必要とする。
したがって、MAPIは、エネルギー消費の面でコストがかかることが知られている乗算演算数を著しく削減する。
我々はMAPIをPCAベースの画像再構成やグラフベースのランキングアルゴリズムに適用する。
RPIと比較すると、MAPIは通常、より高速に収束するだけでなく、優れたパフォーマンスを提供する。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Deflated Dynamics Value Iteration [17.718445089667945]
値関数の計算を高速化するために, DDVI (Deflated Dynamics Value Iteration) を提案する。
DDVI は行列分割法と行列デフレレーション法を用いて、遷移行列 $mathcalPpi$ の上位$s$支配固有構造を効果的に除去する。
このことが$tildeO(gammak |lambda_s+1$is $(s+1)$-the largest eigen value of the dynamics matrix につながることを証明している。
論文 参考訳（メタデータ） (2024-07-15T06:07:05Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Computationally Efficient Approximations for Matrix-based Renyi's
Entropy [33.72108955447222]
最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。
そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。
我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
論文 参考訳（メタデータ） (2021-12-27T14:59:52Z) - Efficient Matrix-Free Approximations of Second-Order Information, with
Applications to Pruning and Optimization [16.96639526117016]
Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。
これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
論文 参考訳（メタデータ） (2021-07-07T17:01:34Z) - Multiplying Matrices Without Multiplying [0.0]
行列の乗算は機械学習における最も基本的で計算集約的な操作の1つである。
本稿では,既存の手法を大幅に上回る学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-21T05:08:54Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。