  The unlabeled sensing problem is to recover an unknown signal from permuted
linear measurements. We propose an alternating minimization algorithm with a
suitable initialization for the widely considered k-sparse permutation model.
Assuming either a Gaussian measurement matrix or a sub-Gaussian signal, we
upper bound the initialization error for the r-local and k-sparse permutation
models in terms of the block size $r$ and the number of shuffles k,
respectively. Our algorithm is computationally scalable and, compared to
baseline methods, achieves superior performance on real and synthetic datasets.
