Fugu-MT 論文翻訳(概要): Low-rank Matrix Recovery With Unknown Correspondence

論文の概要: Low-rank Matrix Recovery With Unknown Correspondence

arxiv url: http://arxiv.org/abs/2110.07959v2
Date: Mon, 18 Oct 2021 03:10:41 GMT
ステータス: 処理完了
システム内更新日: 2021-10-19 12:11:43.095666
Title: Low-rank Matrix Recovery With Unknown Correspondence
Title（参考訳）: 未知の対応による低ランク行列復元
Authors: Zhiwei Tang, Tsung-Hui Chang, Xiaojing Ye, Hongyuan Zha
Abstract要約: 我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
参考スコア（独自算出の注目度）: 62.634051913953485
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study a matrix recovery problem with unknown correspondence: given the observation matrix $M_o=[A,\tilde P B]$, where $\tilde P$ is an unknown permutation matrix, we aim to recover the underlying matrix $M=[A,B]$. Such problem commonly arises in many applications where heterogeneous data are utilized and the correspondence among them are unknown, e.g., due to privacy concerns. We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. We propose an algorithm, $\text{M}^3\text{O}$ (Matrix recovery via Min-Max Optimization) which recasts this combinatorial problem as a continuous minimax optimization problem and solves it by proximal gradient with a Max-Oracle. $\text{M}^3\text{O}$ can also be applied to a more general scenario where we have missing entries in $M_o$ and multiple groups of data with distinct unknown correspondence. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $\text{M}^3\text{O}$ achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.
Abstract（参考訳）: 観測行列が $M_o=[A,\tilde P B]$ ならば、$\tilde P$ は未知の置換行列であり、基礎となる行列が $M=[A,B]$ である。このような問題は、例えばプライバシー上の懸念から、異種データが利用され、それらの間の対応が不明な多くのアプリケーションで一般的に発生する。我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。我々は,この組合せ問題を連続的ミニマックス最適化問題として再キャストし,max-oracle による近位勾配を用いて解くアルゴリズム $\text{m}^3\text{o}$ (min-max 最適化による行列リカバリ)を提案する。また、$\text{m}^3\text{o}$ は、$m_o$ のエントリが不足しているより一般的なシナリオにも適用できます。シミュレーションデータ、MovieLens 100Kデータセット、Yale Bデータベースの実験によると、$\text{M}^3\text{O}$は、いくつかのベースラインで最先端のパフォーマンスを実現し、高精度で地上の真実対応を回復できる。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文参考訳（メタデータ） (2024-08-27T18:28:31Z)
One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文参考訳（メタデータ） (2023-06-06T22:35:16Z)
Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文参考訳（メタデータ） (2022-09-30T04:15:44Z)
Unique sparse decomposition of low rank matrices [17.037882881652617]
低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
論文参考訳（メタデータ） (2021-06-14T20:05:59Z)
Non-Convex Compressed Sensing with Training Data [0.0]
我々は、行列$A$上の比較的少数の仮定を持つ1層の線形ニューラルネットワークの範囲において高い確率で元の問題$Ax = b$の解決策を見つける。本稿では、適切な初期値の代わりに、圧縮センシング問題に関連する追加のトレーニング問題 $Ax = B_l$, $l=1, dots, p$ が提供される代替案を検討する。
論文参考訳（メタデータ） (2021-01-20T20:30:59Z)
The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文参考訳（メタデータ） (2020-05-22T16:55:01Z)
Optimal Exact Matrix Completion Under new Parametrization [0.0]
適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。対象行列を正確に復元する行列補完アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-06T18:31:47Z)

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

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