論文の概要: Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation

• arxiv url: http://arxiv.org/abs/2110.00053v1
• Date: Thu, 30 Sep 2021 19:17:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-04 14:48:28.426258
• Title: Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation
• Title（参考訳）: スティフェル多様体上のスパース2次最適化と置換同期への応用
• Authors: Florian Bernard, Daniel Cremers, Johan Thunberg
• Abstract要約: 二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 71.27989298860481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. Optimisation problems on the Stiefel manifold occur for example in spectral relaxations of various combinatorial problems, such as graph matching, clustering, or permutation synchronisation. Although sparsity is a desirable property in such settings, it is mostly neglected in spectral formulations since existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. We fill this gap and propose a simple yet effective sparsity-promoting modification of the Orthogonal Iteration algorithm for finding the dominant eigenspace of a matrix. By doing so, we can guarantee that our method finds a Stiefel matrix that is globally optimal with respect to the quadratic objective function, while in addition being sparse. As a motivating application we consider the task of permutation synchronisation, which can be understood as a constrained clustering problem that has particular relevance for matching multiple images or 3D shapes in computer vision, computer graphics, and beyond. We demonstrate that the proposed approach outperforms previous methods in this domain.
• Abstract（参考訳）: 二次目的函数を最大化(あるいは最小化)するスティーフェル多様体上のスパース行列(単位長さの相互直交列を持つ行列)を求める非凸最適化問題に対処する。 スティーフェル多様体上の最適化問題は、例えばグラフマッチング、クラスタリング、置換同期のような様々な組合せ問題のスペクトル緩和において発生する。 このような環境ではスパーシティは望ましい性質であるが、既存の解法、例えば固有値分解に基づく解法ではスパーシティを考慮できないが、グローバル最適性保証を維持しているため、スペクトル公式では無視されることが多い。 我々はこのギャップを埋め、行列の優性固有空間を見つけるための直交反復アルゴリズムの単純かつ効果的なスパルシリティ・プロモーティング修正を提案する。 これにより、この手法は二次目的関数に対してグローバルに最適であるスタイフェル行列を見つけると同時に、スパースであることを保証することができる。 モチベーションアプリケーションとして、コンピュータビジョンやコンピュータグラフィックスなどにおいて、複数の画像や3次元形状のマッチングに特に関連する制約付きクラスタリング問題として理解することができる、置換同期のタスクを考える。 提案手法が従来の手法よりも優れていることを示す。

関連論文リスト

• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。 本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。 さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
  論文  参考訳（メタデータ） (2024-02-22T05:48:54Z)
• Diff-PCR: Diffusion-Based Correspondence Searching in Doubly Stochastic Matrix Space for Point Cloud Registration [35.82753072083472]
  最先端の手法では、ソリューションを洗練させるためにRAFTのような反復的な更新が採用されている。 本稿では,最適マッチング行列の探索を予測するために,Denoising Diffusion Modelを利用する新しい手法を提案する。 提案手法は,オンラインバックボーンやホワイトノイズによって提供される任意の初期マッチング行列から検索を開始することで,柔軟性を提供する。
  論文  参考訳（メタデータ） (2023-12-31T09:24:28Z)
• Kernelized multi-graph matching [0.0]
  本稿では,グラフの属性とエッジの両方を扱う,新しいカーネル化されたマルチグラフマッチング手法を提案する。 結果の安定性の向上につながるプロジェクタをいくつか提案する。
  論文  参考訳（メタデータ） (2022-10-11T07:22:47Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  内部最適化問題が凸であるが非滑らかである場合の一階法を研究する。 本研究では, ヤコビアンの近位勾配降下と近位座標降下収率列の前方モード微分が, 正確なヤコビアンに向かって収束していることを示す。
  論文  参考訳（メタデータ） (2021-05-04T17:31:28Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints [3.179831861897336]
  低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。 我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
  論文  参考訳（メタデータ） (2020-09-22T08:59:06Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める 近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。 両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
  論文  参考訳（メタデータ） (2020-03-30T08:40:35Z)

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

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