Unlabeled Sensing With Random Linear Measurements
| Autor: | Saeid Haghighatshoar, Martin Vetterli, Jayakrishnan Unnikrishnan |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Physics Computer Science - Information Theory Information Theory (cs.IT) Probability (math.PR) Dimension (graph theory) Zero (complex analysis) Order (ring theory) 020206 networking & telecommunications 02 engineering and technology Library and Information Sciences 01 natural sciences Computer Science Applications Combinatorics 010104 statistics & probability Matrix (mathematics) Compressed sensing FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Probability distribution 0101 mathematics Random matrix Realization (systems) Mathematics - Probability Information Systems |
| Zdroj: | IEEE Transactions on Information Theory. 64:3237-3253 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2018.2809002 |
| Popis: | 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. Comment: Submitted to IEEE Transactions on Information Theory, Nov 2015 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|