論文の概要: Fast exact recovery of noisy matrix from few entries: the infinity norm approach

• arxiv url: http://arxiv.org/abs/2501.19224v1
• Date: Fri, 31 Jan 2025 15:31:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-03 13:57:46.155859
• Title: Fast exact recovery of noisy matrix from few entries: the infinity norm approach
• Title（参考訳）: 少数成分からの雑音行列の高速精度回復 : 無限ノルムアプローチ
• Authors: BaoLinh Tran, Van Vu,
• Abstract要約: データサイエンスの中心的な問題である行列回復問題は、比較的小さなエントリのサンプルから行列A$を回収することである。 そのようなタスクは一般には不可能であるが、正確に時間内に$A$を回収できることが示されている。 基底行列が有界な精度を持つことを考えると、雑音の場合においても正確な回復が達成できることが示される。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The matrix recovery (completion) problem, a central problem in data science and theoretical computer science, is to recover a matrix $A$ from a relatively small sample of entries. While such a task is impossible in general, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, from a random subset of entries, under three (basic and necessary) assumptions: (1) the rank of $A$ is very small compared to its dimensions (low rank), (2) $A$ has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. There are many different algorithms for the task, including convex optimization by Candes, Tao and Recht (2009), alternating projection by Hardt and Wooters (2014) and low rank approximation with gradient descent by Keshavan, Montanari and Oh (2009, 2010). In applications, it is more realistic to assume that data is noisy. In this case, these approaches provide an approximate recovery with small root mean square error. However, it is hard to transform such approximate recovery to an exact one. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) concerning approximation in the infinity norm showed that we can achieve exact recovery even in the noisy case, given that the ground matrix has bounded precision. Beyond the three basic assumptions above, they required either the condition number of $A$ is small (Abbe et al.) or the gap between consecutive singular values is large (Bhardwaj et al.). In this paper, we remove these extra spectral assumptions. As a result, we obtain a simple algorithm for exact recovery in the noisy case, under only three basic assumptions. This is the first such algorithm. To analyse the algorithm, we introduce a contour integration argument which is totally different from all previous methods and may be of independent interest.
• Abstract（参考訳）: データ科学と理論計算機科学の中心的な問題である行列回復(補完)問題は、比較的小さなエントリのサンプルから行列A$を回収することである。 そのようなタスクは一般には不可能であるが、(1)$A$のランクはその次元(下階)と比較して非常に小さい、(2)$A$は非局在化された特異ベクトル(不整合)を持ち、(3)サンプルサイズは十分に大きい、という3つの仮定の下で、入力のランダムな部分集合から高い確率で多項式時間で正確に$A$を回収できることが示されている。 Candes, Tao and Recht (2009) による凸最適化、 Hardt and Wooters (2014) による交互射影、Keshavan, Montanari and Oh (2009, 2010) による勾配降下による低階近似など、様々なアルゴリズムがある。 アプリケーションでは、データがノイズであると仮定する方が現実的です。 この場合、これらの手法はルート平均二乗誤差を小さくして近似的に回復する。 しかし、そのような近似的なリカバリを正確に変換することは困難である。 近年、無限ノルムの近似に関する Abbe et al (2017) と Bhardwaj et al (2023) の結果は、基底行列が有界な精度であることを考えると、雑音の場合においても正確な回復が可能であることを示した。 上記の3つの基本的な仮定の他に、A$の条件数は小さい(Abbe et al )か、連続特異値の間のギャップが大きい(Bhardwaj et al )。 本稿では、これらの余剰スペクトル仮定を除去する。 その結果,3つの基本前提条件の下で,雑音条件下での正確な回復のための簡単なアルゴリズムが得られた。 これが最初のアルゴリズムである。 このアルゴリズムを解析するために,従来の手法とは全く異なる輪郭積分論法を導入する。

関連論文リスト

• 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)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Truncated Linear Regression in High Dimensions [26.41623833920794]
  truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。 目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。 我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
  論文  参考訳（メタデータ） (2020-07-29T00:31:34Z)
• List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
  未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。 仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。 より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
  論文  参考訳（メタデータ） (2020-06-18T17:47:37Z)
• Robust estimation via generalized quasi-gradients [28.292300073453877]
  最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。 我々は「一般化された準次数」の存在を識別する 一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-05-28T15:14:33Z)
• Optimal Exact Matrix Completion Under new Parametrization [0.0]
  適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。 対象行列を正確に復元する行列補完アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-06T18:31:47Z)

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

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