論文の概要: All-or-nothing statistical and computational phase transitions in sparse
spiked matrix estimation
- arxiv url: http://arxiv.org/abs/2006.07971v2
- Date: Fri, 30 Oct 2020 11:07:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 13:41:01.600047
- Title: All-or-nothing statistical and computational phase transitions in sparse
spiked matrix estimation
- Title（参考訳）: スパーススパイク行列推定における統計的および計算的相転移
- Authors: Jean Barbier, Nicolas Macris and Cynthia Rush
- Abstract要約: スパース方式で近似メッセージパッシングアルゴリズムを解析する。
最小誤差と平均二乗誤差の位相遷移がすべて存在する。
スパース体制では、スパース回復が近似メッセージパッシングに困難であることを示す統計的-アルゴリズム的ギャップが分岐する。
- 参考スコア（独自算出の注目度）: 35.035853993422506
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We determine statistical and computational limits for estimation of a
rank-one matrix (the spike) corrupted by an additive gaussian noise matrix, in
a sparse limit, where the underlying hidden vector (that constructs the
rank-one matrix) has a number of non-zero components that scales sub-linearly
with the total dimension of the vector, and the signal-to-noise ratio tends to
infinity at an appropriate speed. We prove explicit low-dimensional variational
formulas for the asymptotic mutual information between the spike and the
observed noisy matrix and analyze the approximate message passing algorithm in
the sparse regime. For Bernoulli and Bernoulli-Rademacher distributed vectors,
and when the sparsity and signal strength satisfy an appropriate scaling
relation, we find all-or-nothing phase transitions for the asymptotic minimum
and algorithmic mean-square errors. These jump from their maximum possible
value to zero, at well defined signal-to-noise thresholds whose asymptotic
values we determine exactly. In the asymptotic regime the
statistical-to-algorithmic gap diverges indicating that sparse recovery is hard
for approximate message passing.
- Abstract（参考訳）: 本研究では,次数1行列(スパイク)を加法ガウス雑音行列で推定する統計的および計算的限界を,下位の隠れベクトル(階数1行列を構成する)がベクトルの総次元に準線形にスケールする多数の非ゼロ成分を持ち,信号対雑音比が適切な速度で無限大となるようなスパース極限で決定する。
スパイクと観測された雑音行列間の漸近的相互情報に対する明示的な低次元変分公式を証明し,スパースレジームにおける近似メッセージパッシングアルゴリズムを解析した。
Bernoulli と Bernoulli-Rademacher の分散ベクトルに対して、スパーシリティと信号強度が適切なスケーリング関係を満たすとき、漸近的最小誤差とアルゴリズム的平均二乗誤差の全てあるいはなしの位相遷移を求める。
これらは、漸近値が正確に決定される信号対雑音閾値において、最大値からゼロにジャンプする。
漸近的な状況下では、スパースリカバリが近似メッセージパッシングに困難であることを示す統計的-アルゴリズム的ギャップが分岐する。
関連論文リスト
- Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods [24.06775799553418]
本研究では,列相関と列相関の両方でノイズによって劣化したランク1$の信号の特異ベクトルを推定する行列記述問題について検討する。
本研究は,2つのヘテロセダスティックノイズを重畳した行列の,情報理論的およびアルゴリズム的限界を確立する。
論文 参考訳（メタデータ） (2024-05-22T18:38:10Z) - Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled
Gradient Descent, Even with Overparameterization [48.65416821017865]
この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。
低ランク物体の条件数に依存しない定数速度で直線的に収束する。
様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
論文 参考訳（メタデータ） (2023-10-09T21:16:57Z) - Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap [24.073221004661427]
部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
論文 参考訳（メタデータ） (2022-05-26T17:47:35Z) - Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures [12.868722327487752]
本稿では,各行列値の観測値に低ランク構造が植え付けられていることを前提として,低ランクガウス混合モデル(LrMM)を提案する。
一般に計算不可能な最大極大推定器の最小極大最適性を証明する。
以上の結果から,ミニマックス誤差率と統計的-計算的ギャップの相転移が明らかとなった。
論文 参考訳（メタデータ） (2022-01-22T12:43:25Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Long Random Matrices and Tensor Unfolding [4.83420384410068]
行列の次元に応じて臨界信号対雑音比が存在することを示す。
主な応用として、非対称ランクワンスパイクテンソルモデルに対するテンソル展開アルゴリズムについて検討する。
論文 参考訳（メタデータ） (2021-10-19T19:13:27Z) - Rank-one matrix estimation with groupwise heteroskedasticity [5.202966939338455]
本研究では,異なるノイズレベル下で行列の異なるブロックが観測されるガウス観測からランク1行列を推定する問題について検討する。
行列と潜伏変数の両方を推定する際、最小平均二乗誤差の正確な公式を証明した。
我々は、近似メッセージパッシングアルゴリズムと勾配降下アルゴリズムを導出し、これらのアルゴリズムが特定の状況における情報理論的限界を達成することを実証的に示す。
論文 参考訳（メタデータ） (2021-06-22T17:48:36Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳（メタデータ） (2020-07-16T13:27:47Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。