Unlabeled Sensing

Like other data sensing problems, in unlabeled sensing, the target is to solve the equation y = Φx by finding vector x given a set of sample values in vector y as well as the matrix Φ. However, the main challenge in unlabeled sensing is that the correct order of the sample values in vector y is not available. We only have access to the unordered sample values and not to their sorted indices and labellings. Thus, in unlabeled sensing, we have to recover both the vector x as well as the correct ordering of the sample values in y. In this project, we want to answer two main questions regarding data recovery in unlabeled sensing. First, given a set of unordered sample values and specific matrix Φ, is there a unique solution? By considering different configurations in 2-dimensional plane, we prove that there exists no unique solution for few special configurations of Φ where we exactly quantify. However, by simulations we show that in some other configurations uniqueness is guaranteed. In the noisy case, uniqueness depends on configuration of Φ as well as noise level over sample values. Therefore, we consider probability of existence of unique solution in noisy case. Whether unique solution exists or not, the second investigated question is how to define an efficient algorithm to find all possible solutions with low complexity. We propose Distance-Based Algorithm (DBA) as an efficient algorithm for finding all possible solutions with noiseless sample values. Generalized DBA is also proposed as an extension of DBA which can be utilized when noisy sample values are accessible. The main advantages of DBA are its low complexity compared to combinatorial algorithms and also applicability in noisy cases. Simulation results and theoretical proofs are provided in each section to validate our claims.

Vetterli, Martin
Semester Project

Note: The status of this file is: Involved Laboratories Only

 Record created 2016-02-02, last modified 2018-09-13

Midterm and final presentations:
Download fulltextRAR
Python codes:
Download fulltextRAR
Download fulltextPDF
Rate this document:

Rate this document:
(Not yet reviewed)