Signal Recovery from Unlabeled Samples

Abstract

In this paper, we study the recovery of a signal from a set of noisy linear projections (measurements), when such projections are unlabeled, that is, the correspondence between the measurements and the set of projection vectors (i.e., the rows of the measurement matrix) is not known a priori. We consider a special case of unlabeled sensing referred to as Unlabeled Ordered Sampling (UOS) where the ordering of the measurements is preserved. We identify a natural duality between this problem and classical Compressed Sensing (CS), where we show that the unknown support (location of nonzero elements) of a sparse signal in CS corresponds to the unknown indices of the measurements in UOS. While in CS it is possible to recover a sparse signal from an under-determined set of linear equations (less equations than the signal dimension), successful recovery in UOS requires taking more samples than the dimension of the signal. Motivated by this duality, we develop a Restricted Isometry Property (RIP) similar to that in CS. We also design a low-complexity Alternating Minimization algorithm that achieves a stable signal recovery under the established RIP. We analyze our proposed algorithm for different signal dimensions and number of measurements theoretically and investigate its performance empirically via simulations. The results are reminiscent of phase-transition similar to that occurring in CS.

18 pages, 11 figures. Submitted to IEEE Trans. on Signal Processing

References in corpus (5)

• Self-Calibration and Biconvex Compressive Sensing
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Linear regression without correspondence
• Through the Haze: a Non-Convex Approach to Blind Gain Calibration for Linear Random Sensing Models
• Random Matrices and Matrix Completion

Cited by in corpus (12)

• Signal Amplitude Estimation and Detection from Unlabeled Binary Quantized Samples
• Linear Regression without Correspondences via Concave Minimization
• Algorithms and Fundamental Limits for Unlabeled Detection using Types
• Homomorphic Sensing
• Homomorphic Sensing of Subspace Arrangements
• Quickest Anomaly Detection in Sensor Networks With Unlabeled Samples
• The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors
• Extreme Multi-label Classification from Aggregated Labels
• Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics
• A Hypergradient Approach to Robust Regression without Correspondence
• Unlabelled Sensing: A Sparse Bayesian Learning Approach
• Multiview Sensing With Unknown Permutations: An Optimal Transport Approach