Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics
Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics
复制标题
DOI：
10.1109/isit45174.2021.9518137
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Minoh Jeong;Alex Dytso;Martina Cardone
中科院分区：
文献类型：
--
作者：
Minoh Jeong;Alex Dytso;Martina Cardone
本文考虑了在高斯噪声中观察到的n维随机向量X的置换的恢复问题。首先，当使用线性解码器(即，线性估计器之后进行排序操作)时，推导出错误概率的一般表达式。在对X的分布作最小假设的情况下，当噪声具有记忆性时，所导出的表达式仍然成立。其次，对于各向同性噪声(即具有对角标量协方差矩阵的噪声)的情况，在高噪声和低噪声区域中表征了错误概率的收敛速度。在低噪声区域，对于每个维度$n$，误差概率与$\sigma$成正比，其中$\sigma$是噪声标准差。此外，对几种分布的斜率进行了精确的计算，结果表明斜率在n元内呈二次曲线分布。在高噪声区，对于每一维n，正确概率表现为$1/\sigma，并给出了收敛速度的精确表达式。
This paper considers the problem of recovering the permutation of an n-dimensional random vector X observed in Gaussian noise. First, a general expression for the probability of error is derived when a linear decoder (i.e., linear estimator followed by a sorting operation) is used. The derived expression holds with minimal assumptions on the distribution of X and when the noise has memory. Second, for the case of isotropic noise (i.e., noise with a diagonal scalar covariance matrix), the rates of convergence of the probability of error are characterized in the high and low noise regimes. In the low noise regime, for every dimension $n$, the probability of error is shown to behave proportionally to $\sigma$, where $\sigma$ is the noise standard deviation. Moreover, the slope is computed exactly for several distributions and it is shown to behave quadratically in $n$. In the high noise regime, for every dimension $n$, the probability of correctness is shown to behave as $1/\sigma$, and the exact expression for the rate of convergence is also provided.