論文の概要: Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling

• arxiv url: http://arxiv.org/abs/2403.00184v1
• Date: Thu, 29 Feb 2024 23:24:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-05 18:46:21.418780
• Title: Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
• Title（参考訳）: 非一様サンプリングによる低ランク行列完備化のためのエントリ固有境界
• Authors: Xumei Xi, Christina Lee Yu and Yudong Chen
• Abstract要約: 行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。 我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
• 参考スコア（独自算出の注目度）: 10.824999179337558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with highly varying probabilities, potentially with different asymptotic scalings. We show that under structured sampling probabilities, it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. In particular, we prove error upper bounds customized to each entry, which match the minimax lower bounds under certain conditions. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities. We provide numerical experiments that confirm our theoretical findings.
• Abstract（参考訳）: 低ランク行列の完備化は、観測されたエントリのスパース集合を用いて行列内の観測されていないエントリを推定する問題を懸念する。 我々は、観測されたエントリが非常に異なる確率でサンプリングされ、異なる漸近的スケーリングを持つような非一様集合を考える。 構造的サンプリング確率の下では、行列全体ではなく、より小さな部分行列上で推定アルゴリズムを実行する方が適している場合が多い。 特に,各エントリにカスタマイズされた誤差上界が,特定の条件下でのミニマックス下界と一致することを示す。 我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。 理論的結果を確認する数値実験を行った。

関連論文リスト

• Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows [9.631640936820126]
  行列補完は、観察されたエントリのスパースセットに基づいて、低ランク行列の欠落値を予測するタスクに取り組む。 観測パターンによって誘導される二部グラフのネットワークフローに基づく行列補完アルゴリズムを提案する。 この結果から,行列内の特定のエントリの回復に対する最小二乗誤差は,グラフ内の対応するエッジの有効抵抗に比例することを示した。
  論文  参考訳（メタデータ） (2024-09-06T02:01:03Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• Entrywise Inference for Missing Panel Data: A Simple and Instance-Optimal Approach [27.301741710016223]
  停滞した採用によって引き起こされたパネルデータの欠落データバージョンに関連する推論的疑問を考察する。 我々は、予め特定されたカバレッジでエントリワイドな信頼区間を構築するためのデータ駆動方式を開発し、分析する。 我々は、欠落したエントリを推定する際に、そのエラーに非漸近的かつ高い確率境界を証明した。
  論文  参考訳（メタデータ） (2024-01-24T18:58:18Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Matrix Completion from General Deterministic Sampling Patterns [28.116011361245224]
  我々は、精度よく近似した低ランク行列完備問題の理論的保証を確立する。 観測グラフが十分に接続されており、類似ノード次数を持つため、このアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2023-06-04T07:01:31Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Pure Exploration and Regret Minimization in Matching Bandits [19.205538784019936]
  本研究では, 隣接行列上のランク1の仮定を利用して, サンプルの複雑さを低減できることを証明した。 重み付きグラフで最適なマッチングを見つけることは、標準的な問題である。
  論文  参考訳（メタデータ） (2021-07-31T12:37:51Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。 我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。 我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
  論文  参考訳（メタデータ） (2021-07-05T21:05:11Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion [2.0257616108612373]
  部分的な問題としてラッソを含む行列圧縮センシングと行列補完を扱う。 本稿では,ハマー損失関数と核ノルムのペナル化を組み合わせた単純な統一手法を提案する。
  論文  参考訳（メタデータ） (2020-10-25T02:32:07Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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