Unlabeled Sensing With Random Linear Measurements

We study the problem of solving a linear sensing system when the observations are unlabeled. Specifically we seek a solution to a linear system of equations <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}= {\mathbf{A}} {\mathbf{x}} $ </tex-math></inline-formula> when the order of the observations in the vector <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}$ </tex-math></inline-formula> is unknown. Focusing on the setting in which <inline-formula> <tex-math notation="LaTeX">${\mathbf{A}}$ </tex-math></inline-formula> is a random matrix with i.i.d. entries, we show that if the sensing matrix <inline-formula> <tex-math notation="LaTeX">${\mathbf{A}}$ </tex-math></inline-formula> admits an oversampling ratio of 2 or higher, then, with probability 1, it is possible to recover <inline-formula> <tex-math notation="LaTeX">${\mathbf{x}}$ </tex-math></inline-formula> exactly without the knowledge of the order of the observations in <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}$ </tex-math></inline-formula>. Furthermore, if <inline-formula> <tex-math notation="LaTeX">${\mathbf{x}}$ </tex-math></inline-formula> is of dimension <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula>, then any <inline-formula> <tex-math notation="LaTeX">$2K$ </tex-math></inline-formula> entries of <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}$ </tex-math></inline-formula> are sufficient to recover <inline-formula> <tex-math notation="LaTeX">${\mathbf{x}}$ </tex-math></inline-formula>. This result implies the existence of deterministic unlabeled sensing matrices with an oversampling factor of 2 that admit perfect reconstruction. The result is universal in that conditioned on the realization of matrix <inline-formula> <tex-math notation="LaTeX">${\mathbf{A}}$ </tex-math></inline-formula>, recovery is guaranteed for all possible choices of <inline-formula> <tex-math notation="LaTeX">${\mathbf{x}}$ </tex-math></inline-formula>. While the proof is constructive, it uses a combinatorial algorithm which is not practical, leaving the question of complexity open. We also analyze a noisy version of the problem and show that local stability is guaranteed by the solution. In particular, for every <inline-formula> <tex-math notation="LaTeX">${\mathbf{x}}$ </tex-math></inline-formula>, the recovery error tends to zero as the signal-to-noise ratio tends to infinity. The question of universal stability is unclear. In addition, we obtain a converse of the result in the noiseless case: If the number of observations in <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}$ </tex-math></inline-formula> is less than <inline-formula> <tex-math notation="LaTeX">$2K$ </tex-math></inline-formula>, then with probability 1, universal recovery fails, i.e., with probability 1, there exist distinct choices of <inline-formula> <tex-math notation="LaTeX">${\mathbf{x}}$ </tex-math></inline-formula> which lead to the same unordered list of observations in <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}$ </tex-math></inline-formula>. We also present extensions of the result of the noiseless case to special cases with non-i.i.d. entries in <inline-formula> <tex-math notation="LaTeX">${\mathbf{A}}$ </tex-math></inline-formula>, and to a different setting in which the labels of a portion of the observations <inline-formula> <tex-math notation="LaTeX">${\mathbf{y}}$ </tex-math></inline-formula> are known. In terms of applications, the unlabeled sensing problem is related to data association problems encountered in different domains including robotics where it is appears in a method called “simultaneous localization and mapping”, multi-target tracking applications, and in sampling signals in the presence of jitter.