Permutations Unlabeled beyond Sampling Unknown
share
A recent result on unlabeled sampling states that with probability one over iid Gaussian matrices A, any x can be uniquely recovered from y = Π Ax, where Π is an unknown permutation, as soon as A has twice as many rows as columns. In this letter, we show that this condition on A implies something much stronger: that an unknown vector x can be recovered from measurements y = T A x, when T belongs to an arbitrary set of invertible, diagonalizable linear transformations T, with T being finite or countably infinite. When T is an unknown permutation, this models the classical unlabeled sampling problem. We show that for almost all A with at least twice as many rows as columns, all x can be recovered uniquely, or up to a scale depending on T, and that the condition on the size of A is necessary. Our simple proof and based on vector space geometry. Specializing to permutations we obtain a simplified proof of the uniqueness result of Unnikrishnan, Haghighatshoar and Vetterli. In this letter we are only concerned with uniqueness; stability and algorithms are left for future work.
READ FULL TEXT