  The unlabeled sensing problem is to solve a noisy linear system of equations
under unknown permutation of the measurements. We study a particular case of
the problem where the permutations are restricted to be r-local, i.e. the
permutation matrix is block diagonal with r x r blocks. Assuming a Gaussian
measurement matrix, we argue that the r-local permutation model is more
challenging compared to a recent sparse permutation model. We propose a
proximal alternating minimization algorithm for the general unlabeled sensing
problem that provably converges to a first order stationary point. Applied to
the r-local model, we show that the resulting algorithm is efficient. We
validate the algorithm on synthetic and real datasets. We also formulate the
1-d unassigned distance geometry problem as an unlabeled sensing problem with a
structured measurement matrix.
