Sample Complexity of the Boolean Multireference Alignment Problem

2017/01/26 by Emmanuel Abbé, Abbe, Emmanuel, João M. Pereira +3 · 2 citations
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Wireless Communication Security Techniques

paper · pdf · doi:10.48550/arxiv.1701.07540

openalex publication_date 2017/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Boolean multireference alignment problem consists in recovering a Boolean signal from multiple shifted and noisy observations. In this paper we obtain an expression for the error exponent of the maximum A posteriori decoder. This expression is used to characterize the number of measurements needed for signal recovery in the low SNR regime, in terms of higher order autocorrelations of the signal. The characterization is explicit for various signal dimensions, such as prime and even dimensions.

Cited by

• If you can distinguish, you can express: Galois theory, Stone--Weierstrass, machine learning, and linguistics
• Generic orbits, normal bases, and generation degree for fields of rational invariants

Related

• Multireference Alignment is Easier with an Aperiodic Translation\n Distribution
• Super-resolution multi-reference alignment
• Heterogeneous multireference alignment: a single pass approach
• Multireference Alignment using Semidefinite Programming
• Unbiasing Procedures for Scale-invariant Multi-reference Alignment