論文の概要: What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?

• arxiv url: http://arxiv.org/abs/2502.07993v2
• Date: Thu, 22 May 2025 14:51:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-23 14:49:21.624601
• Title: What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
• Title（参考訳）: 低ランク近似におけるスケッチ・アンド・プレコンディションの導出は何か?逆パワーエラーか逆パワー推定か?
• Authors: Ruihan Xu, Yiping Lu,
• Abstract要約: 低ランク行列近似におけるランダム化アルゴリズムのためのスケッチ・アンド・プレコンディション・フレームワークを開発した。 提案手法は,スケッチサイズとともに少なくとも線形に向上する収束率を含む理論的保証を実現する。
• 参考スコア（独自算出の注目度）: 3.817486368952521
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomized sketching accelerates large-scale numerical linear algebra by reducing computational complexity. While the traditional sketch-and-solve approach reduces the problem size directly through sketching, the sketch-and-precondition method leverages sketching to construct a computational friendly preconditioner. This preconditioner improves the convergence speed of iterative solvers applied to the original problem, maintaining accuracy in the full space. Furthermore, the convergence rate of the solver improves at least linearly with the sketch size. Despite its potential, developing a sketch-and-precondition framework for randomized algorithms in low-rank matrix approximation remains an open challenge. We introduce the Error-Powered Sketched Inverse Iteration (EPSI) Method via run sketched Newton iteration for the Lagrange form as a sketch-and-precondition variant for randomized low-rank approximation. Our method achieves theoretical guarantees, including a convergence rate that improves at least linearly with the sketch size.
• Abstract（参考訳）: ランダム化されたスケッチは計算複雑性を減らし、大規模数値線形代数を加速する。 従来のスケッチ・アンド・ソルブ方式はスケッチによって直接問題のサイズを減少させるが、スケッチ・アンド・プレコンディショニング法はスケッチを活用して計算フレンドリーなプレコンディショナーを構築する。 このプレコンディショナーは、元の問題に適用された反復解の収束速度を改善し、全空間における精度を維持する。 さらに、分解器の収束速度はスケッチサイズとともに少なくとも直線的に向上する。 その可能性にもかかわらず、低ランク行列近似におけるランダム化アルゴリズムのためのスケッチ・アンド・プレコンディション・フレームワークの開発は未解決の課題である。 ランダム化低ランク近似のためのスケッチ・アンド・プレコンディションの変種として,ラグランジュ形式のランスケッチNewton反復によるEPSI法を提案する。 提案手法は,スケッチサイズとともに少なくとも線形に向上する収束率を含む理論的保証を実現する。

関連論文リスト

• Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees [23.614074988517864]
  本稿では,非正規化関数によって正規化あるいは凸化される最小二乗問題に対する高速近似を提案する。 スケッチされた凸や非近似問題を解くことにより、推定のための最小値率を初めて示す。
  論文  参考訳（メタデータ） (2023-11-03T09:35:01Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners [37.03247707259297]
  二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 効果的な寸法の観点からスケッチサイズを選択する際の大きな困難は、後者が実際には通常不明であるという事実にあります。
  論文  参考訳（メタデータ） (2021-04-29T04:36:41Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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