Support Recovery with Sparsely Sampled Free Random Matrices

Consider a Bernoulli-Gaussian vector whose components are Vi = XiBi, with Bi Bernoulli-q and Xi CN(0; 2), i.i.d. across i and mutually independent. This randomly nulled vector is multiplied by a random matrix U, and a randomly chosen subset of the components of the resulting vector is then observed in additive Gaussian noise. We extend the scope of conventional models where U is typically the identity or a matrix with iid components, to allow U that satisfies a certain freeness condition, which encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo-Verd u, as well as a number of information theoretic bounds, to study the input-output mutual information and the support recovery error rate.