Back to Search
Start Over
Multi-reference alignment in high dimensions: sample complexity and phase transition
- Source :
- SIAM Journal on Mathematics of Data Science 3.2 (2021): 494-523
- Publication Year :
- 2020
-
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$.
Details
- Database :
- arXiv
- Journal :
- SIAM Journal on Mathematics of Data Science 3.2 (2021): 494-523
- Publication Type :
- Report
- Accession number :
- edsarx.2007.11482
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1137/20M1354994