論文の概要: 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つのイテレーションは行列乗算のみを含むため、リトラクションアルゴリズムに比べて安価である。
そこで本研究では,アルゴリズムの収束を解析し,レトラクション法よりも高速で数値誤差の少ない大規模問題に対する期待を示す。
関連論文リスト
- Learning the Positions in CountSketch [56.22648269865784]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - A fast Multiplicative Updates algorithm for Non-negative Matrix
Factorization [3.553810309063734]
本稿では,各サブプロブレムに対してヘッセン行列のより厳密な上界を構築することにより,乗法更新アルゴリズムの改善を提案する。
コンバージェンスはまだ保証されており、我々は実際に合成と実世界の両方のデータセットで、提案したfastMUアルゴリズムが通常の乗算更新アルゴリズムよりも数桁高速であることを示す。
論文 参考訳（メタデータ） (2023-03-31T12:09:36Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms
for Optimization under Orthogonality Constraints [8.59102802625914]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合、分散と還元のアルゴリズムも検討する。
論文 参考訳（メタデータ） (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) - Learning to Guide Random Search [111.71167792453473]
我々は、潜在低次元多様体上の高次元関数の微分自由最適化を考える。
最適化を行いながらこの多様体を学習するオンライン学習手法を開発した。
本研究では,連続最適化ベンチマークと高次元連続制御問題について実験的に評価する。
論文 参考訳（メタデータ） (2020-04-25T19:21:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。