Sample Complexity Analysis of Multi-Target Detection via Markovian and Hard-Core Multi-Reference Alignment
Provides theoretical guarantees for cryo-EM image reconstruction by bridging the gap between idealized i.i.d. models and realistic non-i.i.d. data.
This paper analyzes the sample complexity of multi-target detection (MTD) with non-i.i.d. latent structures (Markovian and hard-core), showing that the convergence rate matches the i.i.d. multi-reference alignment (MRA) model up to a logarithmic factor, and that the number of patches required scales as σ^{2n_min} in the low-SNR regime.
Motivated by single-particle cryo-electron microscopy, we study the sample complexity of the multi-target detection (MTD) problem, in which an unknown signal appears multiple times at unknown locations within a long, noisy observation. We propose a patching scheme that reduces MTD to a non-i.i.d. multi-reference alignment (MRA) model. In the one-dimensional setting, the latent group elements form a Markov chain, and we show that the convergence rate of any estimator matches that of the corresponding i.i.d. MRA model, up to a logarithmic factor in the number of patches. Moreover, for estimators based on empirical averaging, such as the method of moments, the convergence rates are identical in both settings. We further establish an analogous result in two dimensions, where the latent structure arises from an exponentially mixing random field generated by a hard-core placement model. As a consequence, if the signal in the corresponding i.i.d. MRA model is determined by moments up to order $n_{\min}$, then in the low-SNR regime the number of patches required to estimate the signal in the MTD model scales as $Ï^{2n_{\min}}$, where $Ï^2$ denotes the noise variance.