論文の概要: Column and row subset selection using nuclear scores: algorithms and theory for Nyström approximation, CUR decomposition, and graph Laplacian reduction
- arxiv url: http://arxiv.org/abs/2407.01698v1
- Date: Mon, 1 Jul 2024 18:10:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-03 19:42:31.556523
- Title: Column and row subset selection using nuclear scores: algorithms and theory for Nyström approximation, CUR decomposition, and graph Laplacian reduction
- Title（参考訳）: 核スコアを用いたカラムと行の部分選択:Nyström近似、CUR分解、グラフラプラシアン還元のアルゴリズムと理論
- Authors: Mark Fornace, Michael Lindsey,
- Abstract要約: 我々は,高速,効率的,理論的に保証された列選択のための統一手法を開発した。
まず、カーネル近似やCUR分解といったタスクに適用可能な空間分割決定アルゴリズムを導出し、実装する。
次に、保証濃度境界を満たすランダム化スキームに依存する行列自由形式を考案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Column selection is an essential tool for structure-preserving low-rank approximation, with wide-ranging applications across many fields, such as data science, machine learning, and theoretical chemistry. In this work, we develop unified methodologies for fast, efficient, and theoretically guaranteed column selection. First we derive and implement a sparsity-exploiting deterministic algorithm applicable to tasks including kernel approximation and CUR decomposition. Next, we develop a matrix-free formalism relying on a randomization scheme satisfying guaranteed concentration bounds, applying this construction both to CUR decomposition and to the approximation of matrix functions of graph Laplacians. Importantly, the randomization is only relevant for the computation of the scores that we use for column selection, not the selection itself given these scores. For both deterministic and matrix-free algorithms, we bound the performance favorably relative to the expected performance of determinantal point process (DPP) sampling and, in select scenarios, that of exactly optimal subset selection. The general case requires new analysis of the DPP expectation. Finally, we demonstrate strong real-world performance of our algorithms on a diverse set of example approximation tasks.
- Abstract（参考訳）: カラム選択は、データサイエンス、機械学習、理論化学など、様々な分野にまたがる幅広い応用を持つ、低ランク近似の構造保存に不可欠なツールである。
本研究では,高速,効率的,理論的に保証された列選択のための統一手法を開発する。
まず、カーネル近似やCUR分解といったタスクに適用可能な空間分割決定アルゴリズムを導出し、実装する。
次に,CUR分解とグラフラプラシアンの行列関数の近似の両方に適用し,保証された濃度境界を満たすランダム化スキームに依存する行列自由形式を考案する。
重要なことに、ランダム化は、列選択に使用するスコアの計算にのみ関係しており、これらのスコアが与えられたときの選択そのものではない。
決定論的アルゴリズムと行列自由アルゴリズムの両方において、決定点プロセス(DPP)サンプリングの期待性能と、選択シナリオにおいて、真に最適なサブセット選択の性能とを比較検討する。
一般的なケースでは、DPP期待の新しい分析が必要である。
最後に,多種多様な近似タスクに対して,アルゴリズムの実際の性能を示す。
関連論文リスト
- Optimal Kernel Choice for Score Function-based Causal Discovery [92.65034439889872]
本稿では,データに最も適合する最適なカーネルを自動的に選択する,一般化スコア関数内のカーネル選択手法を提案する。
合成データと実世界のベンチマークの両方で実験を行い,提案手法がカーネル選択法より優れていることを示す。
論文 参考訳（メタデータ） (2024-07-14T09:32:20Z) - A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
中心行列および非標準行列に対するフロベニウスノルムにおける低ランク近似誤差の解析のための枠組みを提案する。
最小限の仮定の下では、期待と確率の正確な境界を導出する。
私たちの境界には、プロパティを導出し、実践的な選択を動機付けるための明確な解釈があります。
論文 参考訳（メタデータ） (2024-05-08T04:51:56Z) - Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。
カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。
我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-10-09T03:55:09Z) - Efficient Global Planning in Large MDPs via Stochastic Primal-Dual
Optimization [12.411844611718958]
提案手法は, 生成モデルに対する多数のクエリの後に, ほぼ最適ポリシーを出力することを示す。
提案手法は計算効率が高く,低次元パラメータベクトルでコンパクトに表現される単一のソフトマックスポリシーを出力する点が大きな利点である。
論文 参考訳（メタデータ） (2022-10-21T15:49:20Z) - Feature Selection via the Intervened Interpolative Decomposition and its
Application in Diversifying Quantitative Strategies [4.913248451323163]
本稿では,観測行列の各列がそれぞれの優先度や重要性を持つ補間分解(ID)を計算するための確率論的モデルを提案する。
提案したモデルを,中国A株10株を含む実世界のデータセット上で評価した。
論文 参考訳（メタデータ） (2022-09-29T03:36:56Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳（メタデータ） (2022-09-16T19:15:50Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Piecewise linear regression and classification [0.20305676256390928]
本稿では,線形予測器を用いた多変量回帰と分類問題の解法を提案する。
本論文で記述されたアルゴリズムのpython実装は、http://cse.lab.imtlucca.it/bemporad/parcで利用可能である。
論文 参考訳（メタデータ） (2021-03-10T17:07:57Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Sequential Quadratic Optimization for Nonlinear Equality Constrained
Stochastic Optimization [10.017195276758454]
この設定では、客観的関数と微分値を明示的に計算することは難しそうだと仮定する。
最先端のライン探索SQPアルゴリズムをモデルとした決定論的設定のためのアルゴリズムを提案する。
数値実験の結果は,提案手法の実用性を示すものである。
論文 参考訳（メタデータ） (2020-07-20T23:04:26Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。