论文标题
线性回归无通信通过凹面最小化
Linear Regression without Correspondences via Concave Minimization
论文作者
论文摘要
线性回归没有对应关系涉及线性回归设置中信号的恢复，其中观测值和线性函数之间的对应关系未知。当信号的尺寸大于一个时，相关的最大似然函数是NP-硬化。为了优化该目标功能，我们将其重新将其重新定义为一个最小化问题，我们通过分支机构和结合来解决。这是一个可计算的搜索空间来支持的，这是一个通过凸封膜最小化的有效下限方案和精制的上限，这都是自然而然的，这都是凹面最小化的重新构造。最终的算法优于完全改组的数据的最先进方法，并且仍可以高达$ 8 $维的信号进行操作，这是先前工作中未触及的制度。
Linear regression without correspondences concerns the recovery of a signal in the linear regression setting, where the correspondences between the observations and the linear functionals are unknown. The associated maximum likelihood function is NP-hard to compute when the signal has dimension larger than one. To optimize this objective function we reformulate it as a concave minimization problem, which we solve via branch-and-bound. This is supported by a computable search space to branch, an effective lower bounding scheme via convex envelope minimization and a refined upper bound, all naturally arising from the concave minimization reformulation. The resulting algorithm outperforms state-of-the-art methods for fully shuffled data and remains tractable for up to $8$-dimensional signals, an untouched regime in prior work.
