  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
y = Ax when the order of the observations in the vector y is unknown. Focusing
on the setting in which A is a random matrix with i.i.d. entries, we show that
if the sensing matrix A admits an oversampling ratio of 2 or higher, then with
probability 1 it is possible to recover x exactly without the knowledge of the
order of the observations in y. Furthermore, if x is of dimension K, then any
2K entries of y are sufficient to recover x. 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 recovery is
guaranteed for all possible choices of x. 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 x, the
recovery error tends to zero as the signal-to-noise-ratio tends to infinity.
The question of universal stability is unclear. We also obtain a converse of
the result in the noiseless case: If the number of observations in y is less
than 2K, then with probability 1, universal recovery fails, i.e., with
probability 1, there exists distinct choices of x which lead to the same
unordered list of observations in y. 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" (SLAM), multi-target tracking
applications, and in sampling signals in the presence of jitter.
