Poster
Homomorphic Sensing
Manolis Tsakiris · Liangzu Peng

Tue Jun 11th 06:30 -- 09:00 PM @ Pacific Ballroom #167

A recent line of research termed "unlabeled sensing" and "shuffled linear regression" has been exploring under great generality the recovery of signals from subsampled and permuted measurements; a challenging problem in diverse fields of data science and machine learning. In this paper we introduce an abstraction of this problem which we call "homomorphic sensing". Given a linear subspace and a finite set of linear transformations we develop an algebraic theory which establishes conditions guaranteeing that points in the subspace are uniquely determined from their homomorphic image under some transformation in the set. As a special case, we recover known conditions for unlabeled sensing, as well as new results and extensions. On the algorithmic level we exhibit two dynamic programming based algorithms, which to the best of our knowledge are the first working solutions for the unlabeled sensing problem for small dimensions. One of them, additionally based on branch-and-bound, when applied to image registration under affine transformations, performs on par with or outperforms state-of-the-art methods on benchmark datasets.

Author Information

Manolis Tsakiris (Johns Hopkins University)
Liangzu Peng (ShanghaiTech University)

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

More from the Same Authors