A note on the sample complexity of multi-target detection
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Note on Target Q-learning For Solving Finite MDPs with A Generative Oracle
Q-learning with function approximation could diverge in the off-policy setting and the target network is a powerful technique to address this issue. In this manuscript, we examine the sample complexity of the associated …
Q-LearningGuarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples
A driving force behind the diverse applicability of modern machine learning is the ability to extract meaningful features across many sources. However, many practical domains involve data that are non-identically distrib…
Representation LearningMedDec: A Dataset for Extracting Medical Decisions from Discharge Summaries
Medical decisions directly impact individuals' health and well-being. Extracting decision spans from clinical notes plays a crucial role in understanding medical decision-making processes. In this paper, we develop a new…
Decision MakingSome Notes on the Sample Complexity of Approximate Channel Simulation
Channel simulation algorithms can efficiently encode random samples from a prescribed target distribution $Q$ and find applications in machine learning-based lossy data compression. However, algorithms that encode exact …
Data CompressionCompressed-Domain Detection and Estimation for Colocated MIMO Radar
This paper proposes compressed domain signal processing (CSP) multiple input multiple output (MIMO) radar, a MIMO radar approach that achieves substantial sample complexity reduction by exploiting the idea of CSP. CSP MI…
compressed sensingCompressive SensingData Compression