### Abstract

A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar, and Vetterli states that with probability one over Gaussian random matrices A with iid entries, 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.

Original language | English (US) |
---|---|

Article number | 8678393 |

Pages (from-to) | 823-827 |

Number of pages | 5 |

Journal | IEEE Signal Processing Letters |

Volume | 26 |

Issue number | 6 |

DOIs | |

State | Published - Jun 2019 |

### Keywords

- Sampling
- shuffled regression
- unknown permutation
- unknown transformation
- unlabeled sampling

### ASJC Scopus subject areas

- Signal Processing
- Electrical and Electronic Engineering
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Permutations Unlabeled beyond Sampling Unknown'. Together they form a unique fingerprint.

## Cite this

*IEEE Signal Processing Letters*,

*26*(6), 823-827. [8678393]. https://doi.org/10.1109/LSP.2019.2908505