Linear regression with an unknown permutation: Statistical and computational limits
Linear regression with an unknown permutation: Statistical and computational limits
复制标题
DOI：
10.1109/allerton.2016.7852261
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
A. Pananjady;M. Wainwright;T. Courtade
中科院分区：
文献类型：
--
作者：
A. Pananjady;M. Wainwright;T. Courtade
考虑具有未知排列的噪声线性观察模型，基于观察 y = Π*Ax* + w，其中 x* ∈ ℝd 是未知向量，Π* 是未知的 n × n 排列矩阵，w ∈ ℝn 是加性高斯噪声。我们分析了随机设计设置中的排列恢复问题，其中矩阵 A 的条目是独立同分布的。根据标准高斯分布，并建立 SNR、样本大小 n 和维度 d 的尖锐条件，在该条件下 Π* 可以精确且近似地恢复。在计算方面，我们表明 Π* 的最大似然估计是 NP 难计算的，同时还提供了 d = 1 时的多项式时间算法。
Consider a noisy linear observation model with an unknown permutation, based on observing y = Π*Ax* + w, where x* ∈ ℝd is an unknown vector, Π* is an unknown n × n permutation matrix, and w ∈ ℝn is additive Gaussian noise. We analyze the problem of permutation recovery in a random design setting in which the entries of the matrix A are drawn i.i.d. from a standard Gaussian distribution, and establish sharp conditions on the SNR, sample size n, and dimension d under which Π* is exactly and approximately recoverable. On the computational front, we show that the maximum likelihood estimate of Π* is NP-hard to compute, while also providing a polynomial time algorithm when d = 1.