  A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar and
Vetterli states that with probability one over iid Gaussian matrices $A$, any
$x$ can be uniquely recovered from an unknown permutation of $y = A x$ as soon
as $A$ has at least twice as many rows as columns. 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 the unknown $T$ belongs to an
arbitrary set of invertible, diagonalizable linear transformations
$\mathcal{T}$. The set $\mathcal{T}$ can be finite or countably infinite. When
it is the set of $m \times m$ permutation matrices, we have 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 either uniquely, or up to a
scale depending on $\mathcal{T}$, and that the condition on the size of $A$ is
necessary. Our proof is 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.
