論文の概要: Dynamical perturbation theory for eigenvalue problems

• arxiv url: http://arxiv.org/abs/2002.12872v3
• Date: Wed, 11 Mar 2020 15:39:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 07:41:52.391033
• Title: Dynamical perturbation theory for eigenvalue problems
• Title（参考訳）: 固有値問題に対する動的摂動理論
• Authors: Maseim Kenmoe, Matteo Smerlak, Anton Zadorin
• Abstract要約: 提案アルゴリズムは,通常のレイリー=シュル・オーディンガー展開を3つの数で上回ることを示す。 また,本手法は汎用固有値ルーチンよりも行列のサイズがよい。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many problems in physics, chemistry and other fields are perturbative in nature, i.e. differ only slightly from related problems with known solutions. Prominent among these is the eigenvalue perturbation problem, wherein one seeks the eigenvectors and eigenvalues of a matrix with small off-diagonal elements. Here we introduce a novel iterative algorithm to compute these eigenpairs based on fixed-point iteration for an algebraic equation in complex projective space. We show from explicit and numerical examples that our algorithm outperforms the usual Rayleigh-Schr\"odinger expansion on three counts. First, since it is not defined as a power series, its domain of convergence is not a priori confined to a disk in the complex plane; we find that it indeed usually extends beyond the standard perturbative radius of convergence. Second, it converges at a faster rate than the Rayleigh-Schr\"odinger expansion, i.e. fewer iterations are required to reach a given precision. Third, the (time- and space-) algorithmic complexity of each iteration does not increase with the order of the approximation, allowing for higher precision computations. Because this complexity is merely that of matrix multiplication, our dynamical scheme also scales better with the size of the matrix than general-purpose eigenvalue routines such as the shifted QR or divide-and-conquer algorithms. Whether they are dense, sparse, symmetric or unsymmetric, we confirm that dynamical diagonalization quickly outpaces LAPACK drivers as the size of matrices grows; for the computation of just the dominant eigenvector, our method converges order of magnitudes faster than the Arnoldi algorithm implemented in ARPACK.
• Abstract（参考訳）: 物理学、化学、その他の分野における多くの問題は自然界において摂動的であり、既知の解に関する関連する問題とわずかに異なる。 固有値摂動問題(英: eigenvalue perturbation problem)は、小さなオフ対角要素を持つ行列の固有ベクトルと固有値を求める問題である。 本稿では,複素射影空間における代数方程式に対する不動点反復に基づいて,これらの固有ペアを計算するための新しい反復アルゴリズムを提案する。 明示的および数値的な例から、我々のアルゴリズムは3つの数に対して通常のレイリー=シュルンガー展開よりも優れていることを示す。 第一に、それは級数として定義されていないので、その収束領域は複素平面内のディスクに制限された前もってはいない。 第二に、レイリー=シュル(rayleigh-schr\"odinger)の展開よりも速い速度で収束する。 第3に、各イテレーションの(時間的および空間的)アルゴリズムの複雑さは近似の順序で増加せず、より高精度な計算が可能となる。 この複雑さは単に行列乗算のものであるため、我々の動的スキームは、シフトしたQRや除算アルゴリズムのような汎用固有値ルーチンよりも行列のサイズでスケールする。 それらは密度、スパース、対称、非対称であっても、行列の大きさが大きくなるにつれて、動的対角化はラパックドライバを急速に上回り、優占固有ベクトルの計算ではarpackで実装されたアルノルディアルゴリズムよりも桁違いに収束する。

関連論文リスト

• A fixed-point algorithm for matrix projections with applications in quantum information [7.988085110283119]
  このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。 量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
  論文  参考訳（メタデータ） (2023-12-22T11:16:11Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• On algorithmically boosting fixed-point computations [0.9790236766474201]
  アルゴリズムブースティング(英: Algorithmic boosting)は、反復写像の(長期の)平均を取ることによって固定点を計算する原理である。 本研究では,アルゴリズムの高速化により,収束速度の指数的高速化が実現可能であることを示す。
  論文  参考訳（メタデータ） (2023-04-04T07:26:50Z)
• Low-Rank Updates of Matrix Square Roots [7.832944895330117]
  行列平方根と逆平方根演算を考える。 行列に対する低階摂動が与えられたとき、(逆)平方根に対する低階近似補正が存在すると論じる。 次に、その方程式に対する低ランク解をどのように計算するかについて議論する。
  論文  参考訳（メタデータ） (2022-01-31T12:05:33Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Fast and accurate optimization on the orthogonal manifold without retraction [7.887285735878797]
  本稿では,リトラクションを伴わないランディングアルゴリズムを提案する。 このアルゴリズムは多様体上に留まることを制約されないが、その進化はポテンシャルエネルギーによって駆動される。 着陸アルゴリズムの1つは行列乗算のみを伴っているため、リトラクションアルゴリズムに比べて安価である。
  論文  参考訳（メタデータ） (2021-02-15T10:12:05Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration [4.162663632560141]
  雑音正の半定値行列から第1主固有ベクトルを復元するコーン投影パワーアルゴリズムを提案する。 シミュレーションおよび実データに関する数値実験により,本手法は通常の電力と疎結合な主成分分析アルゴリズムと比較して,実行時間と誤差が短いことを示す。
  論文  参考訳（メタデータ） (2020-05-15T15:02:24Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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