This paper considers the task of linear regression with shuffled labels,
i.e., $\mathbf Y = \mathbf \Pi \mathbf X \mathbf B + \mathbf W$, where $\mathbf
Y \in \mathbb R^{n\times m}, \mathbf Pi \in \mathbb R^{n\ti
本文研究了线性感知系统在无标签观测的情况下如何解决问题，着重于利用具有独立同分布条目的随机矩阵来解决。我们证明了如果感知矩阵 A 具有超采样率为 2 或更高，则可以在不知道 y 中观察顺序的情况下达到准确恢复 x 的目标，而且对于任何 2K 个 y 观测到的条目都足以恢复 x。 这个结果意味着具有超采样因子 2 的确定性未标记感知矩阵可以实现完美重建。