Unlabeled Compressed Sensing From Multiple Measurement Vectors

This paper introduces an algorithmic solution to a broader class of unlabeled sensing problems with multiple measurement vectors (MMV). The goal is to recover an unknown structured signal matrix, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>, from its noisy linear observation matrix, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Y</i>, whose rows are further randomly shuffled by an unknown permutation matrix <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>. A new Bayes-optimal unlabeled compressed sensing (UCS) recovery algorithm is developed from the bilinear vector approximate message passing (Bi-VAMP) framework using non-separable and coupled priors on the rows and columns of the permutation matrix <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>. In particular, standard unlabeled sensing is a special case of the proposed framework, and UCS further generalizes it by neither assuming a partially shuffled signal matrix <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i> nor a small-sized permutation matrix <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>. For the sake of theoretical performance prediction, we also conduct a state evolution (SE) analysis of the proposed algorithm and show its consistency with the asymptotic empirical mean-squared error (MSE). Numerical results demonstrate the effectiveness of the proposed UCS algorithm and its advantage over state-of-the-art baseline approaches in various applications. We also numerically examine the phase transition diagrams of UCS, thereby characterizing the detectability region as a function of the signal-to-noise ratio (SNR).