論文の概要: Multi-reference alignment in high dimensions: sample complexity and phase transition

• arxiv url: http://arxiv.org/abs/2007.11482v3
• Date: Thu, 30 Sep 2021 14:44:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-07 23:32:09.536474
• Title: Multi-reference alignment in high dimensions: sample complexity and phase transition
• Title（参考訳）: 高次元におけるマルチリファレンスアライメント:サンプル複雑性と相転移
• Authors: Elad Romanov, Tamir Bendory, Or Ordentlich
• Abstract要約: マルチ参照アライメントは、円形にシフトしたノイズの多いコピーから$mathbbRL$のシグナルを推定する。 単一粒子の低温電子顕微鏡により、高次元状態における問題のサンプルの複雑さを解析した。 我々の分析では、パラメータ $alpha = L/(sigma2log L)$ で制御される相転移現象を発見し、$sigma2$ はノイズの分散である。
• 参考スコア（独自算出の注目度）: 31.841289319809814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-reference alignment entails estimating a signal in $\mathbb{R}^L$ from its circularly-shifted and noisy copies. This problem has been studied thoroughly in recent years, focusing on the finite-dimensional setting (fixed $L$). Motivated by single-particle cryo-electron microscopy, we analyze the sample complexity of the problem in the high-dimensional regime $L\to\infty$. Our analysis uncovers a phase transition phenomenon governed by the parameter $\alpha = L/(\sigma^2\log L)$, where $\sigma^2$ is the variance of the noise. When $\alpha>2$, the impact of the unknown circular shifts on the sample complexity is minor. Namely, the number of measurements required to achieve a desired accuracy $\varepsilon$ approaches $\sigma^2/\varepsilon$ for small $\varepsilon$; this is the sample complexity of estimating a signal in additive white Gaussian noise, which does not involve shifts. In sharp contrast, when $\alpha\leq 2$, the problem is significantly harder and the sample complexity grows substantially quicker with $\sigma^2$.
• Abstract（参考訳）: 多重参照アライメントは、円偏移とノイズのコピーから$\mathbb{r}^l$の信号の推定を伴っている。 この問題は近年、有限次元の設定(固定値$l$)に焦点をあてて徹底的に研究されている。 単粒子核電子顕微鏡を応用し,高次元領域における問題のサンプル複雑性を解析した。 我々の分析では、パラメータ $\alpha = L/(\sigma^2\log L)$ で支配される相転移現象を明らかにし、$\sigma^2$ はノイズの分散である。 $\alpha>2$の場合、未知の円周シフトがサンプルの複雑さに与える影響は小さい。 すなわち、所望の精度を達成するのに必要な測定値の数を$\varepsilon$ approach $\sigma^2/\varepsilon$ for small $\varepsilon$; これは、シフトを伴わない付加的な白色ガウス雑音で信号を推定するサンプルの複雑さである。 対照的に、$\alpha\leq 2$ の場合、問題は著しく難しく、サンプルの複雑さは $\sigma^2$ でかなり速く成長する。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling [6.219791262322396]
  実ガウス項を持つ $sfS|LWErangle$ および $sfC|LWErangle$ に対する新しいアルゴリズム、硬度結果、およびその他の関連する振幅を示す。
  論文  参考訳（メタデータ） (2023-10-01T11:53:24Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
  ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。 我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
  論文  参考訳（メタデータ） (2022-09-09T23:35:25Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Estimation of Shortest Path Covariance Matrices [21.772761365915176]
  共分散行列 $mathbfSigma in mathbbRdtimes d$ of a distribution $mathcal D$ over $mathbbRd$ given independent sample。 単に$O(sqrtD)$エントリ複雑性と$tilde O(r)を使って、標準エラーまで$mathbfSigma$を推定するための非常に単純なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-11-19T17:37:46Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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