Linear regression without correspondence
Linear regression without correspondence
复制标题
DOI：
--
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Daniel J. Hsu;K. Shi;Xiaorui Sun
中科院分区：
文献类型：
--
作者：
Daniel J. Hsu;K. Shi;Xiaorui Sun
本文考虑了当协变量和响应之间的对应关系未知时线性回归的算法和统计方面。首先，给出了任意常维自然最小二乘优化问题的全多项式时间逼近格式。接下来，在平均情况和无噪声的情况下，响应完全对应于标准多元正态分布中i.i.d的线性函数，基于格基约简的有效算法可以精确地恢复任意维的未知线性函数。最后，建立了用任意估计量近似恢复未知线性函数的信噪比下界。
This article considers algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown. First, a fully polynomial-time approximation scheme is given for the natural least squares optimization problem in any constant dimension. Next, in an average-case and noise-free setting where the responses exactly correspond to a linear function of i.i.d. draws from a standard multivariate normal distribution, an efficient algorithm based on lattice basis reduction is shown to exactly recover the unknown linear function in arbitrary dimension. Finally, lower bounds on the signal-to-noise ratio are established for approximate recovery of the unknown linear function by any estimator.