TY - JOUR
T1 - Multi-target detection with an arbitrary spacing distribution
AU - Lan, Ti Yen
AU - Bendory, Tamir
AU - Boumal, Nicolas
AU - Singer, Amit
N1 - Funding Information:
Manuscript received June 19, 2019; revised January 22, 2020; accepted February 17, 2020. Date of publication February 24, 2020; date of current version March 13, 2020. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Hassan Mansour. This work was supported in part by Award R01GM090200 from the NIGMS, FA9550-17-1-0291 from AFOSR, Simons Foundation Math+X Investigator Award, the Moore Foundation Data-Driven Discovery Investigator Award, and NSF BIGDATA Award IIS-1837992. The work of N. Boumal was supported by NSF Award DMS-1719558. (Corresponding author: Ti-Yen Lan.) Ti-Yen Lan, Nicolas Boumal, and Amit Singer are with the Program in Applied and Computational Mathematics and the Mathematics Department, Princeton University, Princeton, NJ 08544 USA (e-mail: tiyenlan@princeton.edu; nboumal@math.princeton.edu; amits@math.princeton.edu).
Publisher Copyright:
© 1991-2012 IEEE.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Autocorrelation analysis
KW - Blind deconvolution
KW - Cryo-em
KW - Expectation maximization
KW - Frequency marching
UR - http://www.scopus.com/inward/record.url?scp=85082395329&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082395329&partnerID=8YFLogxK
U2 - 10.1109/TSP.2020.2975943
DO - 10.1109/TSP.2020.2975943
M3 - Article
AN - SCOPUS:85082395329
SN - 1053-587X
VL - 68
SP - 1589
EP - 1601
JO - IRE Transactions on Audio
JF - IRE Transactions on Audio
M1 - 9007472
ER -