論文の概要: Phase retrieval in high dimensions: Statistical and computational phase
transitions
- arxiv url: http://arxiv.org/abs/2006.05228v2
- Date: Fri, 23 Oct 2020 15:27:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 15:56:09.159990
- Title: Phase retrieval in high dimensions: Statistical and computational phase
transitions
- Title（参考訳）: 高次元における位相検索:統計的および計算的位相遷移
- Authors: Antoine Maillard, Bruno Loureiro, Florent Krzakala, Lenka Zdeborov\'a
- Abstract要約: 我々は$mathbfXstar$を$m$(おそらくノイズの多い)観測から再構成する問題を考察する。
特に、フルランク行列に対する情報理論上の完全回復への遷移は、$alpha=1$と$alpha=2$である。
我々の研究は、高次元位相探索における統計的およびアルゴリズム的しきい値の広範な分類を提供する。
- 参考スコア（独自算出の注目度）: 27.437775143419987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the phase retrieval problem of reconstructing a $n$-dimensional
real or complex signal $\mathbf{X}^{\star}$ from $m$ (possibly noisy)
observations $Y_\mu = | \sum_{i=1}^n \Phi_{\mu i} X^{\star}_i/\sqrt{n}|$, for a
large class of correlated real and complex random sensing matrices
$\mathbf{\Phi}$, in a high-dimensional setting where $m,n\to\infty$ while
$\alpha = m/n=\Theta(1)$. First, we derive sharp asymptotics for the lowest
possible estimation error achievable statistically and we unveil the existence
of sharp phase transitions for the weak- and full-recovery thresholds as a
function of the singular values of the matrix $\mathbf{\Phi}$. This is achieved
by providing a rigorous proof of a result first obtained by the replica method
from statistical mechanics. In particular, the information-theoretic transition
to perfect recovery for full-rank matrices appears at $\alpha=1$ (real case)
and $\alpha=2$ (complex case). Secondly, we analyze the performance of the
best-known polynomial time algorithm for this problem -- approximate
message-passing -- establishing the existence of a statistical-to-algorithmic
gap depending, again, on the spectral properties of $\mathbf{\Phi}$. Our work
provides an extensive classification of the statistical and algorithmic
thresholds in high-dimensional phase retrieval for a broad class of random
matrices.
- Abstract（参考訳）: m$(おそらく騒がしい)の観測値から$n$の実または複素信号$\mathbf{x}^{\star}$を再構成する位相検索問題を考える。 $m,n\to\infty$の高次元環境では$y_\mu = | \sum_{i=1}^n \phi_{\mu i} x^{\star}_i/\sqrt{n}|$である。
まず、統計的に達成可能な最小推定誤差に対するシャープな漸近を導出し、行列 $\mathbf{\Phi}$ の特異値の関数として弱および完全回復しきい値に対するシャープな位相遷移の存在を明らかにする。
これは、統計力学からレプリカ法によって最初に得られた結果の厳密な証明を提供することによって達成される。
特に、フルランク行列に対する情報理論上の完全回復への遷移は、$\alpha=1$ (実ケース) および $\alpha=2$ (複素ケース) に現れる。
次に,この問題に対する最もよく知られた多項式時間アルゴリズム(近似メッセージパッシング)の性能を解析し,$\mathbf{\phi}$ のスペクトル特性に依存する統計的-代数的ギャップの存在を明らかにした。
本研究は,確率行列の広いクラスに対する高次元位相探索における統計的およびアルゴリズム的しきい値の広範な分類を提供する。
関連論文リスト
- Near-Optimal and Tractable Estimation under Shift-Invariance [0.21756081703275998]
そのような信号のクラスは、非常にリッチである:$mathbbCn$ 上のすべての指数振動を含み、合計$s$ である。
このクラスの統計複雑性は、$(delta)$-confidence $ell$-ballの半径2乗最小マックス周波数によって測定されるが、$s$-sparse信号のクラス、すなわち$Oleft(slog(en) + log(delta-1)right) cdot log(en/s)とほぼ同じであることを示す。
論文 参考訳（メタデータ） (2024-11-05T18:11:23Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics [8.90202564665576]
一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳（メタデータ） (2020-06-09T02:05:40Z) - Asymptotic errors for convex penalized linear regression beyond Gaussian
matrices [23.15629681360836]
雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。
平均二乗誤差に対する明示的な式を厳密に導出する。
我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
論文 参考訳（メタデータ） (2020-02-11T13:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。