The proportional mean decomposition: A bridge between the Gaussian and bernoulli ensembles

Abstract

We consider ill-posed linear inverse problems involving the estimation of structured sparse signals. When the sensing matrix has i.i.d. standard normal entries, there is a full-fledged theory on the sample complexity and robustness properties. In this work, we propose a way of making use of this theory to get good bounds for the i.i.d. Bernoulli ensemble. We first provide a deterministic relation between the two ensembles that relates the restricted singular values. Then, we show how one can get non-asymptotic results with small constants for the Bernoulli ensemble. While our discussion focuses on Bernoulli measurements, the main idea can be extended to any discrete distribution with little difficulty.