論文の概要: Fast and accurate optimization on the orthogonal manifold without retraction

• arxiv url: http://arxiv.org/abs/2102.07432v1
• Date: Mon, 15 Feb 2021 10:12:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-02-17 07:20:19.722394
• Title: Fast and accurate optimization on the orthogonal manifold without retraction
• Title（参考訳）: 引き込みのない直交多様体の高速かつ正確な最適化
• Authors: Pierre Ablin and Gabriel Peyr\'e
• Abstract要約: 本稿では,リトラクションを伴わないランディングアルゴリズムを提案する。 このアルゴリズムは多様体上に留まることを制約されないが、その進化はポテンシャルエネルギーによって駆動される。 着陸アルゴリズムの1つは行列乗算のみを伴っているため、リトラクションアルゴリズムに比べて安価である。
• 参考スコア（独自算出の注目度）: 7.887285735878797
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of minimizing a function over the manifold of orthogonal matrices. The majority of algorithms for this problem compute a direction in the tangent space, and then use a retraction to move in that direction while staying on the manifold. Unfortunately, the numerical computation of retractions on the orthogonal manifold always involves some expensive linear algebra operation, such as matrix inversion or matrix square-root. These operations quickly become expensive as the dimension of the matrices grows. To bypass this limitation, we propose the landing algorithm which does not involve retractions. The algorithm is not constrained to stay on the manifold but its evolution is driven by a potential energy which progressively attracts it towards the manifold. One iteration of the landing algorithm only involves matrix multiplications, which makes it cheap compared to its retraction counterparts. We provide an analysis of the convergence of the algorithm, and demonstrate its promises on large-scale problems, where it is faster and less prone to numerical errors than retraction-based methods.
• Abstract（参考訳）: 直交行列の多様体上の関数を最小化する問題を考える。 この問題のアルゴリズムの大半は、接空間内の方向を計算し、その後、引き込みを使用して多様体上にとどまりながらその方向に移動する。 残念なことに、直交多様体上の引き算の数値計算は常に、行列反転や行列平方根のような高価な線型代数演算を伴う。 これらの操作は、行列の次元が大きくなるとすぐに高価になる。 この制限を回避するために,リトラクションを含まないランディングアルゴリズムを提案する。 このアルゴリズムは多様体上に留まることに制約されないが、その進化は多様体に向かって徐々に引き寄せるポテンシャルエネルギーによって駆動される。 ランディングアルゴリズムの1つのイテレーションは行列乗算のみを含むため、リトラクションアルゴリズムに比べて安価である。 そこで本研究では,アルゴリズムの収束を解析し,レトラクション法よりも高速で数値誤差の少ない大規模問題に対する期待を示す。

関連論文リスト

• The Structural Complexity of Matrix-Vector Multiplication [0.10485739694839669]
  行列ベクトル乗算問題は$tildeO(n2)$プレプロセッシングと$tildeO(n2-1/d)$クエリ時間で解けることを示す。 我々の結果は、多くの応用において最初の非自明な上界が得られる。
  論文  参考訳（メタデータ） (2025-02-28T17:11:36Z)
• Riemannian coordinate descent algorithms on matrix manifolds [12.05722932030768]
  行列多様体上で計算効率の良い座標降下(CD)アルゴリズムを開発するための一般的なフレームワークを提供する。 我々は、Stiefel, Grassmann, (Generalized) hyperbolic, symplectic, and symmetric positive (semi) definite などの多様体に対するCDアルゴリズムを提案する。 我々はそれらの収束と複雑性を分析し、いくつかのアプリケーションでその効果を実証的に説明する。
  論文  参考訳（メタデータ） (2024-06-04T11:37:11Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold [16.099883128428054]
  直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。 ODCGMはベクトル空間へのプロジェクションのみを必要とする。 以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
  論文  参考訳（メタデータ） (2023-03-16T12:25:53Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Adaptive and Momentum Methods on Manifolds Through Trivializations [6.85316573653194]
  任意の多様体に対して適応法と運動量法を一般化する枠組みを導入する。 すべての微分可能多様体に対して、ほとんどすべての多様体をカバーする放射凸開集合が存在する。 本稿では,これらの手法をリトラクション付き降下手法の文脈に拡張する方法を示す。
  論文  参考訳（メタデータ） (2020-10-09T14:58:09Z)
• Dynamical perturbation theory for eigenvalue problems [0.0]
  提案アルゴリズムは,通常のレイリー=シュル・オーディンガー展開を3つの数で上回ることを示す。 また,本手法は汎用固有値ルーチンよりも行列のサイズがよい。
  論文  参考訳（メタデータ） (2020-02-28T17:13:22Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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