Sample complexity of the boolean multireference alignment problem

Emmanuel Abbe; Joãto M. Pereira; Amit Singer

doi:10.1109/ISIT.2017.8006742

Sample complexity of the boolean multireference alignment problem

Emmanuel Abbe, Joãto M. Pereira, Amit Singer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Scopus citations

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.

Original language	English (US)
Title of host publication	2017 IEEE International Symposium on Information Theory, ISIT 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1316-1320
Number of pages	5
ISBN (Electronic)	9781509040964
DOIs	https://doi.org/10.1109/ISIT.2017.8006742
State	Published - Aug 9 2017
Event	2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany Duration: Jun 25 2017 → Jun 30 2017

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Other

Other	2017 IEEE International Symposium on Information Theory, ISIT 2017
Country/Territory	Germany
City	Aachen
Period	6/25/17 → 6/30/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2017.8006742

Cite this

Abbe, E., Pereira, J. M., & Singer, A. (2017). Sample complexity of the boolean multireference alignment problem. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 1316-1320). [8006742] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8006742

@inproceedings{ab2d514c333741299e3c8819cfc493c5,

title = "Sample complexity of the boolean multireference alignment problem",

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.",

author = "Emmanuel Abbe and Pereira, {Jo{\~a}to M.} and Amit Singer",

note = "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: {\textcopyright} 2017 IEEE.; 2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = aug,

day = "9",

doi = "10.1109/ISIT.2017.8006742",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1316--1320",

booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",

address = "United States",

}

Abbe, E, Pereira, JM & Singer, A 2017, Sample complexity of the boolean multireference alignment problem. in 2017 IEEE International Symposium on Information Theory, ISIT 2017., 8006742, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1316-1320, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 6/25/17. https://doi.org/10.1109/ISIT.2017.8006742

Sample complexity of the boolean multireference alignment problem. / Abbe, Emmanuel; Pereira, Joãto M.; Singer, Amit.
2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1316-1320 8006742 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Sample complexity of the boolean multireference alignment problem

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this