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.

Additional details