# A note on the sample complexity of multi-target detection

arXiv: https://arxiv.org/abs/2501.11980 · HTML: https://mlsanity.com/paper/2501.11980/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2025.

## Built on by (most cited first, 1 of 1)

- [Solving ill-conditioned polynomial equations using score-based priors with application to multi-target detection](https://mlsanity.com/paper/2509.11397/) (2025)

## Abstract (arXiv)

This work studies the sample complexity of the multi-target detection (MTD) problem, which involves recovering a signal from a noisy measurement containing multiple instances of a target signal in unknown locations, each transformed by a random group element. This problem is primarily motivated by single-particle cryo-electron microscopy (cryo-EM), a groundbreaking technology for determining the structures of biological molecules. We establish upper and lower bounds for various MTD models in the high-noise regime as a function of the group, the distribution over the group, and the arrangement of signal occurrences within the measurement. The lower bounds are established through a reduction to the related multi-reference alignment problem, while the upper bounds are derived from explicit recovery algorithms utilizing autocorrelation analysis. These findings provide fundamental insights into estimation limits in noisy environments and lay the groundwork for extending this analysis to more complex applications, such as cryo-EM.