Unlabelled Compressive Sensing Under Sparse Permutation and Prior Information

Abstract

In this paper, we study the problem of unlabelled compressed sensing, where the correspondence between the measurement values and the rows of the sensing matrix is lost, the number of measurements is less than the dimension of the regression vector, and the regression vector is sparse in the identity basis. Additionally, motivated by practical situations, we assume that we accurately know a small number of correspondences between the rows of the measurement matrix and the measurement vector. We propose a tractable estimator, based on a modified form of the \textsc{Lasso}, to estimate the regression vector, and we derive theoretical error bounds for the estimate. This is unlike previous approaches to unlabelled compressed sensing, which either do not produce theoretical bounds or which produce bounds for intractable estimators. We show that our algorithm outperforms a hard thresholding pursuit (\textsc{Htp}) approach and an $\ell_1$-norm estimator used to solve a similar problem across diverse regimes. We also propose a modified \textsc{Htp} based estimator which has superior properties to the baseline \textsc{Htp} estimator. Lastly, we show an application of unlabelled compressed sensing in image registration, demonstrating the utility of a few known point correspondences.