Fugu-MT 論文翻訳(概要): Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion

論文の概要: Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion

arxiv url: http://arxiv.org/abs/2008.04988v1
Date: Tue, 11 Aug 2020 19:56:35 GMT
ステータス: 処理完了
システム内更新日: 2022-10-31 11:14:00.785740
Title: Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion
Title（参考訳）: 階数 1 行列完備に対する交互最小化の漸近収束速度
Authors: Rui Liu and Alex Olshevsky
Abstract要約: 最小限の最小化を最小限の条件で検討する。我々は、可逆的コンセンサス問題の固有値の変動特性により収束率を束縛する。このことは、ノード数と明らかにされたエントリのグラフの最大の度合いの点で、そのレートの上限に繋がる。
参考スコア（独自算出の注目度）: 15.321579527891457
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study alternating minimization for matrix completion in the simplest possible setting: completing a rank-one matrix from a revealed subset of the entries. We bound the asymptotic convergence rate by the variational characterization of eigenvalues of a reversible consensus problem. This leads to a polynomial upper bound on the asymptotic rate in terms of number of nodes as well as the largest degree of the graph of revealed entries.
Abstract（参考訳）: 最も単純な設定で行列補完の交互最小化について検討する: エントリーの明らかな部分集合からランク1行列を完結する。我々は、可逆コンセンサス問題の固有値の変動特性により漸近収束率を束縛する。これにより、ノード数と明らかにされたエントリのグラフの最大の次数という観点から、漸近速度の多項式上界が導かれる。

関連論文リスト

Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文参考訳（メタデータ） (2024-05-23T12:26:25Z)
Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling [10.824999179337558]
行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
論文参考訳（メタデータ） (2024-02-29T23:24:43Z)
Complete Upper Bound Hierarchies for Spectral Minimum in Noncommutative Polynomial Optimization [1.6385815610837167]
この研究は、有限個の非可換制約に対する非可換対象のスペクトル最小値を求めることに焦点をあてる。 Navascu'es-Pironio-Ac'in 階層はラッサールの正方形のモーメントサムの非可換類似である。本稿では,スペクトル最小値に対する上界の相補的完全階層を導出する。
論文参考訳（メタデータ） (2024-02-03T11:53:57Z)
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文参考訳（メタデータ） (2023-01-10T12:18:47Z)
Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文参考訳（メタデータ） (2022-05-21T01:47:17Z)
Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization [16.325663190517773]
我々は、任意の過パラメータ化を持つ自然な非定式化の下で、非対称な分解問題を考察する。観測された行列に対して最高の低ランク近似を生成する。
論文参考訳（メタデータ） (2022-03-06T00:07:53Z)
Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-09-30T19:17:35Z)
Pure Exploration and Regret Minimization in Matching Bandits [19.205538784019936]
本研究では, 隣接行列上のランク1の仮定を利用して, サンプルの複雑さを低減できることを証明した。重み付きグラフで最適なマッチングを見つけることは、標準的な問題である。
論文参考訳（メタデータ） (2021-07-31T12:37:51Z)
Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文参考訳（メタデータ） (2021-05-03T16:36:27Z)
Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent [22.851500417035947]
因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
論文参考訳（メタデータ） (2021-02-04T03:41:54Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)

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