  In "Unlabeled Sensing", one observes a set of linear measurements of an
underlying signal with incomplete or missing information about their ordering,
which can be modeled in terms of an unknown permutation. Previous work on the
case of a single noisy measurement vector has exposed two main challenges: 1) a
high requirement concerning the \emph{signal-to-noise ratio} ($\snr$), i.e.,
approximately of the order of $n^{5}$, and 2) a massive computational burden in
light of NP-hardness in general.
  In this paper, we study the case of \emph{multiple} noisy measurement vectors
(MMVs) resulting from a \emph{common} permutation and investigate to what
extent the number of MMVs $m$ facilitates permutation recovery by "borrowing
strength". The above two challenges have at least partially been resolved
within our work. First, we show that a large stable rank of the signal
significantly reduces the required snr which can drop from a polynomial in $n$
for $m = 1$ to a constant for $m = \Omega(\log n)$, where $m$ denotes the
number of MMVs and $n$ denotes the number of measurements per MV. This bound is
shown to be sharp and is associated with a phase transition phenomenon. Second,
we propose a computational scheme for recovering the unknown permutation in
practice. For the "oracle case" with the known signal, the maximum likelihood
(ML) estimator reduces to a linear assignment problem whose global optimum can
be obtained efficiently. For the case in which both the signal and permutation
are unknown, the problem is reformulated as a bi-convex optimization problem
with an auxiliary variable, which can be solved by the Alternating Direction
Method of Multipliers (ADMM). Numerical experiments based on the proposed
computational scheme confirm the tightness of our theoretical analysis.
