Sample Complexity Analysis of Multi-Target Detection via Markovian and Hard-Core Multi-Reference Alignment
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918415913975808 |
|---|---|
| author | Abraham, Kweku Balanov, Amnon Bendory, Tamir Esteve-Yagüe, Carlos |
| author_facet | Abraham, Kweku Balanov, Amnon Bendory, Tamir Esteve-Yagüe, Carlos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17775 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sample Complexity Analysis of Multi-Target Detection via Markovian and Hard-Core Multi-Reference Alignment Abraham, Kweku Balanov, Amnon Bendory, Tamir Esteve-Yagüe, Carlos Signal Processing Information Theory 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. |
| title | Sample Complexity Analysis of Multi-Target Detection via Markovian and Hard-Core Multi-Reference Alignment |
| topic | Signal Processing Information Theory |
| url | https://arxiv.org/abs/2510.17775 |