論文の概要: Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

• arxiv url: http://arxiv.org/abs/2605.09755v1
• Date: Sun, 10 May 2026 21:05:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.406023
• Title: Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
• Title（参考訳）: 高速スケッチによる低域近似の高速化
• Authors: Shabarish Chenakkod, Michał Dereziński,
• Abstract要約: 高速スケッチによるパワーメソッドの高速化のためのアルゴリズム的・理論的枠組みを開発する。 我々のフレームワークは、特異値分解、低ランク因子化、およびNystrm近似の単純かつ証明可能な方法をもたらす。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.
• Abstract（参考訳）: パワーメソッドは、低ランク行列近似を用いてデータから最上位の主成分を抽出する最も基本的なツールの1つである。 しかし、目標ランクが大きくなると、この手順に関連する行列乗算のコストが大きなボトルネックとなる。 ランダム化線形代数において一般的なパラダイムである高速スケッチによるパワーメソッドの高速化のためのアルゴリズム的・理論的枠組みを開発する。 本フレームワークは, 特異値分解, 低ランク因子分解, および Nyström 近似の簡易かつ証明可能な手法を導出し, ベンチマーク問題に対して高い数値性能を実現する。 我々の分析における重要な新規性は、従来の議論よりもパワーメソッド保証の一般化においてより柔軟な高速スケッチ法の特性である正規化スペクトル近似を使うことである。

関連論文リスト

• Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem [6.938695246282628]
  Split-Mergeはスペクトル知識を必要とせずに加速収束を達成するアルゴリズムである。 効率性とスケーラビリティの両面で、最先端のメソッドを一貫して上回ります。 従来のパワーメソッドよりも$boldsymbol10times$のスピードアップを実現している。
  論文  参考訳（メタデータ） (2025-01-25T08:37:17Z)
• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  本稿では,カーネルサポートベクトルマシン(SVM)に特化して設計された革新的な手法を提案する。 イテレーション毎のイテレーションを高速化するだけでなく、従来のSFO技術と比較して収束度も向上する。 実験の結果,提案アルゴリズムはSFO法のスケーラビリティを維持できるだけでなく,潜在的に超越していることが示された。
  論文  参考訳（メタデータ） (2024-07-30T17:03:19Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。 まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
  論文  参考訳（メタデータ） (2022-08-11T22:27:22Z)
• Practical and Fast Momentum-Based Power Methods [7.223413715110717]
  Power Methodは、ストリーミングPCA、スペクトルクラスタリング、低ランク行列近似などの機械学習タスクに広く応用された古典的アルゴリズムである。 運動量に基づくスキームは、パワーメソッドの高速化に使用することができるが、既存のアルゴリズムで最適収束率を達成するには、実行時に利用できない追加のスペクトル情報に批判的に依存する。 遅延モーメント電力法 (DMPower) とストリーミング変種 (DMStream) と呼ぶ新しいモーメントベース電力法を提案する。 我々の手法は不正確なデフレを生かし、極端に最適に近い収束を達成することができる。
  論文  参考訳（メタデータ） (2021-08-20T16:54:12Z)
• Acceleration Methods [57.202881673406324]
  まず2次最適化問題を用いて加速法を2つ導入する。 我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。 我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
  論文  参考訳（メタデータ） (2021-01-23T17:58:25Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Average-case Acceleration Through Spectral Density Estimation [35.01931431231649]
  ランダム2次問題の平均ケース解析のためのフレームワークを開発する。 この分析で最適なアルゴリズムを導出する。 我々は, 均一性, マルテンコ・パストゥル, 指数分布の明示的アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-02-12T01:44:26Z)

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

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