TY - GEN
T1 - Sample complexity of the boolean multireference alignment problem
AU - Abbe, Emmanuel
AU - Pereira, Joãto M.
AU - Singer, Amit
N1 - Funding Information:
E. A. is partially supported by NSF CAREER Award CCF-1552131 and ARO grant W911NF-16-1-0051.
Funding Information:
ACKNOWLEDGMENT A. S. and J. P. were partially supported by Award Number R01GM090200 from the NIGMS, FA9550-12-1-0317 from AFOSR, Simons Foundation Investigator Award and Simons Collaborations on Algorithms and Geometry, and the Moore Foundation Data-Driven Discovery Investigator Award.
Publisher Copyright:
© 2017 IEEE.
PY - 2017/8/9
Y1 - 2017/8/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85034101560&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034101560&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2017.8006742
DO - 10.1109/ISIT.2017.8006742
M3 - Conference contribution
C2 - 29755834
AN - SCOPUS:85034101560
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1316
EP - 1320
BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017
Y2 - 25 June 2017 through 30 June 2017
ER -