論文の概要: Matrix Completion from General Deterministic Sampling Patterns

• arxiv url: http://arxiv.org/abs/2306.02283v1
• Date: Sun, 4 Jun 2023 07:01:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-06 18:45:54.831172
• Title: Matrix Completion from General Deterministic Sampling Patterns
• Title（参考訳）: 一般決定論的サンプリングパターンからの行列補完
• Authors: Hanbyul Lee, Rahul Mazumder, Qifan Song, Jean Honorio
• Abstract要約: 我々は、精度よく近似した低ランク行列完備問題の理論的保証を確立する。 観測グラフが十分に接続されており、類似ノード次数を持つため、このアルゴリズムが成功することを示す。
• 参考スコア（独自算出の注目度）: 28.116011361245224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most of the existing works on provable guarantees for low-rank matrix completion algorithms rely on some unrealistic assumptions such that matrix entries are sampled randomly or the sampling pattern has a specific structure. In this work, we establish theoretical guarantee for the exact and approximate low-rank matrix completion problems which can be applied to any deterministic sampling schemes. For this, we introduce a graph having observed entries as its edge set, and investigate its graph properties involving the performance of the standard constrained nuclear norm minimization algorithm. We theoretically and experimentally show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees. Our result can be viewed as an extension of the works by Bhojanapalli and Jain [2014] and Burnwal and Vidyasagar [2020], in which the node degrees of the observation graph were assumed to be the same. In particular, our theory significantly improves their results when the underlying matrix is symmetric.
• Abstract（参考訳）: 低ランク行列補完アルゴリズムの証明可能な保証に関する既存の研究のほとんどは、行列のエントリがランダムにサンプリングされるか、サンプリングパターンが特定の構造を持つという非現実的な仮定に依存している。 本研究では,任意の決定論的サンプリングスキームに適用可能な完全かつ近似的な低ランク行列完備問題に対する理論的保証を確立する。 そこで本研究では,そのエッジセットとしてエントリを観測したグラフを導入し,標準制約付き核ノルム最小化アルゴリズムの性能を含むグラフ特性について検討する。 理論的および実験的に観察グラフが良好に連結され、類似のノード次数を持つため、アルゴリズムが成功することを示す。 我々の結果は、Bhojanapalli と Jain [2014] と Burnwal と Vidyasagar [2020] による、観測グラフのノード次数が同じであると仮定された作品の拡張と見なすことができる。 特に、基礎となる行列が対称である場合、我々の理論は結果を大幅に改善する。

関連論文リスト

• Low-rank Bayesian matrix completion via geodesic Hamiltonian Monte Carlo on Stiefel manifolds [0.18416014644193066]
  低ランクベイズ行列の効率的な計算を可能にするための新しいサンプリングベース手法を提案する。 提案手法は, 標準ギブスサンプリング器で発生するサンプリング困難を, 行列完備化に使用される一般的な2つの行列因子化のために解決することを示す。 数値的な例は、より優れた混合と定常分布への高速収束を含む優れたサンプリング性能を示す。
  論文  参考訳（メタデータ） (2024-10-27T03:12:53Z)
• Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows [9.631640936820126]
  行列補完は、観察されたエントリのスパースセットに基づいて、低ランク行列の欠落値を予測するタスクに取り組む。 観測パターンによって誘導される二部グラフのネットワークフローに基づく行列補完アルゴリズムを提案する。 この結果から,行列内の特定のエントリの回復に対する最小二乗誤差は,グラフ内の対応するエッジの有効抵抗に比例することを示した。
  論文  参考訳（メタデータ） (2024-09-06T02:01:03Z)
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling [10.824999179337558]
  行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。 我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
  論文  参考訳（メタデータ） (2024-02-29T23:24:43Z)
• Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms [5.405890484609721]
  本稿では,ソーシャルグラフやハイパーグラフだけでなく,サブサンプル行列のエントリにもとづく評価行列の完成問題を考察する。 評価行列を正確に完遂するタスクに対して,サンプル確率にエンフシャープしきい値が存在することを示す。 我々は,観測されたグラフやハイパーグラフを効果的に活用する計算効率の良い行列補完アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-01-16T08:25:29Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  種々の非重み付きグラフの集合上でガウス過程の先行を定義するための原理的手法を提案する。 さらに、未重み付きグラフの同値類の集合を検討し、それに対する事前の適切なバージョンを定義する。 化学の応用に触発されて、我々は、小データ構造における実際の分子特性予測タスクについて、提案手法を解説した。
  論文  参考訳（メタデータ） (2022-11-03T10:18:17Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Bayesian matrix completion with a spectral scaled Student prior: theoretical guarantee and efficient sampling [0.30458514384586394]
  スペクトルスケールされた学生プリエントは、データマトリックスの下位低ランク構造を好むために利用される。 提案手法は,本手法がモデル不特定条件下でうまく機能することを保証し,極小最適オラクル不等式を満足することを示す。
  論文  参考訳（メタデータ） (2021-04-16T16:03:43Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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