論文の概要: Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations

• arxiv url: http://arxiv.org/abs/2207.06503v6
• Date: Tue, 22 Oct 2024 00:38:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:24:30.078196
• Title: Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
• Title（参考訳）: ランダムにピボットしたColesky: エントリ評価の少ないカーネル行列の実用的な近似
• Authors: Yifan Chen, Ethan N. Epperly, Joel A. Tropp, Robert J. Webber,
• Abstract要約: ランダムにピボットされた部分チョレスキーアルゴリズム(RPCholesky)は、N x N の正準有限(psd)行列の階数-k近似を計算する。 RPCholeskyの単純さ、有効性、堅牢性は、科学計算や機械学習アプリケーションでの使用を強く支持している。
• 参考スコア（独自算出の注目度）: 2.7796535578871575
• License:
• Abstract: The randomly pivoted partial Cholesky algorithm (RPCholesky) computes a factorized rank-k approximation of an N x N positive-semidefinite (psd) matrix. RPCholesky requires only (k + 1) N entry evaluations and O(k^2 N) additional arithmetic operations, and it can be implemented with just a few lines of code. The method is particularly useful for approximating a kernel matrix. This paper offers a thorough new investigation of the empirical and theoretical behavior of this fundamental algorithm. For matrix approximation problems that arise in scientific machine learning, experiments show that RPCholesky matches or beats the performance of alternative algorithms. Moreover, RPCholesky provably returns low-rank approximations that are nearly optimal. The simplicity, effectiveness, and robustness of RPCholesky strongly support its use in scientific computing and machine learning applications.
• Abstract（参考訳）: ランダムにピボットされた部分チョレスキーアルゴリズム(RPCholesky)は、N x N の正準有限(psd)行列の階数-k近似を計算する。 RPCholesky は (k + 1) N のエントリ評価と O(k^2 N) の追加演算しか必要とせず、ほんの数行のコードで実装できる。 この方法は特にカーネルマトリックスの近似に有用である。 本論文は,本アルゴリズムの実証的および理論的挙動について,新しい知見を与えるものである。 科学機械学習で生じる行列近似問題に対して、RPCholeskyが代替アルゴリズムのパフォーマンスにマッチするか、勝っていることを示す実験がある。 さらにRPCholeskyは、ほぼ最適に近い低ランク近似を確実に返します。 RPCholeskyの単純さ、有効性、堅牢性は、科学計算や機械学習アプリケーションでの使用を強く支持している。

関連論文リスト

• Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky [0.6554326244334868]
  ランダムピボットされたコレスキー (RPCholesky) は、少数の列を用いて正半有限行列の低ランク近似を構築するアルゴリズムである。 本稿では,ブロック行列計算とリジェクションサンプリングを併用したRPCholeskyの高速化版を開発し,元のアルゴリズムの実行を効率的にシミュレートする。
  論文  参考訳（メタデータ） (2024-10-04T23:21:37Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Kernel-based estimation for partially functional linear model: Minimax rates and randomized sketches [12.799283644502882]
  本稿では,機能的共変量と高次元スカラーベクトルからなる部分関数線形モデル(PFLM)について考察する。 無限次元再生核ヒルベルト空間上で、提案されたPFLMの推定は、関数ノルムと$ell_$-ノルムの2つの混合正規化を持つ最小二乗アプローチである。
  論文  参考訳（メタデータ） (2021-10-18T06:27:59Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Denise: Deep Robust Principal Component Analysis for Positive Semidefinite Matrices [8.1371986647556]
  Deniseは、共分散行列の堅牢なPCAのためのディープラーニングベースのアルゴリズムである。 実験により、デニスは分解品質の点で最先端の性能と一致していることが示された。
  論文  参考訳（メタデータ） (2020-04-28T15:45:21Z)

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

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