論文の概要: Optimal Exact Matrix Completion Under new Parametrization
- arxiv url: http://arxiv.org/abs/2002.02431v3
- Date: Sat, 5 Mar 2022 00:32:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 09:52:01.979478
- Title: Optimal Exact Matrix Completion Under new Parametrization
- Title（参考訳）: 新しいパラメトリゼーションによる最適エクササイズ行列補完
- Authors: Ilqar Ramazanli, Barnabas Poczos
- Abstract要約: 適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。
対象行列を正確に復元する行列補完アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of exact completion for $m \times n$ sized matrix of
rank $r$ with the adaptive sampling method.
We introduce a relation of the exact completion problem with the sparsest
vector of column and row spaces (which we call \textit{sparsity-number} here).
Using this relation, we propose matrix completion algorithms that exactly
recovers the target matrix. These algorithms are superior to previous works in
two important ways. First, our algorithms exactly recovers $\mu_0$-coherent
column space matrices by probability at least $1 - \epsilon$ using much smaller
observations complexity than $\mathcal{O}(\mu_0 rn
\mathrm{log}\frac{r}{\epsilon})$ the state of art. Specifically, many of the
previous adaptive sampling methods require to observe the entire matrix when
the column space is highly coherent. However, we show that our method is still
able to recover this type of matrices by observing a small fraction of entries
under many scenarios. Second, we propose an exact completion algorithm, which
requires minimal pre-information as either row or column space is not being
highly coherent. At the end of the paper, we provide experimental results that
illustrate the strength of the algorithms proposed here.
- Abstract（参考訳）: 適応サンプリング法を用いて、$m \times n$ の階数$r$の行列の正確な完備化の問題を研究する。
列空間と行空間の最もスパースなベクトル(ここでは \textit{sparsity-number} と呼ぶ)との完全完備問題の関係を導入する。
この関係を用いて,ターゲット行列を正確に復元する行列補完アルゴリズムを提案する。
これらのアルゴリズムは、以前の2つの重要な方法でより優れている。
第一に、我々のアルゴリズムは、$\mathcal{O}(\mu_0 rn \mathrm{log}\frac{r}{\epsilon})$よりもはるかに小さな観測量を用いて、確率1 - \epsilon$で$\mu_0$-コヒーレントな列空間行列を正確に復元する。
特に、以前の適応サンプリング法の多くは、カラム空間が高度にコヒーレントであるときに行列全体を観察する必要がある。
しかし,本手法では,多くのシナリオにおいて少数のエントリを観測することで,このタイプの行列を復元できることを示す。
第2に,行あるいは列空間が高度に整合していないため,最小限の事前情報を必要とする完全補完アルゴリズムを提案する。
論文の最後に,本論文で提案するアルゴリズムの強みを示す実験結果を示す。
関連論文リスト
- Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
政策改善と政策評価の段階を交互に行うモデルフリー学習アルゴリズムであるLoRa-PI(Low-Rank Policy Iteration)を提案する。
LoRa-PIは$widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$サンプルを使用して$varepsilon$-optimal Policyを学習する。
論文 参考訳（メタデータ） (2024-10-30T20:22:17Z) - 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Nonparametric Matrix Estimation with One-Sided Covariates [5.457150493905064]
mathbbRntimes m$ のデータセット $X をスパシティ $p$ で観測する行列推定のタスクを考える。
我々は,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析を提供する。
論文 参考訳（メタデータ） (2021-10-26T19:11:45Z) - Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。
シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
論文 参考訳（メタデータ） (2021-10-15T09:27:50Z) - Unique sparse decomposition of low rank matrices [17.037882881652617]
低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。
我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
論文 参考訳（メタデータ） (2021-06-14T20:05:59Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Solving the Robust Matrix Completion Problem via a System of Nonlinear
Equations [28.83358353043287]
低階行列 $L_*$ とスパース行列 $S_*$ をそれらの和 $M=L_*+S_*inmathbbRmtimes n$ の不完全観測から回復することを目的としたロバスト行列完備化の問題を考える。
このアルゴリズムは並列性が高く、大規模な問題に適している。
数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
論文 参考訳（メタデータ） (2020-03-24T17:28:15Z) - Rank $2r$ iterative least squares: efficient recovery of ill-conditioned
low rank matrices from few entries [4.230158563771147]
低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。
我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
論文 参考訳（メタデータ） (2020-02-05T16:20:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。