論文の概要: One-sided Matrix Completion from Two Observations Per Row

• arxiv url: http://arxiv.org/abs/2306.04049v1
• Date: Tue, 6 Jun 2023 22:35:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-08 16:59:00.975323
• Title: One-sided Matrix Completion from Two Observations Per Row
• Title（参考訳）: 1列に2つの観測から片面行列を完成させる
• Authors: Steven Cao, Percy Liang, Gregory Valiant
• Abstract要約: 行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
• 参考スコア（独自算出の注目度）: 95.87811229292056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given only a few observed entries from a low-rank matrix $X$, matrix completion is the problem of imputing the missing entries, and it formalizes a wide range of real-world settings that involve estimating missing data. However, when there are too few observed entries to complete the matrix, what other aspects of the underlying matrix can be reliably recovered? We study one such problem setting, that of "one-sided" matrix completion, where our goal is to recover the right singular vectors of $X$, even in the regime where recovering the left singular vectors is impossible, which arises when there are more rows than columns and very few observations. We propose a natural algorithm that involves imputing the missing values of the matrix $X^TX$ and show that even with only two observations per row in $X$, we can provably recover $X^TX$ as long as we have at least $\Omega(r^2 d \log d)$ rows, where $r$ is the rank and $d$ is the number of columns. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing. In these settings, our algorithm substantially outperforms standard matrix completion and a variety of direct factorization methods.
• Abstract（参考訳）: 低ランクマトリックス$x$からの観察されたエントリ数を仮定すると、マトリックス補完は、欠落したエントリを暗示する問題であり、欠落データの推定を含む、幅広い実世界の設定を定式化する。 しかし、行列を完遂するには観測されるエントリが少なすぎる場合、基盤となる行列の他の側面は確実に復元できるだろうか? 左特異ベクトルの回復が不可能な状態においても、列よりも行数が多く、観測がほとんどない状態においても、右特異ベクトルを$X$で回収することが目的である「片側」行列完備化のそのような問題について研究する。 我々は,行列の欠落値である$X^TX$を計算し,少なくとも$\Omega(r^2 d \log d)$行を持つ限り,$X^TX$は1行あたり2つの観測しか持たないが,$r$はランクであり,$d$は列数であることを示す自然アルゴリズムを提案する。 合成データの片面復元と低被覆ゲノムシークエンシングに関するアルゴリズムを評価した。 これらの設定において、本アルゴリズムは、標準行列補完および様々な直接分解法を実質的に上回っている。

関連論文リスト

• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• On the well-spread property and its relation to linear regression [4.619541348328937]
  頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。 与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
  論文  参考訳（メタデータ） (2022-06-16T11:17:44Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。 シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
  論文  参考訳（メタデータ） (2021-10-15T09:27:50Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Unique sparse decomposition of low rank matrices [17.037882881652617]
  低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。 我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
  論文  参考訳（メタデータ） (2021-06-14T20:05:59Z)
• Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
  この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。 その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
  論文  参考訳（メタデータ） (2020-07-18T15:36:11Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。 最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。 これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
  論文  参考訳（メタデータ） (2020-04-16T22:57:06Z)
• Optimal Exact Matrix Completion Under new Parametrization [0.0]
  適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。 対象行列を正確に復元する行列補完アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-06T18:31:47Z)
• 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)

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

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