Paper Info
Title
Unlabeled sensing: Solving a linear system with unordered measurements.
Abstract
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 one 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. While the proof is constructive, it uses a combinatorial algorithm which is not practical, leaving the question of complexity open. In terms of applications, the unlabeled sensing problem is related to a popular method in robotics called simultaneous location and mapping (SLAM).
Year
Venue
Field
2015
2015 53RD ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON)
Random variable,Mathematical optimization,System of linear equations,Oversampling,Linear system,Computer science,Matrix (mathematics),Probability distribution,Compressed sensing,Random matrix
DocType
ISSN
Citations 
Conference
2474-0195
1
PageRank 
References 
Authors
0.36
6
3
Name
Order
Citations
PageRank
Jayakrishnan Unnikrishnan128021.34
Saeid Haghighatshoar212615.94
Martin Vetterli3139262397.68