论文标题
高维度的多引用对准：样品复杂性和相变
Multi-reference alignment in high dimensions: sample complexity and phase transition
论文作者
论文摘要
多引用对齐需要从其圆形和嘈杂的副本中估算$ \ mathbb {r}^l $中的信号。近年来，已经对这个问题进行了彻底的研究，重点是有限维设置（固定$ L $）。由单粒子冷冻电子显微镜进行的，我们分析了高维度$ l \ to \ infty $中问题的样本复杂性。我们的分析揭示了由参数$α= l/（σ^2 \ log l）$控制的相变现象，其中$σ^2 $是噪声的方差。当$α> 2 $时，未知的圆形移位对样品复杂性的影响很小。也就是说，实现所需准确性$ \ varepsilon $接近$σ^2/\ varepsilon $所需的测量数量，用于小$ \ varepsilon $;这是估计添加剂白色高斯噪声中信号的样本复杂性，这不涉及变化。相比之下，当$α\ leq 2 $时，问题更加困难，样品复杂性会以$σ^2 $的速度增长。
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 $α= L/(σ^2\log L)$, where $σ^2$ is the variance of the noise. When $α>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 $σ^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 $α\leq 2$, the problem is significantly harder and the sample complexity grows substantially quicker with $σ^2$.
