論文の概要: Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach

• arxiv url: http://arxiv.org/abs/2011.04235v1
• Date: Mon, 9 Nov 2020 07:47:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-28 01:34:36.887429
• Title: Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach
• Title（参考訳）: スパース行列再構成とインクリメンタルアプローチによる高速・高精度擬似逆解析
• Authors: Jinhong Jung and Lee Sael
• Abstract要約: 擬逆は行列逆の一般化であり、機械学習で広く利用されている。 FastPIはスパース行列に対する新たなインクリメンタル特異値分解法(SVD)である。 我々は,FastPIが精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示す。
• 参考スコア（独自算出の注目度）: 4.710916891482697
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How can we compute the pseudoinverse of a sparse feature matrix efficiently and accurately for solving optimization problems? A pseudoinverse is a generalization of a matrix inverse, which has been extensively utilized as a fundamental building block for solving linear systems in machine learning. However, an approximate computation, let alone an exact computation, of pseudoinverse is very time-consuming due to its demanding time complexity, which limits it from being applied to large data. In this paper, we propose FastPI (Fast PseudoInverse), a novel incremental singular value decomposition (SVD) based pseudoinverse method for sparse matrices. Based on the observation that many real-world feature matrices are sparse and highly skewed, FastPI reorders and divides the feature matrix and incrementally computes low-rank SVD from the divided components. To show the efficacy of proposed FastPI, we apply them in real-world multi-label linear regression problems. Through extensive experiments, we demonstrate that FastPI computes the pseudoinverse faster than other approximate methods without loss of accuracy. %and uses much less memory compared to full-rank SVD based approach. Results imply that our method efficiently computes the low-rank pseudoinverse of a large and sparse matrix that other existing methods cannot handle with limited time and space.
• Abstract（参考訳）: 最適化問題を解くためにスパース特徴行列の擬逆を効率的に正確に計算する方法 pseudoinverseは行列逆の一般化であり、機械学習における線形システムを解くための基本的な構築ブロックとして広く利用されている。 しかし、擬似逆の正確な計算は、その要求される時間的複雑さのために非常に時間がかかり、大きなデータに適用されることが制限される。 本稿では,スパース行列に対する新たなインクリメンタル特異値分解法であるFastPI(Fast Pseudo Inverse)を提案する。 多くの実世界の特徴行列がスパースで高度に歪んでいるという観測に基づいて、FastPIは特徴行列を並べ替えて分割し、分割されたコンポーネントから低ランクSVDを漸進的に計算する。 提案手法の有効性を示すために,実世界の多ラベル線形回帰問題に適用する。 実験により,FastPIは精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示した。 %と、フルランクSVDベースのアプローチに比べてはるかに少ないメモリを使用する。 その結果,既存の手法では時間と空間が制限されない大小行列の低ランク擬似逆数を効率的に計算できることが示唆された。

関連論文リスト

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Optimized Sparse Matrix Operations for Reverse Mode Automatic Differentiation [3.72826300260966]
  本稿では,PyTorch のための CSR ベースのスパース行列ラッパーの実装について述べる。 また,結果のスパースカーネルを最適化に応用し,実装や性能測定の容易さを高密度カーネルと比較した。
  論文  参考訳（メタデータ） (2022-12-10T00:46:51Z)
• RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations [56.59168541623729]
  トレーニンググラフニューラルネットワーク(GNN)は、疎グラフベースの操作がハードウェアによって加速することが難しいため、時間を要する。 我々は,サンプリングに基づく近似による時間的複雑性を低減するために,計算精度のトレードオフを検討する。 本稿では,GNNを近似演算でトレーニングする可能性を初めて示すランダム化スパース計算を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:25:33Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• 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)
• Fast Differentiable Matrix Square Root [65.67315418971688]
  微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。 前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。 もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
  論文  参考訳（メタデータ） (2022-01-21T12:18:06Z)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。 そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。 我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
  論文  参考訳（メタデータ） (2021-12-27T14:59:52Z)
• Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication [0.0]
  カーネル行列は一般に密度が高く大規模である。特徴空間の次元によっては、合理的な時間における全てのエントリの計算さえも難しい課題となる。 そこで我々は,ANOVAカーネルを用いて低次元の特徴空間に基づいて複数のカーネルを構築し,行列ベクトル積を実現する高速アルゴリズムを提案する。 特徴グループ化アプローチに基づいて,カーネルリッジ回帰と事前条件付き共役勾配解法を選択する学習手法に,高速な行列ベクトル積を組み込む方法を示す。
  論文  参考訳（メタデータ） (2021-11-19T10:29:39Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Fast Coherent Point Drift [4.369046007546103]
  コヒーレント点ドリフト(CPD)は、非剛性点集合登録のための古典的な方法である。 単純な対応する制約を導入することで、PDの高速な実装を開発する。 3次元点雲データによる実験結果から,本手法は登録プロセスの負担を大幅に軽減できることが示された。
  論文  参考訳（メタデータ） (2020-06-11T09:35:23Z)
• Fast Generalized Matrix Regression with Applications in Machine Learning [46.79740387890322]
  スケッチ技術を用いてGMR問題を効率的に解く高速一般化行列回帰アルゴリズム(Fast GMR)を提案する。 我々は,Fast GMRアルゴリズムを対称正定値行列近似と単一パス特異値分解に適用する。
  論文  参考訳（メタデータ） (2019-12-27T07:03:37Z)

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

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