Timezone: »

Homomorphic Sensing: Sparsity and Noise
Liangzu Peng · Boshi Wang · Manolis Tsakiris

Wed Jul 21 09:00 AM -- 11:00 AM (PDT) @ None #None

\emph{Unlabeled sensing} is a recent problem encompassing many data science and engineering applications and typically formulated as solving linear equations whose right-hand side vector has undergone an unknown permutation. It was generalized to the \emph{homomorphic sensing} problem by replacing the unknown permutation with an unknown linear map from a given finite set of linear maps. In this paper we present tighter and simpler conditions for the homomorphic sensing problem to admit a unique solution. We show that this solution is locally stable under noise, while under a sparsity assumption it remains unique under less demanding conditions. Sparsity in the context of unlabeled sensing leads to the problem of \textit{unlabeled compressed sensing}, and a consequence of our general theory is the existence under mild conditions of a unique sparsest solution. On the algorithmic level, we solve unlabeled compressed sensing by an iterative algorithm validated by synthetic data experiments. Finally, under the unifying homomorphic sensing framework we connect unlabeled sensing to other important practical problems.

Author Information

Liangzu Peng (ShanghaiTech University)
Boshi Wang (ShanghaiTech University)
Manolis Tsakiris (ShanghaiTech University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors