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

• arxiv url: http://arxiv.org/abs/2207.06503v1
• Date: Wed, 13 Jul 2022 19:51:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-15 14:55:53.919011
• Title: Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
• Title（参考訳）: ランダムにピボットされたcholesky: 入力評価の少ないカーネル行列の実用的近似
• Authors: Yifan Chen, Ethan N. Epperly, Joel A. Tropp, Robert J. Webber
• Abstract要約: ランダムピボットされたチョレスキー (RPCholesky) は、N x N の正半定値 (psd) 行列のランク k 近似を計算する自然なアルゴリズムである。 本稿では,その実験的および理論的挙動について,初めて真剣な調査を行った。 このアルゴリズムの単純さ、有効性、堅牢性は、科学計算や機械学習アプリケーションでの利用を強く支持する。
• 参考スコア（独自算出の注目度）: 11.956729651227882
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomly pivoted Cholesky (RPCholesky) is a natural algorithm for computing a rank-k approximation of an N x N positive semidefinite (psd) matrix. RPCholesky can be implemented with just a few lines of code. It requires only (k+1)N entry evaluations and O(k^2 N) additional arithmetic operations. This paper offers the first serious investigation of its experimental and theoretical behavior. Empirically, RPCholesky matches or improves on the performance of alternative algorithms for low-rank psd approximation. Furthermore, RPCholesky provably achieves near-optimal approximation guarantees. The simplicity, effectiveness, and robustness of this algorithm 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は、低ランクpsd近似のための代替アルゴリズムの性能を実証的に比較または改善する。 さらに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)

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

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