TY - GEN

T1 - Recovering Structure of Noisy Data through Hypothesis Testing

AU - Jeong, Minoh

AU - Dytso, Alex

AU - Cardone, Martina

AU - Poor, H. Vincent

N1 - Funding Information:
The work of M. Jeong and M. Cardone was supported in part by the U.S. National Science Foundation under Grant CCF-1849757. The work of A. Dytso and H. V. Poor was supported in part by the U.S. National Science Foundation under Grant CCF-1908308
Publisher Copyright:
© 2020 IEEE.

PY - 2020/6

Y1 - 2020/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85090404759&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85090404759&partnerID=8YFLogxK

U2 - 10.1109/ISIT44484.2020.9174229

DO - 10.1109/ISIT44484.2020.9174229

M3 - Conference contribution

AN - SCOPUS:85090404759

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1307

EP - 1312

BT - 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2020 IEEE International Symposium on Information Theory, ISIT 2020

Y2 - 21 July 2020 through 26 July 2020

ER -