On Estimation under Noisy Order Statistics

Alex Dytso; Martina Cardone; Mishfad S. Veedu; H. Vincent Poor

doi:10.1109/ISIT.2019.8849813

On Estimation under Noisy Order Statistics

Alex Dytso, Martina Cardone, Mishfad S. Veedu, H. Vincent Poor

Electrical and Computer Engineering

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

10 Scopus citations

Abstract

This paper presents an estimation framework to assess the performance of the sorting function over data that is perturbed. In particular, the performance is measured in terms of the Minimum Mean Square Error (MMSE) between the values of the sorting function computed on the data without perturbation and the estimate that uses the sorting function applied to the perturbed data. It is first shown that, under certain conditions satisfied by the practically relevant Gaussian noise perturbation, the optimal estimator can be expressed as a linear combination of estimators on the unsorted data. Then, a suboptimal estimator is proposed, and its performance is evaluated and compared to the optimal estimator. Finally, a lower bound on the desired MMSE is derived when data is i.i.d. and has a Gaussian distribution. This is accomplished by solving a new problem that consists of estimating the norm of an unsorted vector from a noisy observation of it.

Original language	English (US)
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	36-40
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849813
State	Published - Jul 2019
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: Jul 7 2019 → Jul 12 2019

Publication series

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

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	7/7/19 → 7/12/19

Bibliographical note

Funding Information:
The work of A. Dytso and H. V. Poor was supported in part by the U.S. National Science Foundation under Grants CCF-0939370 and CCF-1513915. The work of M. Cardone was supported in part by the U.S. National Science Foundation under Grant CCF-1849757.

Publisher Copyright:
© 2019 IEEE.

Publisher link

10.1109/ISIT.2019.8849813

Find It

Find It at U of M Libraries

Cite this

Dytso, A., Cardone, M., Veedu, M. S., & Vincent Poor, H. (2019). On Estimation under Noisy Order Statistics. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 36-40). Article 8849813 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849813

On Estimation under Noisy Order Statistics. / Dytso, Alex; Cardone, Martina; Veedu, Mishfad S. et al.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 36-40 8849813 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

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

Dytso, A, Cardone, M, Veedu, MS & Vincent Poor, H 2019, On Estimation under Noisy Order Statistics. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849813, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 36-40, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/7/19. https://doi.org/10.1109/ISIT.2019.8849813

@inproceedings{115f80a26da24ba6a9766cfe7c181dc3,

title = "On Estimation under Noisy Order Statistics",

abstract = "This paper presents an estimation framework to assess the performance of the sorting function over data that is perturbed. In particular, the performance is measured in terms of the Minimum Mean Square Error (MMSE) between the values of the sorting function computed on the data without perturbation and the estimate that uses the sorting function applied to the perturbed data. It is first shown that, under certain conditions satisfied by the practically relevant Gaussian noise perturbation, the optimal estimator can be expressed as a linear combination of estimators on the unsorted data. Then, a suboptimal estimator is proposed, and its performance is evaluated and compared to the optimal estimator. Finally, a lower bound on the desired MMSE is derived when data is i.i.d. and has a Gaussian distribution. This is accomplished by solving a new problem that consists of estimating the norm of an unsorted vector from a noisy observation of it.",

author = "Alex Dytso and Martina Cardone and Veedu, {Mishfad S.} and {Vincent Poor}, H.",

note = "Funding Information: The work of A. Dytso and H. V. Poor was supported in part by the U.S. National Science Foundation under Grants CCF-0939370 and CCF-1513915. The work of M. Cardone was supported in part by the U.S. National Science Foundation under Grant CCF-1849757. Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/ISIT.2019.8849813",

language = "English (US)",

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

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

pages = "36--40",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

TY - GEN

T1 - On Estimation under Noisy Order Statistics

AU - Dytso, Alex

AU - Cardone, Martina

AU - Veedu, Mishfad S.

AU - Vincent Poor, H.

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

PY - 2019/7

Y1 - 2019/7

N2 - This paper presents an estimation framework to assess the performance of the sorting function over data that is perturbed. In particular, the performance is measured in terms of the Minimum Mean Square Error (MMSE) between the values of the sorting function computed on the data without perturbation and the estimate that uses the sorting function applied to the perturbed data. It is first shown that, under certain conditions satisfied by the practically relevant Gaussian noise perturbation, the optimal estimator can be expressed as a linear combination of estimators on the unsorted data. Then, a suboptimal estimator is proposed, and its performance is evaluated and compared to the optimal estimator. Finally, a lower bound on the desired MMSE is derived when data is i.i.d. and has a Gaussian distribution. This is accomplished by solving a new problem that consists of estimating the norm of an unsorted vector from a noisy observation of it.

AB - This paper presents an estimation framework to assess the performance of the sorting function over data that is perturbed. In particular, the performance is measured in terms of the Minimum Mean Square Error (MMSE) between the values of the sorting function computed on the data without perturbation and the estimate that uses the sorting function applied to the perturbed data. It is first shown that, under certain conditions satisfied by the practically relevant Gaussian noise perturbation, the optimal estimator can be expressed as a linear combination of estimators on the unsorted data. Then, a suboptimal estimator is proposed, and its performance is evaluated and compared to the optimal estimator. Finally, a lower bound on the desired MMSE is derived when data is i.i.d. and has a Gaussian distribution. This is accomplished by solving a new problem that consists of estimating the norm of an unsorted vector from a noisy observation of it.

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

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

U2 - 10.1109/ISIT.2019.8849813

DO - 10.1109/ISIT.2019.8849813

M3 - Conference contribution

AN - SCOPUS:85073144621

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 36

EP - 40

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

PB - Institute of Electrical and Electronics Engineers Inc.

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

Y2 - 7 July 2019 through 12 July 2019

ER -

On Estimation under Noisy Order Statistics

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this