Support Recovery With Sparsely Sampled Free Random Matrices
Antonia Maria Tulino, Giuseppe Caire, Sergio Verdú, Shlomo Shitz Shamai · IEEE Transactions on Information Theory · 2013
Consider a Bernoulli-Gaussian complexn-vector whose components areVi=XiBi, withXi~C N(0,Px) and binaryBimutually independent and iid acrossi. This randomq-sparse vector is multiplied by a square random matrixU, and a randomly chosen subset, of average sizen 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 whereUis typically a matrix with iid components, to allowUsatisfying 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 ofn→ ∞. 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 andl1relaxation.