eduzhai > Applied Sciences > Engineering >

Multi-reference alignment in high dimensions sample complexity and phase transition

  • king
  • (0) Download
  • 20210506
  • Save

... pages left unread,continue reading

Document pages: 44 pages

Abstract: Multi-reference alignment entails estimating a signal in $ mathbb{R}^L$ fromits circularly-shifted and noisy copies. This problem has been studiedthoroughly in recent years, focusing on the finite-dimensional setting (fixed$L$). Motivated by single-particle cryo-electron microscopy, we analyze thesample 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 samplecomplexity is minor. Namely, the number of measurements required to achieve adesired accuracy $ varepsilon$ approaches $ sigma^2 varepsilon$ for small$ varepsilon$; this is the sample complexity of estimating a signal in additivewhite Gaussian noise, which does not involve shifts. In sharp contrast, when$ alpha leq 2$, the problem is significantly harder and the sample complexitygrows substantially quicker with $ sigma^2$.

Please select stars to rate!

         

0 comments Sign in to leave a comment.

    Data loading, please wait...
×