Abstract: In multi-reference alignment (MRA), one wishes to recover a signal (L-dimensional vector) from circularly shifted and noisy measurements of itself. This problem has received considerable attention in recent years, being a “toy model” for problems in imaging (e.g., cryo-em). It is known that the sample complexity, namely the number of measurements needed to achieve some prescribed estimation error, displays a qualitatively different behavior with respect to the SNR between a “high-SNR” and a “low-SNR” regime. A seminal result of [Perry el al. 2017] has shown that for “generic” signals, as SNR << 1, the sample complexity scales like n ~ 1/SNR^3 ; whereas when SNR >> 1 it is known to scale like n ~ 1/SNR (Note: 1/SNR is the sample complexity scaling for estimating a signal in only additive noise, *without* circular shifts). These bounds hide a (polynomial) dimensional dependence, which hasn’t been characterized tightly. Motivated by the high dimension of contemporary imaging datasets, we study MRA in a high-dimensional framework (L -> inf). Our main result unveils a phase-transition behavior with respect to the statistical difficulty of MRA. Let alpha=SNR/log(L) ; then as L -> inf, we identify two SNR regimes:
(i) “High-SNR” : alpha > 2, where the sample complexity of MRA is essentially the same as estimating a signal in only additive noise.
(ii) “Low-SNR” : alpha <= 2, where the sample complexity is much worse – in this regime, MRA is a substantially more difficult problem, in an information-theoretic sense.
This is joint work with Tamir Bendory (TAU) and Or Ordentlich (HUJI).