Fugu-MT 論文翻訳(概要): Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky

論文の概要: Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky

arxiv url: http://arxiv.org/abs/2410.03969v1
Date: Fri, 4 Oct 2024 23:21:37 GMT
ステータス: 処理完了
システム内更新日: 2024-11-02 15:00:17.041528
Title: Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky
Title（参考訳）: エンブレス拒絶:無作為なランダムピボットColeskyによるカーネル行列近似
Authors: Ethan N. Epperly, Joel A. Tropp, Robert J. Webber,
Abstract要約: ランダムピボットされたコレスキー (RPCholesky) は、少数の列を用いて正半有限行列の低ランク近似を構築するアルゴリズムである。本稿では,ブロック行列計算とリジェクションサンプリングを併用したRPCholeskyの高速化版を開発し,元のアルゴリズムの実行を効率的にシミュレートする。
参考スコア（独自算出の注目度）: 0.6554326244334868
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Randomly pivoted Cholesky (RPCholesky) is an algorithm for constructing a low-rank approximation of a positive-semidefinite matrix using a small number of columns. This paper develops an accelerated version of RPCholesky that employs block matrix computations and rejection sampling to efficiently simulate the execution of the original algorithm. For the task of approximating a kernel matrix, the accelerated algorithm can run over $40\times$ faster. The paper contains implementation details, theoretical guarantees, experiments on benchmark data sets, and an application to computational chemistry.
Abstract（参考訳）: ランダムピボットされたコレスキー (RPCholesky) は、少数の列を用いて正半有限行列の低ランク近似を構築するアルゴリズムである。本稿では,ブロック行列計算とリジェクションサンプリングを併用したRPCholeskyの高速化版を開発し,元のアルゴリズムの実行を効率的にシミュレートする。カーネル行列を近似するタスクでは、加速されたアルゴリズムは40\times$より高速に動作することができる。本稿では,実装の詳細,理論的保証,ベンチマークデータセットの実験,計算化学への応用について述べる。

関連論文リスト

Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。計算のためのランダム化アルゴリズムを2つ開発した。提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
論文参考訳（メタデータ） (2024-02-13T00:02:05Z)
An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-30T15:57:14Z)
Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-11T07:28:35Z)
Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文参考訳（メタデータ） (2022-10-21T15:56:13Z)
Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations [2.7796535578871575]
ランダムにピボットされた部分チョレスキーアルゴリズム(RPCholesky)は、N x N の正準有限(psd)行列の階数-k近似を計算する。 RPCholeskyの単純さ、有効性、堅牢性は、科学計算や機械学習アプリケーションでの使用を強く支持している。
論文参考訳（メタデータ） (2022-07-13T19:51:24Z)
Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文参考訳（メタデータ） (2021-12-17T17:04:34Z)
Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
論文参考訳（メタデータ） (2021-12-03T14:39:10Z)
Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
論文参考訳（メタデータ） (2021-08-08T05:28:06Z)
Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach [4.710916891482697]
擬逆は行列逆の一般化であり、機械学習で広く利用されている。 FastPIはスパース行列に対する新たなインクリメンタル特異値分解法(SVD)である。我々は,FastPIが精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示す。
論文参考訳（メタデータ） (2020-11-09T07:47:10Z)
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文参考訳（メタデータ） (2020-02-03T16:17:50Z)

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