← All problems

10 Lectures and 42 Open Problems — Consistency and sample complexity of Multireference Alignment

In the standard cyclic multireference-alignment model, an unknown signal θ∈Rd\theta\in\mathbb{R}^d is observed through independent samples

Yi=Rℓiθ+σξi,i=1,…,n,Y_i=R_{\ell_i}\theta+\sigma\xi_i,\qquad i=1,\ldots,n,

where RℓR_\ell is circular shift by ℓ∈Zd\ell\in\mathbb{Z}_d, the shifts ℓi\ell_i are independent and uniform on Zd\mathbb{Z}_d, and ξi∼N(0,Id)\xi_i\sim\mathcal{N}(0,I_d) are independent of the shifts. Signals are identifiable only up to a common circular shift; write ρ(z,θ)=min⁡ℓ∈Zd∥z−Rℓθ∥2\rho(z,\theta)=\min_{\ell\in\mathbb{Z}_d}\|z-R_\ell\theta\|_2. With a fixed Fourier convention, the power spectrum is the vector (∣θ^k∣2)k∈Zd(|\widehat\theta_k|^2)_{k\in\mathbb{Z}_d}. The fixed-power-spectrum question is whether a maximum-likelihood estimate constrained to signals zz with ∣z^k∣2=∣θ^k∣2|\widehat z_k|^2=|\widehat\theta_k|^2 for every kk is consistent, meaning that its distance ρ(θ^n,θ)\rho(\widehat\theta_n,\theta) tends to zero as n→∞n\to\infty. The accompanying sample-complexity question asks how many observations are required to make this distance at most a prescribed ε>0\varepsilon>0 with a prescribed confidence. The consistency question is posed informally; in particular, fixing the true spectrum and constraining the estimate using a spectrum estimated from data are distinct formulations. Perry et al., The sample complexity of multi-reference alignment (arXiv:1707.00943) Moment Constraints and Phase Recovery for Multireference Alignment (arXiv:2409.04868)

Background

MRA is a tractable model for recovering signals obscured by latent transformations, with motivation including image registration and cryo-electron microscopy. A central difficulty is that each observation has an unknown shift, so estimating the signal is not the same as averaging aligned observations. The method of invariants instead uses quantities unchanged by shifts. The second-order invariant, equivalently the power spectrum, determines Fourier magnitudes but generally not phases; the third-order invariant is related to the bispectrum, which generically determines a signal up to shift when its Fourier spectrum is nonvanishing. Estimating cubic statistics in high noise has variance of order σ6/n\sigma^6/n, pointing to a sample requirement proportional to σ6=SNR−3\sigma^6=\mathrm{SNR}^{-3} when the signal norm is normalized and SNR=1/σ2\mathrm{SNR}=1/\sigma^2. Perry et al., The sample complexity of multi-reference alignment (arXiv:1707.00943) Moment Constraints and Phase Recovery for Multireference Alignment (arXiv:2409.04868)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.