Retrieving Data Permutations From Noisy Observations: Asymptotics

Minoh Jeong, Alex Dytso, Martina Cardone

    Research output: Contribution to journalArticlepeer-review

    Abstract

    This paper studies the problem of data permutation recovery, where the goal is to estimate the ordering of an n -dimensional data vector given a noisy observation of it. The focus is on scenarios where the noise is additive Gaussian with an arbitrary known covariance matrix. The goal is to characterize the probability of error and its behavior when a linear decoder (that is, a linear estimator followed by a sorting operation) is employed. First, a general expression is derived for the probability of error when a linear decoder is used. The derived expression holds for any continuous distribution of the input data vector, and when the noise has memory. Then, the rates of convergence of the probability of error in the low-noise and high-noise regimes are investigated when a simple linear decoder is used. It is shown that in the low-noise regime, the probability of error can quadratically increase with n, and in the high-noise regime it behaves as 1-1/n! for several distributions of interest. Finally, upper and lower bounds on the probability of correctness with respect to n are derived for the case of an i.i.d. data distribution and show that the rate of convergence is at least exponential in n. The results showcase that the permutation recovery problem is noise dominated, which motivates the study of more relaxed versions of the permutation recovery problem that are also discussed.

    Original languageEnglish (US)
    Pages (from-to)2999-3017
    Number of pages19
    JournalIEEE Transactions on Information Theory
    Volume70
    Issue number4
    DOIs
    StatePublished - Apr 1 2024

    Bibliographical note

    Publisher Copyright:
    © 1963-2012 IEEE.

    Keywords

    • Gaussian noise
    • Permutation
    • asymptotics
    • data ranking
    • isotonic regression
    • order statistics

    Fingerprint

    Dive into the research topics of 'Retrieving Data Permutations From Noisy Observations: Asymptotics'. Together they form a unique fingerprint.

    Cite this