Multi-target detection with an arbitrary spacing distribution

Ti Yen Lan, Tamir Bendory, Nicolas Boumal, Amit Singer

Research output: Contribution to journalArticle

Abstract

Motivated by the structure reconstruction problem in single-particle cryo-electron microscopy, we consider the multi-target detection model, where multiple copies of a target signal occur at unknown locations in a long measurement, further corrupted by additive Gaussian noise. At low noise levels, one can easily detect the signal occurrences and estimate the signal by averaging. However, in the presence of high noise, which is the focus of this paper, detection is impossible. Here, we propose two approaches - autocorrelation analysis and an approximate expectation maximization algorithm - to reconstruct the signal without the need to detect signal occurrences in the measurement. In particular, our methods apply to an arbitrary spacing distribution of signal occurrences. We demonstrate reconstructions with synthetic data and empirically show that the sample complexity of both methods scales as SNR{}^{-3} in the low SNR regime.

Original languageEnglish (US)
Article number9007472
Pages (from-to)1589-1601
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume68
DOIs
StatePublished - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Electrical and Electronic Engineering

Keywords

  • Autocorrelation analysis
  • Blind deconvolution
  • Cryo-em
  • Expectation maximization
  • Frequency marching

Fingerprint Dive into the research topics of 'Multi-target detection with an arbitrary spacing distribution'. Together they form a unique fingerprint.

  • Cite this