Recovering Structure of Noisy Data through Hypothesis Testing

Minoh Jeong, Alex Dytso, Martina Cardone, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper considers a noisy data structure recovery problem. Specifically, the goal is to investigate the following question: Given a noisy observation of the data, according to which permutation was the original data sorted? The main focus is on scenarios where data is generated according to an isotropic Gaussian distribution, and the perturbation consists of adding Gaussian noise with diagonal scalar covariance matrix. This problem is posed within a hypothesis testing framework. First, the optimal decision criterion is characterized and shown to be identical to the hypothesis of the observation. Then, by leveraging the structure of the optimal decision criterion, the probability of error is characterized. Finally, the logarithmic behavior (i.e., the exponent) of the probability of error is derived in the regime where the dimension of the data goes to infinity.

Original languageEnglish (US)
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1307-1312
Number of pages6
ISBN (Electronic)9781728164328
DOIs
StatePublished - Jun 2020
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States
Duration: Jul 21 2020Jul 26 2020

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2020-June
ISSN (Print)2157-8095

Conference

Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
CountryUnited States
CityLos Angeles
Period7/21/207/26/20

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Recovering Structure of Noisy Data through Hypothesis Testing'. Together they form a unique fingerprint.

  • Cite this

    Jeong, M., Dytso, A., Cardone, M., & Poor, H. V. (2020). Recovering Structure of Noisy Data through Hypothesis Testing. In 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings (pp. 1307-1312). [9174229] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2020-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT44484.2020.9174229