Support Recovery With Sparsely Sampled Free Random Matrices

Consider a Bernoulli-Gaussian complex n-vector whose components are V_i = X_iB_i, with X_i ~ C N(0, P_x) and binary B_i mutually independent and iid across i. This random q-sparse vector is multiplied by a square random matrix U, and a randomly chosen subset, of average size n p, p ∈ [0,1], of the resulting vector components is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models where U is typically a matrix with iid components, to allow U satisfying a certain freeness condition. This class of matrices encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdú, as well as a number of information-theoretic bounds, to study the input-output mutual information and the support recovery error rate in the limit of n → ∞. We also extend the scope of the large deviation approach of Rangan and characterize the performance of a class of estimators encompassing thresholded linear MMSE and l₁ relaxation.