論文の概要: Kissing to Find a Match: Efficient Low-Rank Permutation Representation

• arxiv url: http://arxiv.org/abs/2308.13252v1
• Date: Fri, 25 Aug 2023 08:59:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-28 14:43:35.868385
• Title: Kissing to Find a Match: Efficient Low-Rank Permutation Representation
• Title（参考訳）: 一致を見つけるためのキス: 効率的な低ランク置換表現
• Authors: Hannah Dr\"oge, Zorah L\"ahner, Yuval Bahat, Onofre Martorell, Felix Heide, Michael M\"oller
• Abstract要約: そこで本稿では,低ランク行列係数化を用いて近似し,次いで非線形性を用いて,大きな置換行列の次元性の呪いに取り組むことを提案する。 提案手法の適用性とメリットを,様々な問題に対する一連の実験を通じて実証する。
• 参考スコア（独自算出の注目度）: 33.880247068298374
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Permutation matrices play a key role in matching and assignment problems across the fields, especially in computer vision and robotics. However, memory for explicitly representing permutation matrices grows quadratically with the size of the problem, prohibiting large problem instances. In this work, we propose to tackle the curse of dimensionality of large permutation matrices by approximating them using low-rank matrix factorization, followed by a nonlinearity. To this end, we rely on the Kissing number theory to infer the minimal rank required for representing a permutation matrix of a given size, which is significantly smaller than the problem size. This leads to a drastic reduction in computation and memory costs, e.g., up to $3$ orders of magnitude less memory for a problem of size $n=20000$, represented using $8.4\times10^5$ elements in two small matrices instead of using a single huge matrix with $4\times 10^8$ elements. The proposed representation allows for accurate representations of large permutation matrices, which in turn enables handling large problems that would have been infeasible otherwise. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems that involve predicting permutation matrices, from linear and quadratic assignment to shape matching problems.
• Abstract（参考訳）: 置換行列は、分野、特にコンピュータビジョンとロボット工学において、マッチングと割り当ての問題において重要な役割を果たす。 しかし、置換行列を明示的に表現するメモリは問題のサイズと二次的に増大し、大きな問題のインスタンスを禁止している。 本研究では,大置換行列の次元性の呪いを低階行列因子分解を用いて近似し,非線形性を用いて解くことを提案する。 この目的のために、私たちは、与えられたサイズの置換行列を表現するのに必要な最小のランクを推定するために、キス数理論に頼る。 例えば、$n=20000$という2つの小さな行列で8.4\times10^5$要素で表されるサイズの問題に対して、$n=20000$という最大3ドル以下のメモリコストは、$4\times 10^8$要素の1つの巨大な行列を使う代わりに、大幅に削減される。 提案された表現は、大きな置換行列の正確な表現を可能にするが、そうでなければ実現不可能だった大きな問題を処理できる。 本研究では,線形および二次代入から形状マッチング問題まで,置換行列の予測を含む様々な問題に関する一連の実験を通じて,提案手法の適用性とメリットを示す。

関連論文リスト

• A Simple Quantum Blockmodeling with Qubits and Permutations [0.0]
  量子コンピュータにおけるブロックモデリングの解法を示す。 モデルでは、小さな量子ビットのグループの測定結果が、適合度値を示すためにマッピングされる。
  論文  参考訳（メタデータ） (2023-11-13T20:10:53Z)
• Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes [0.14454647768189902]
  本稿では、二重行列ドメインウォールと呼ばれる新しい置換符号化手法を提案する。 これは、カーネル内の二次項の数と最大絶対係数値を著しく減少させる。 また、部分置換と準非制約バイナリ最適化(QUBO)モデルへの符号化手法の適用性を実証する。
  論文  参考訳（メタデータ） (2023-08-02T09:15:30Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-09-16T18:42:21Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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