論文の概要: Leveraged Matrix Completion with Noise
- arxiv url: http://arxiv.org/abs/2011.05885v2
- Date: Mon, 14 Aug 2023 10:15:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-16 00:01:16.501003
- Title: Leveraged Matrix Completion with Noise
- Title（参考訳）: 雑音によるレバレッジマトリックス補完
- Authors: Xinjian Huang and Weiwei Liu and Bo Du and Dacheng Tao
- Abstract要約: 未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry.
我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
- 参考スコア（独自算出の注目度）: 84.20092979053119
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Completing low-rank matrices from subsampled measurements has received much
attention in the past decade. Existing works indicate that
$\mathcal{O}(nr\log^2(n))$ datums are required to theoretically secure the
completion of an $n \times n$ noisy matrix of rank $r$ with high probability,
under some quite restrictive assumptions: (1) the underlying matrix must be
incoherent; (2) observations follow the uniform distribution. The
restrictiveness is partially due to ignoring the roles of the leverage score
and the oracle information of each element. In this paper, we employ the
leverage scores to characterize the importance of each element and
significantly relax assumptions to: (1) not any other structure assumptions are
imposed on the underlying low-rank matrix; (2) elements being observed are
appropriately dependent on their importance via the leverage score. Under these
assumptions, instead of uniform sampling, we devise an ununiform/biased
sampling procedure that can reveal the ``importance'' of each observed element.
Our proofs are supported by a novel approach that phrases sufficient optimality
conditions based on the Golfing Scheme, which would be of independent interest
to the wider areas. Theoretical findings show that we can provably recover an
unknown $n\times n$ matrix of rank $r$ from just about $\mathcal{O}(nr\log^2
(n))$ entries, even when the observed entries are corrupted with a small amount
of noisy information. The empirical results align precisely with our theories.
- Abstract（参考訳）: サブサンプリングによる低ランク行列の完成は、過去10年間で大きな注目を集めている。
既存の研究は、$\mathcal{O}(nr\log^2(n))$ datumsが、高い確率で$r$のランクの$n \times n$ noisy行列の完備化を理論的に確保するために必要であることを示している。
制限性の一部は、レバレッジスコアの役割と各要素のオラクル情報を無視しているためである。
本稿では,各要素の重要性を特徴付けるレバレッジスコアを用い,(1)下位の低ランク行列に他の構造仮定が課されないこと,(2)観測される要素がレバレッジスコアを通じてその重要性に適切に依存すること,など,仮定を著しく緩和する。
これらの仮定の下では、一様サンプリングの代わりに、観測された各要素の'重要'を明らかにする、一様/バイアスサンプリング手順を考案する。
我々の証明は、ゴルフのスキームに基づいて十分な最適条件をフレーズする新しいアプローチによって支持されている。
理論的には、未知のn\times n$ matrix of rank $r$ を約$\mathcal{o}(nr\log^2 (n))$エントリから取り出すことができる。
実験結果は我々の理論と正確に一致している。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - RankFeat: Rank-1 Feature Removal for Out-of-distribution Detection [65.67315418971688]
textttRankFeat は OOD 検出のためのシンプルだが効果的な textttpost hoc アプローチである。
textttRankFeatは、Emphstate-of-the-artパフォーマンスを実現し、以前のベストメソッドと比較して平均偽陽性率(FPR95)を17.90%削減する。
論文 参考訳（メタデータ） (2022-09-18T16:01:31Z) - Robust Matrix Completion with Heavy-tailed Noise [0.5837881923712392]
本稿では,重み付き潜在的非対称雑音の存在下での低ランク行列の完全性について検討する。
本稿では,大規模かつ非対称な誤りに対して頑健な重み付き雑音に適応するハマー損失を適応的に適用する。
誤差の2番目のモーメント条件下では、ユークリッド誤差は最小値の統計的推定誤差に到達するまで幾何的に早く落ちることが証明される。
論文 参考訳（メタデータ） (2022-06-09T04:48:48Z) - Robust Linear Regression for General Feature Distribution [21.0709900887309]
本研究では, 不正な相手によってデータが汚染されるような頑健な線形回帰について検討する。
必ずしもその機能が中心であるとは限らない。
特徴が中心ならば、標準収束率を得ることができる。
論文 参考訳（メタデータ） (2022-02-04T11:22:13Z) - Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates
and Model Misspecification [16.0817847880416]
ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。
誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
論文 参考訳（メタデータ） (2022-01-06T08:51:08Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Tackling small eigen-gaps: Fine-grained eigenvector estimation and
inference under heteroscedastic noise [28.637772416856194]
ノイズの観測から、固有ベクトル推定と低ランク行列の推測に2つの根本的な課題が生じる。
未知固有ベクトルに対する推定と不確実性定量化手法を提案する。
未知固有値に対する信頼区間を構築するための最適手順を確立する。
論文 参考訳（メタデータ） (2020-01-14T04:26:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。