論文の概要: Making the Nystr\"om method highly accurate for low-rank approximations

• arxiv url: http://arxiv.org/abs/2307.05785v1
• Date: Tue, 11 Jul 2023 20:25:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-13 14:56:32.344724
• Title: Making the Nystr\"om method highly accurate for low-rank approximations
• Title（参考訳）: 低ランク近似に対するnystr\"om法の高精度化
• Authors: Jianlin Xia
• Abstract要約: 我々はNystr"om法を非対称行列や長方形行列に対して高い精度で適用するための一連の戦略を提案する。 結果として得られる方法(高速ナイストローム法と呼ばれる)は、高速なピボット戦略として、ナイストローム法(英語版)とスキンのランク-リーベリング因子化(英語版)を扱います。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Nystr\"om method is a convenient heuristic method to obtain low-rank approximations to kernel matrices in nearly linear complexity. Existing studies typically use the method to approximate positive semidefinite matrices with low or modest accuracies. In this work, we propose a series of heuristic strategies to make the Nystr\"om method reach high accuracies for nonsymmetric and/or rectangular matrices. The resulting methods (called high-accuracy Nystr\"om methods) treat the Nystr\"om method and a skinny rank-revealing factorization as a fast pivoting strategy in a progressive alternating direction refinement process. Two refinement mechanisms are used: alternating the row and column pivoting starting from a small set of randomly chosen columns, and adaptively increasing the number of samples until a desired rank or accuracy is reached. A fast subset update strategy based on the progressive sampling of Schur complements is further proposed to accelerate the refinement process. Efficient randomized accuracy control is also provided. Relevant accuracy and singular value analysis is given to support some of the heuristics. Extensive tests with various kernel functions and data sets show how the methods can quickly reach prespecified high accuracies in practice, sometimes with quality close to SVDs, using only small numbers of progressive sampling steps.
• Abstract（参考訳）: Nystr\"om法は、ほぼ線形な複雑さでカーネル行列に対する低ランク近似を得るための便利なヒューリスティック法である。 現存する研究は、通常、正の半定値行列を低いあるいは控えめな精度で近似するためにこの方法を用いる。 本研究ではNystr\"om法を非対称行列および/または長方行列に対して高い精度に到達させるための一連のヒューリスティック戦略を提案する。 結果として得られる方法(高速Nystr\"om method)は、進行的交互方向精錬プロセスにおいて高速なピボット戦略として、Nystr\"om methodとskinny rank-revealing factorizationを扱います。 ランダムに選択された列の小さなセットから始まる行と列のピボットを交互に行い、所望のランクや精度に到達するまでサンプルの数を適応的に増加させる。 シュア補体のプログレッシブサンプリングに基づく高速部分集合更新戦略が提案され,改良プロセスの高速化が図られた。 効率的なランダム化精度制御も提供する。 関連する精度と特異値解析は、いくつかのヒューリスティックをサポートするために与えられる。 様々なカーネル関数とデータセットによる広範囲なテストは、いくつかのプログレッシブサンプリングステップのみを使用して、時にはSVDに近い品質で、メソッドが事前に規定された高い精度に迅速に到達できることを示す。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  非定常データストリームから非線形関数のパラメータを推定するための効率的なオンライン近似ベイズ推定アルゴリズムを提案する。 この方法は拡張カルマンフィルタ (EKF) に基づいているが、新しい低ランク+斜角行列分解法を用いている。 変分推論に基づく手法とは対照的に,本手法は完全に決定論的であり,ステップサイズチューニングを必要としない。
  論文  参考訳（メタデータ） (2023-05-31T03:48:49Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  本稿では,分散動的安全スクリーニング(DDSS)手法を提案し,共有メモリアーキテクチャと分散メモリアーキテクチャにそれぞれ適用する。 提案手法は, 線形収束率を低次複雑度で達成し, 有限個の繰り返しにおいてほとんどすべての不活性な特徴をほぼ確実に除去できることを示す。
  論文  参考訳（メタデータ） (2022-04-23T02:45:55Z)
• Linear Time Kernel Matrix Approximation via Hyperspherical Harmonics [3.24890820102255]
  機械学習のカーネル手法で発生する行列の低ランク近似を構築するための新しい手法を提案する。 提案手法では,基礎となるカーネル関数の解析的拡張をデータ依存圧縮ステップと組み合わせて,近似をさらに最適化する。 実験の結果,提案手法は,与えられたランクの精度と,与えられた精度の計算時間の両方に関して,カーネル,次元,データセットにまたがってよく用いられるNystrom法と比較した。
  論文  参考訳（メタデータ） (2022-02-08T05:19:39Z)
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling [0.9806910643086042]
  本稿では,勾配降下アルゴリズムの平均化法により推定されるパラメータのベクトルに対するオンライン推論法を提案する。 我々のアプローチはオンラインデータで完全に運用されており、機能中心極限定理によって厳格に支えられている。
  論文  参考訳（メタデータ） (2021-06-06T15:38:37Z)
• A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples [0.0]
  低ランク行列補完のための反復アルゴリズムを提案する。 ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
  論文  参考訳（メタデータ） (2021-06-03T20:31:00Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Gauss-Legendre Features for Gaussian Process Regression [7.37712470421917]
  カーネル行列の低階近似を用いてガウス過程の回帰をスケールアップするためのガウス・レーゲンドル二次法を提案する。 この手法はよく知られたランダムなフーリエ特徴法に触発され、数値積分による低ランク近似も構築する。
  論文  参考訳（メタデータ） (2021-01-04T18:09:25Z)
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning [27.775096437736973]
  独立サンプリング方式は、一般に使用されている一様サンプリング方式の性能を向上させる傾向にあることを示す。 我々の新しい分析は、サンプリングの速度が今までで最高のものより速いことも示しています。
  論文  参考訳（メタデータ） (2020-09-14T16:41:32Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。 一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
  論文  参考訳（メタデータ） (2020-07-13T17:39:35Z)
• Path Sample-Analytic Gradient Estimators for Stochastic Binary Networks [78.76880041670904]
  二進的アクティベーションや二進的重みを持つニューラルネットワークでは、勾配降下によるトレーニングは複雑である。 そこで本研究では,サンプリングと解析近似を併用した新しい推定法を提案する。 勾配推定において高い精度を示し、深部畳み込みモデルにおいてより安定かつ優れた訓練を行うことを示す。
  論文  参考訳（メタデータ） (2020-06-04T21:51:21Z)

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

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