Allerton 2015 Paper Abstract


Paper ThA1.2

Unnikrishnan, Jayakrishnan (General Electric), Haghighatshoar, Saeid (TU Berlin), Vetterli, Martin (EPFL)

Unlabeled Sensing: Solving a Linear System with Unordered Measurements

Scheduled for presentation during the Invited Session "Distributed Decision Making" (ThA1), Thursday, October 1, 2015, 08:50−09:10, Library

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Statistical Signal Processing


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).



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  08:40:32 PST  Terms of use