The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing From Multiple Measurement Vectors

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
signal-to-noise ratio
(
$\mathsf {\mathbf {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
multiple
noisy measurement vectors (MMVs) resulting from a
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 computational methods for recovering the unknown permutation. For the “oracle case” with known signal, the maximum likelihood (ML) estimator reduces to a linear assignment problem whose global optimum can be obtained efficiently. If both the signal and the permutation are unknown, the problem becomes a quadratic assignment problem; while such a problem is generally NP-hard and hence poses a significant challenge, we propose to tackle it via projected gradient descent with a non-convex constraint set, and establish a monotonic descent property of this scheme. Numerical experiments based on the proposed computational approach confirm the tightness of our theoretical analysis.