Unlabeled Sensing with Random Linear Measurements

Understand

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.