Unlabeled Sensing with Random Linear Measurements

From the introduction:

Unlabeled sensing has potential applications in a number of different fields. Consider the following example. You are blindfolded in a room, and the floor is not flat but a 3 dimensional terrain model. You can sample the height, but you dont know where you take the samples. Is it possible, under some assumption about the terrain model, to recover the location of the samples and the shape of the terrain? This is related to a celebrated problem in robotics called simultaneous location and mapping (SLAM) [8]. Similar data-association problems also arise in the task of assigning observations to targets in multi-target tracking problems that arise in radar applications [9]. More generally, consider the problem of reconstructing a spatial field from samples. Let x denote the representation of the field in some K-dimensional basis. Each measurement can be interpreted as an inner product of x with a “sampling vector” unique to the location where the sample was taken. Consider a mobile sensing scheme [10, 11] where a moving sensor samples the field at N different locations. Further suppose that the mobile sensor does not have access to accurate spatial measurements, although the set of M potential sampling locations and the sampling vectors corresponding to the potential locations are known a priori. The field reconstruction problem one faces in this situation is precisely the unlabeled sensing problem studied in this paper. A similar situation arises in time-domain sampling in the presence of clock jitter [12] which makes it impossible to associate sampled observations to the correct time indices. There is some prior work on reconstruction of bandlimited signals from samples at unknown locations. In [13] an approximate solution to this problem is proposed under the setting of continuous-time measurements and bandlimited signals. In [14], an iterative procedure to reconstruct discrete-time bandlimited signals is proposed. Our work differs from that of these papers in that we do not restrict ourselves to a bandlimited signal model. Our main results are focused on the setting in which the sampling vectors are randomly distributed. In such settings we show that an exact solution to the unlabeled sensing problem is possible when we take twice as many samples as required in classic labeled sensing.

Enjoy the paper:

Unlabeled Sensing with Random Linear Measurements by Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, Martin Vetterli

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.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.